[CSP-S模拟测试]:矩阵游戏(数学)
题目描述
$LZK$发明一个矩阵游戏,大家一起来玩玩吧,有一个$N$行$M$列的矩阵。第一行的数字是$1,2,...,M$,第二行的数字是$M+1,M+2,...,2\times M$,以此类推,第$N$行的数字是$(N-1)\times M+1,(N-1)\times M+2,...,N\times M$。
例如$N=3,M=4$的矩阵是这样的:
1 2 3 4
5 6 7 8
9 10 11 12
对于身为智慧之神的$LZK$来说,这个矩阵过于无趣。于是他决定改造这个矩阵,改造会进行$K$次,每次改造会将矩阵的某一行或某一列乘上一个数字,你的任务是计算最终这个矩阵内所有数字的和,输出答案对${10}^9+7$取模。
输入格式
第一行包含三个正整$N$、$M$、$K$,表示矩阵的大小与改造次数。接下来的行,每行会是如下两种形式之一:
$R\ X\ Y$,表示将矩阵的第$X$行变为原来的$Y$倍。
$S\ X\ Y$,表示将矩阵的第$X$列变为原来的$Y$倍。
输出格式
输出一行一个整数,表示最终矩阵内所有元素的和对${10}^9+7$取模的结果。
样例
样例输入1:
3 4 4
R 2 4
S 4 1
R 3 2
R 2 0
样例输出1:
94
样例输入2:
2 4 4
S 2 0
S 2 3
R 1 5
S 1 3
样例输出2:
80
数据范围与提示
$40\%$的数据满足:$1\leqslant N,M\leqslant 1,000$;
$80\%$的数据满足:$1\leqslant N,M\leqslant 1,000,000,1\leqslant K\leqslant 1,000$;
$100\%$的数据满足:$1\leqslant N,M\leqslant 1,000,000,1\leqslant K\leqslant 100,000$。
题解
$40\%$算法:
暴力求出每一个点的初始值,暴力更改,暴力统计答案。
时间复杂度:$\Theta(N\times K)$。
期望得分:$40$分。
$100\%$算法:
显然,我们如果$\Theta(N\times M)$求出每一个点的初始值是不能接受的,所以我们考虑用式子推出,点$(i,j)$的初始值就是$(i-1)\times M+j$。
考虑乘法交换律,先乘和后乘一样,所以我们可以预处理出来$\prod R$和$\prod S$,设其分别为$h[i]$和$l[i]$。
再来推式子,每一个点对答案的贡献就是:$((i-1)\times M+j)\times h[i]\times l[i]$。
把式子拆开:$(i-1)\times M\times h[i]\times l[i]+j\times h[i]\times l[i]$。
我们可以维护$sumh=\sum \limits_{i=1}^N h[i]$和$sum=\sum \limits_{i=1}^N (i-1)\times M\times h[i]$。
那么答案即为$\sum \limits_{i=1}^M (sum+i\times sumh)\times l[i]$。
具体实现看代码叭~
时间复杂度:$\Theta(N+M)$。
期望得分:$100$分。
代码时刻
$40\%$算法:
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long Map[5000][5000];
long long ans;
int main()
{
scanf("%d%d%d",&n,&m,&k);
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
Map[i][j]=++cnt;
while(k--)
{
char ch[5];
long long x,y;
scanf("%s%lld%lld",ch+1,&x,&y);
if(ch[1]=='R')
for(int i=1;i<=m;i++)
Map[x][i]=(Map[x][i]*y)%1000000007;
else
for(int i=1;i<=n;i++)
Map[i][x]=(Map[i][x]*y)%1000000007;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=(ans+Map[i][j])%1000000007;
printf("%lld",ans);
return 0;
}
$100\%$算法:
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int h[1000001],l[1000001];
int sum,sumh,ans;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=1000000;i++)
h[i]=l[i]=1;
while(k--)
{
char ch[3];
int x,y;
scanf("%s%d%d",ch+1,&x,&y);
if(ch[1]=='R')h[x]=1LL*h[x]*y%1000000007;
else l[x]=1LL*l[x]*y%1000000007;
}
for(int i=1;i<=n;i++)
{
sum=(sum+(1LL*(i-1)*m+1)%1000000007*h[i]%1000000007)%1000000007;
sumh=(sumh+h[i])%1000000007;
}
for(int i=1;i<=m;i++)
{
ans=(ans+1LL*sum*l[i]%1000000007)%1000000007;
sum=(sum+sumh)%1000000007;
}
printf("%lld",ans);
return 0;
}
rp++
最新文章
- 部署Qt程序时plugins相关问题
- JS运算符
- Warning C4819
- 升级nodejs版本
- hdu1025 最长上升子序列 (nlogn)
- 对table的tr使用display:block显示colspan失效问题的解决
- BITED数学建模七日谈之四:数学模型分类浅谈
- C#操作Excel(2)-- 打开-读取Excel文档
- 在内存中观察CRL托管内存及GC行为
- 验证Oracle收集统计信息参数granularity数据分析的力度
- JsDoc脚本注释文档生成
- Loadrunner回放https脚本时出现错误Error -27780 Connection reset by peer解决办法
- 【Java】「深入理解Java虚拟机」学习笔记(1) - Java语言发展趋势
- emSecure Use Digital Signatures to protect your products
- Django 日志
- vue.js相关UI组件收集
- poj1696 Space Ant【计算几何】
- c#如何仅在datatgirdview控件的头部(列名处)添加右键菜单
- thinkphp3.2 常用入口文件
- 解释型vs编译型 动态vs静态 强类型vs弱类型