Descrption
\(LZK\)发明一个矩阵游戏,大家一起来玩玩吧,有一个\(N\)行M列的矩阵。第一行的数字是\(1,2,…M\),第二行的数字是\(M+1,M+2…2*M\),以此类推,第 \(N\) 行的数字是\((N-1)*M+1,(N-1)*M+2…N*M\)。
例如,\(N=3,M=4\)的矩阵是这样的:
1 2 3 4
5 6 7 8
9 10 11 12
对于身为智慧之神的 \(LZK\) 来说,这个矩阵过于无趣.于是他决定改造这个矩阵,改造会进行 \(K\) 次,每次改造会将矩阵的某一行或某一列乘上一个数字,你的任务是计算最终这个矩阵内所有数字的和,输出答案对\(10^9+7\)取模。
Input
Output
Sample Input
game.in
3 4 4
R 2 4
S 4 1
R 3 2
R 2 0
game.out
94
?```
Sample Output
game.in
2 4 4
S 2 0
S 2 3
R 1 5
S 1 3
game.out
80
Hint
分析
方法一:
显然对于每一个数,乘法的顺序不会对结果产生任何影响,我们用数组 \(r_i\) 标记第 \(i\) 行所有乘的数的积,用数组 \(s_i\) 标记第 \(j\) 列所有乘的数的积。
通过观察,可以发现第 \(i\) 行第 \(j\) 列的数字为:\((i-1)*m+j\) 。
因为先做行的乘法或先做列的乘法,结果都一样,所以我们可以先做行的乘法。然后我们可以把同一列的所有数都加起来,令 \(sum_j\) :表示做了行乘法后,第 \(j\) 列的和。
令 \(k_1=\sum_{i=1}^n r_i\times (i-1)*m,k_2=\sum_{i=1}^{n} r_i\) ,显然 \(k_1,k_2\) 是跟 \(i\) 相关数。 \(sum_j=k_1+j\times k_2\) 。
Code
#include <bits/stdc++.h>
typedef long long LL;
const int maxn=1e6+5;
const LL Mod=1e9+7;
LL s[maxn],r[maxn];
int n,m;
void Init(){
int k;scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)r[i]=1;
for(int i=1;i<=m;++i)s[i]=1;
while(k--){
LL x,y;char ch;
scanf(" %c%lld%lld",&ch,&x,&y);
if(ch==‘S‘)s[x]=(s[x]*y)%Mod;
if(ch==‘R‘)r[x]=(r[x]*y)%Mod;
}
}
void Solve(){
LL sum1=0,sum2=0,ans=0;
for(int i=1;i<=n;++i)//第一部分:sigma r[i]*(i-1)*m
sum1=(r[i]*m%Mod*(i-1)%Mod+sum1)%Mod;
for(int i=1;i<=n;++i)//第二部分:sigma r[i]
sum2=(sum2+r[i])%Mod;
for(int i=1;i<=m;++i)//ans=sigma sumi*s[j]
ans=(ans+(sum1+sum2*i%Mod)%Mod*s[i]%Mod)%Mod;
printf("%lld\n",ans);
}
int main(){
Init();
Solve();
return 0;
}
方法二:
Code
#include <bits/stdc++.h>
typedef long long LL;
const int maxn=1e6+5;
const LL Mod=1e9+7;
LL col[maxn];//col[i]记录第i列的乘数
LL a[maxn],b[maxn];//a[i],b[i]分别为第i行首项和公差
LL sum[maxn];//sum[i]表示第i列之和
int n,m;
void Init(){
int k;scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i){
a[i]=(1LL*(i-1)*m+1)%Mod;//第i行的首项
b[i]=1;//第i行的公差
}
for(int i=1;i<=m;++i)col[i]=1;
while(k--){
LL x,y;char ch;
scanf(" %c%lld%lld",&ch,&x,&y);
if(ch==‘S‘)
col[x]=(col[x]*y)%Mod;
if(ch==‘R‘){
a[x]=(a[x]*y)%Mod;
b[x]=(b[x]*y)%Mod;
}
}
}
void Solve(){
LL d=0,ans=0;
for(int i=1;i<=n;++i){//求出第一列之和
sum[1]=(sum[1]+a[i])%Mod;//首项
d=(d+b[i])%Mod;//公差
}
for(int i=2;i<=m;++i)//利用等差数列公式求出其他列之和
sum[i]=(sum[i-1]+d)%Mod;
for(int i=1;i<=m;++i)
ans=(ans+sum[i]*col[i]%Mod)%Mod;
printf("%lld\n",ans);
}
int main(){
Init();
Solve();
return 0;
}
原文:https://www.cnblogs.com/hbhszxyb/p/13425634.html