「题解」矩阵游戏 game

题目链接:GMOJ 6277

题目

题目描述

LZK 发明一个矩阵游戏,大家一起来玩玩吧,有一个 $N$ 行 $M$ 列的矩阵。第一行的数字是 $1,2,3,…,M$,第二行的数字是 $M+1,M+2,…,2\times M$,以此类推,第 $N$ 行的数字是 $(N-1)\times M+1,(N-1)\times M+2,\cdots,N\times M$。
例如,$N=3,M=4$ 的矩阵是这样的:

1234
5678
9101112

对于身为智慧之神的 LZK 来说,这个矩阵过于无趣。于是他决定改造这个矩阵,改造会进行 $K$ 次,每次改造会将矩阵的某一行或某一列乘上一个数字,你的任务是计算最终这个矩阵内所有数字的和,输出答案对 $K$ 取模。

输入格式

第一行包含三个正整数 $N,M,K$,表示矩阵的大小与改造次数。接下来的 $K$ 行,每行会是如下两种形式之一:

  • R X Y,表示将矩阵的第 $X$ 行变为原来的 $Y$ 倍。
  • S X Y,表示将矩阵的第 $X$ 列变为原来的 $Y$ 倍。

输出格式

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

样例输入输出

#1

  • Input:
3 4 4
R 2 4
S 4 1
R 3 2
R 2 0
  • Output:
94

解释

操作后矩阵会变成这样:

1234
0000
18202224

#2

  • Input:
2 4 4
S 2 0
S 2 3
R 1 5
S 1 3
  • Output:
80

数据范围

变量数据范围
$n,m$$1\leq n,m\leq 10^6$
$k$$1\leq k\leq 10^5$

时空限制

题目编号时间限制空间限制
GMOJ 6277$1\text{s}$$512\text{MiB}$

题解

思路

等差数列求和即可。

代码

#include<cstdio>
typedef long long ll;
#define MOD 1000000007ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=1000000+5;
const int MAXM=1000000+5;
const int MAXK=100000+5;
char str[4];
int n,m,k;
int x,y;
ll line[MAXN],column[MAXM];
inline ll GetVal(ll,ll);
int main(void){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    register int i;
    register ll sum=0,d=0,ans=0;
    n=read(),m=read(),k=read();
    //scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;++i)
        line[i]=1;
    for(i=1;i<=m;++i)
        column[i]=1;
    while(k--){
        do
            str[0]=getchar();
        while(str[0]<'A'||'Z'<str[0]);
        x=read(),y=read();
        //scanf("%s%d%d",str,&x,&y);
        if(str[0]=='R')
            line[x]=(line[x]*y)%MOD;
        if(str[0]=='S')
            column[x]=(column[x]*y)%MOD;
    }
    for(i=1;i<=n;++i){
        sum=(sum+(GetVal(i,1)*line[i]%MOD))%MOD;//求首项和
        d=(d+line[i])%MOD;//求公差
    }
    for(i=1;i<=m;++i){
        ans=(ans+sum*column[i])%MOD;//每一项的倍数累计
        sum=(sum+d)%MOD;//通项公式(公差翻倍)
    }
    printf("%lld\n",ans);//输出答案
    return 0;
}
inline ll GetVal(ll i,ll j){//这里记得开long long
    return ((i-1)*m%MOD+j)%MOD;
}