2026-4-15D 操作(op)
题目大意
多组测试数据,组数为 T。
给定模数 p 和 n 个操作,有一个变量 w 初始为 0,操作分为两种:
- 令 w=x。
- 令 w=(w+x)modp
如果可以任意排序这些操作,最终的 w 在 0∼p−1 中有多少数无法取到?
对于所有数据,1≤T≤2,1≤n≤106,2≤p≤106,∑n≤1.1×106,0≤x<p。
思路
首先我们发现,最终得到的 w 一定只与最后一个 1 操作及其以后的 2 操作有关。
因此,问题转换为任意选取一个 1 操作和若干 2 操作,求最终多少数在模 p 下凑不出来,我们发现这类似于一个背包 DP,于是设 fi 表示 i 能否被凑出来。
对于一个 2 操作数值为 v,有如下状态转移方程:
fi=fi∨f(i−v+p)modp
所以,这其实是个 DP 问题,但是直接转移是 O(np) 的,考虑进行优化。
对于每次更新,一定是有 f(i−v+p)modp=1,也就是说我们可以通过将 f 看作超长 0/1 串,而若 f 与 f≫v 相同时,一定不需要更新。(注意此时前提条件,不要看反)
因此,我们需要一个支持查询区间哈希值的数据结构,这里使用树状数组,定义每个位置的前缀哈希值为 (∑fi×Pi)modM(注意是 P 不是 p)。
但是,这样我们只能保证哈希相同时一定不会多更新,但哈希不同时会更新到无用的分支上,我们需要证明不会浪费太多复杂度。
我们发现,每个 fi 仅会从 0→1 然后再也不会变化,所以整个序列的有用操作次数 ≤p,考虑从此入手。
在模 p 意义下,我们会发现 fi 在 v 时的更新其实形成了 (v,p) 个环(这里 (v,p) 是最大公因数的意思)。
为什么是 (v,p) 个环?
我们以从 0 开始的环为例,经过的点依次为 0,v,2v,3v,⋯(modp),也可以表示为 kv≡0(modp),显然有 p∣kv,也就是 (v,p)p∣k×(v,p)v。
此时,我们需要的是最小的 k,而 (v,p)p 与 (v,p)v 显然互质,也就是 k 最小为 (v,p)p。(注意互质)
也就是说,一共有 (v,p)p 个环。
由于环互不相交,我们可以只看一个 0/1 环,显然如果有一个 0 后有 1 也一定存在一个 1 后有 0。(可以想一下 0,1,1,0,0,1)
也就是说,我们最多只会浪费 p 次更新,也就是总更新次数 ≤2p,所以这个做法的时间复杂度为 O(nlogp+plog2p)。
写在后面
这道题我做了四天,重构两遍,卡常一小时,前面所述哈希可能并不可用,需要用 unsigned long long 的自然溢出来取模。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
typedef unsigned long long ULL;
namespace Fenwick {
const int N = 2e6+10;
const int P = 2011;
int n , p;
ULL pow[N];
ULL c[N];
bitset<N> bit;
int res[N] , cnt;
inline int lowbit(int x) {
return x & (-x);
}
void init(int x) {
memset(c , 0 , (n+1)*sizeof(c[0]));
p = x; n = x * 2; bit.reset();
pow[0] = 1;
pow[1] = P;
for(int i = 2 ; i <= n ; i ++) {
pow[i] = pow[i-1] * P;
}
}
void modify(int x) {
int i = x; bit[x] = true;
while(i <= n) {
c[i] += pow[x];
i += lowbit(i);
}
}
ULL query(int x) {
ULL res = 0;
while(x) {
res += c[x];
x -= lowbit(x);
}
return res;
}
inline int get(int x) {
return bit[x];
}
void set(int x) {
if(x < 1 || x > p) return;
if(!get(x)) modify(x);
if(!get(x+p)) modify(x+p);
}
void update(int l , int r , int v) {
if(query(r+p) - query(l+p-1) == (query(r+p-v) - query(l+p-v-1)) * pow[v]) return;
if(l == r) {
if(bit[l+p-v]) res[++ cnt] = l;
return;
}
int mid = (l+r) >> 1;
update(l , mid , v);
update(mid+1 , r , v);
}
}
namespace Main {
inline int read() {
int x = 0 , f = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
const int N = 1e6+10;
int vec[N] , cnt;
void solve() {
int p , n;
p = read(); n = read(); cnt = 0;
Fenwick::init(p);
bool flag = true;
for(int i = 1 ; i <= n ; i ++) {
int op , v;
op = read(); v = read();
v %= p;
if(!op) {
flag = false;
Fenwick::set(v+1);
} else if(v) {
vec[++ cnt] = v;
}
}
if(flag) {
printf("%d\n" , p-1);
return;
}
for(int i = 1 ; i <= cnt ; i ++) {
Fenwick::update(1 , p , vec[i]);
for(int j = 1 ; j <= Fenwick::cnt ; j ++) Fenwick::set(Fenwick::res[j]);
Fenwick::cnt = 0;
}
int res = 0;
for(int i = 1 ; i <= p ; i ++)
if(!Fenwick::get(i)) {
res ++;
}
printf("%d\n" , res);
return;
}
void main() {
int T; T = read();
while(T --) solve();
}
}
int main() {
Main::main();
return 0;
}