矩阵游戏

矩阵游戏(数学规律 \(\star\star \))

时限：\(1s\) 内存：\(256M\)

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

第一行包含三个正整数\(N、M、K\)，表示矩阵的大小与改造次数。接下来的行,每行会是如下两种形式之一:
- \(R\ X\ Y\),表示将矩阵的第\(X(1 ≤ X ≤ N)\)行变为原来的\(Y(0 ≤ Y ≤10^9)\)倍.
- \(S\ X\ Y\),表示将矩阵的第\(X(1 ≤ X ≤ M)\)列变为原来的\(Y(0 ≤ Y ≤10^9)\)倍.

Output

输出一行一个整数,表示最终矩阵内所有元素的和对\(10^9+7\)取模的结果。

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\) 列的和。

\[sum_j=\sum_{i=1}^{n}r_i\times((i-1)\times m+j) \\ \Rightarrow sum_j=\sum_{i=1}^{n}r_i\times (i-1)*m+\sum_{i=1}^{n}r_i \times j \\ \Rightarrow sum_j=\sum_{i=1}^n r_i\times(i-1)*m+j\times \sum_{i=1}^{n} r_i \]
令 \(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;
}

方法二：

经过分析可知：
1. 操作可以任意顺序进行，不会影响最终结果。
2. 每一行都是一个等差数列，且一开始公差都为\(1\)。
3. 每一列相加得到的数列也是等差数列，公差为所有等差数列的公差之和。
我们就可以考虑先进行的操作，再进列的操作。每一行的数乘上一个数后仍然是等差数列，公差增加相应倍数。这样，对于每一行，我们只用维护第一项和它的公差就好了。
当行的操作弄完后，将所有等差数列的第一项相加，得到第一列的和，再将公差相加，得到每一列和的公差，就可以求出每一列的和，剩下的就是直接对列的和进行乘法就好了。

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;
}

矩阵游戏

矩阵游戏(数学规律 \(\star\star \))

推荐阅读