Link:2025夏令营提高冲刺标准卷19
题面
题解
暴力-直接模拟
按照题意一个一个修改元素，有手就行。O(nmq)，30pts，全款拿下。
暴力+优化
对于区间可以做一个差分
前置知识：逆元
根据费马小定理（oi.wiki)，当 p 是个质数时，满足：
a^{(p-1)} \equiv 1 (\mod p)
当 b 与 p 互质且 ab \equiv bd (\mod p) 时，可得 a \equiv d (\mod p)
又因为质数和所有小于它的数互质（质数的性质），可得：
a^{(p-2)} \equiv \frac{1}{a} (\mod p)
所以想要在 \mod p 下除 a 只需要乘上 a^{(p-2)} 即可。又因为 1e9+7 是个质数，所以逆元法适用于本题。记 p=1e9+7 ，以下 a 的逆元皆指 a^{(p-2)} 。
由于每次操作是整行乘和整列乘，则开一个 r 数组和一个 c 数组，操作1对应在 r_l 乘上一个 v 并且在 r_{r+1} 乘上一个 v 的逆元，操作2对应在 c_l 乘上一个 v 并且在 c_{r+1} 乘上一个 v 的逆元。（本句中上面的大 r 指数组 r ，下标中的 r 指读入的右边界 r 。此后下文的 r 均指数组 r 。）
那么想要求出这一列乘上了多少的 v ，代入下式：
c_i= \prod_{k=1}^{i} c_k
同理，
r_i=\prod_{k=1}^{i} r_k
（差分看不出来自行百度，真看不出来或者不知道差分是什么的自行oi-wiki）
OK，最后的答案就是:
\sum_{i=1}^{n} \sum_{j=1}^{m} c_j r_i [(i-1)m+j]
此时如果暴力加起来就是 O(nm) ，40pts不全款拿下。
开始正解
时间复杂度太高了，看看能不能变成线性的东西求解。
把大括号拆开就是：
\sum_{i=1}^{n} \sum_{j=1}^{m} m c_j [r_i (i-1)] + (c_j j) r_i
那么分开求解。
先看
\sum_{i=1}^{n} \sum_{j=1}^{m} m c_j [r_i (i-1)]
明显和 j 无关的可以直接直接提出来，于是变成：
\sum_{i=1}^{n} m r_i (i-1) (\sum_{j=1}^{m} c_j)
很明显 (\sum_{j=1}^{m} c_j) 可以直接在求 c_j 的时候顺便求一求。时间复杂度直接 O(m) 。
同时又发现因为 m r_i (i-1) 和 j 无关，所以根据乘法分配律， \sum_{i=1}^{n} m r_i (i-1) 预处理（复杂度 O(n) ）记作 t_r ， \sum_{j=1}^{m} c_j 预处理记作 s_c ，这部分就可以简单表示为：
m s_c t_r
接着关注：
\sum_{i=1}^{n} \sum_{j=1}^{m} (c_j j) r_i
同样， r_i 提出去，
\sum_{i=1}^{n} r_i \sum_{j=1}^{m} c_j j
注意到 \sum_{i=1}^{n} r_i 预处理的时间复杂度是 O(n) ， \sum_{j=1}^{m} c_j j 预处理的时间复杂度是 O(m) ，
预处理 \sum_{i=1}^{n} r_i 记作 s_r ，预处理 \sum_{j=1}^{m} c_j j 记作 t_c ，这部分简单表示为：
t_c + s_r
于是答案就是：
m s_c t_r + t_c s_r
（来源于题面）
namespace FastIO {
#define il inline
const int iL = 1 << 25;
char ibuf[iL], *iS = ibuf + iL, *iT = ibuf + iL;
#define GC() (iS == iT) ? \
(iT = (iS = ibuf) + fread(ibuf, 1, iL, stdin), (iS == iT) ? EOF : *iS++) : *iS++
template <class T>il void read(T &x) {
x = 0;
char c = GC(); bool flg = false;
while (!isdigit(c)) {flg |= c == '-'; c = GC();}
while (isdigit(c)) {x = (x << 1) + (x << 3) + (c & 15); c = GC();}
if (flg) x = -x;
}
char Out[iL], *iter = Out;
#define Flush() fwrite(Out, 1, iter - Out, stdout); iter = Out
template <class T>il void write(T x, char LastChar = '\n') {
int c[35], len = 0;
if (x < 0) {*iter++ = '-'; x = -x;}
do {c[++len] = x % 10; x /= 10;} while (x);
while (len) *iter++ = c[len--] + '0';
*iter++ = LastChar; Flush();
}
}
using namespace FastIO;
命名空间会看吧？快读是read()，快写是write()，答案就一个数字cout就可以了，还要什么快写？
计算最终答案 code：
部分代码不予展示。
#include<bits/stdc++.h>
//把快读快写模板放这
using namespace std;
typedef long long ll;
constexpr ll MOD=1e9+7,MAXN=1e6+50;
ll n,m,q;
ll row[MAXN],col[MAXN];
int main(){
//...
ll tr=0;
ll sr=0;
for(ll i=1;i<=n;i++){
row[i]*=row[i-1];
row[i]%=MOD;
tr+=row[i]*(i-1)%MOD;
tr%=MOD;
sr+=row[i];
sr%=MOD;
}
ll sc=0;
ll tc=0;
for(ll j=1;j<=m;j++){
col[j]*=col[j-1];
col[j]%=MOD;
sc+=col[j]%MOD;
sc%=MOD;
tc+=col[j]*j%MOD;
tc%=MOD;
}
ll ans=1;
ans=m*sc%MOD*tr%MOD;
ans=(ans+tc*sr%MOD)%MOD;
write(ans);
return 0;
}
2025.8.11