Task 1. 矩阵游戏
题目大意：有一个 n 行 m 列的矩阵，第一行的数字为 1 2 3 ... m-1 m，第二行为 m+1 m+2 m+3 ...2m-1 2m，依次类推，第 i 行为 (i-1)m+1 (i-1)m+2 (i-1)m+3 ... (i-1)m+m-1 (i-1)m+m。现在有 k 次操作，每次操作对这个矩阵的第 x 行或者第 x 列的所有数字乘上 c ，求所有操作之后矩阵中数字的和 (mod 109+7)。
数据范围：1≤N,M≤106,1≤K≤10
很明显，操作的顺序是不重要的，所以我们把对行的操作和对列的操作分开处理。
设 ri 是对第 i 行乘的数，si 是对第 i 列乘的数，所有的 ri si 在开始时都为 1。
一种 80 分暴力的思路：
先处理所有关于行的操作，直接算出所有行不考虑关于列的操作的结果，再加上所有列的和乘上 si-1 的结果，这样对于一个位置 (x,y) 在第一次的结果中会被算 rx 次，在第二次的结果中会被计算 sy-1 次。这样的位置会被算 (rx+sy-1) 次，要么不被操作影响只算 1 次(rx=1,sy=1)，要么被一个操作影响(rx=c,sy=1或rx=1,sy=c)，要么被两个操作影响(rx=c,sy=d)。这样的交点的贡献应该是 rx*sy ，直接减掉前面多算的再加上实际的贡献，交点数量至多 K2 个。复杂度 O(N+M+K2)。
正解：
80分做法的复杂度瓶颈在于对交点的枚举，是否存在一种交点的有效枚举方法或者可以不考虑交点的做法？
通过观察矩阵，我们发现如果没有列操作，每一列的和组成了一个等差数列（想象我们把矩阵拍扁了）。如果这时候再加上列操作，我们就可以直接对这个数列的某一项直接修改了。
维护行的首项和公差的前缀和，这二者即上述等差数列的首项和公差，枚举每一项即可。复杂度 O(N+M)。
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 6 template<class T>void read(T &x){ 7 x=0; char c=getchar(); 8 while(c<‘0‘||‘9‘<c)c=getchar(); 9 while(‘0‘<=c&&c<=‘9‘){x=(x<<1)+(x<<3)+(c^48); c=getchar();} 10 } 11 typedef long long ll; 12 const int N=1000050; 13 const int M=1000000007; 14 ll mul(int x,int y){ return (1ll*x*y)%M;} 15 16 int n,m,k; 17 int r[N],s[N]; 18 int a,d,ans; 19 int main(){ 20 // freopen("game.in","r",stdin); 21 // freopen("game.out","w",stdout); 22 read(n); read(m); read(k); 23 for(int i=max(n,m);i;i--)r[i]=s[i]=1; 24 char op[3]; int x,c; 25 for(int i=1;i<=k;i++){ 26 scanf("%s",op); 27 read(x); read(c); 28 if(op[0]==‘R‘) r[x]=mul(r[x],c); 29 else s[x]=mul(s[x],c); 30 } 31 for(int i=1;i<=n;i++){ 32 a=(1ll*a+mul((1ll*(i-1)*m+1)%M,r[i]))%M; 33 d=(d+r[i])%M; 34 } 35 for(int i=1;i<=m;i++){ 36 ans=(1ll*ans+mul(a,s[i]))%M; 37 a=(a+d)%M; 38 } 39 printf("%d\n",ans); 40 return 0; 41 }
PS:被 1LL 教做人了。
原文：https://www.cnblogs.com/opethrax/p/11303600.html
