C
挺有意思的题，但要在场上切难度还是挺大的（和前十题不在一个档次）
转成原根后变成模意义下的01背包（原本考虑了一下转生成函数，但是得保留\(np\)位，显然不靠谱；而bitset优化暴力又过不去）。
发现做这个背包的过程是或运算，也就是说有用的操作只会把某些0变成1，那么自然地会想到：每次用\(Poly(log)\)的时间找到要改变的位置，这样总的复杂度就是\(O(pPoly(log))\)的。
但这个要改变的位置的条件比较抽象，是\(f[i]=0,f[i-x]=1\)（另一种情况同理），考虑一遍跳过去的话，很难直接找到下一个满足这个条件的位置。
但通过联想一些做题经验（比如CF-R857-E），发现要找到下一个两段不同的位置是容易的（二分+哈希BIT即可），即\(f[i]=0,f[i-x]=1 或 f[i]=1,f[i-x]=0\)
那如果直接这么找，再判断一下，复杂度如何呢？感性认知上挺对的；实际上：转移形成的有向图形成若干置换环，那么这两种边的个数是一样的。所以总复杂度就是\(O(plog^2p+n)\)了！
实现有些小细节，比如转成原根之后是在\(p-1\)的环上走；不同起点的哈希判断要平移（这个判错会导致复杂度不对而TLE，然后以为其它错导致的）;没有赋值操作的特判等。（其实想清楚了也都还好）
点击查看代码
#include <bits/stdc++.h>
using namespace std;
inline int fpw(int a,int x,int P){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
inline int prd(int a,int b,int P){return 1ll*a*b%P;}
#define repeat(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
ll getG(ll n){ // 求 n 最小的原根
static vector<ll> a; a.clear();
ll k=n-1;
repeat(i,2,sqrt(k+1)+1)
if(k%i==0){
a.push_back(i); // a 存放 (n-1) 的质因数
while(k%i==0)k/=i;
}
if(k!=1)a.push_back(k);
repeat(i,2,n){ // 枚举答案
bool f=1;
for(auto j:a)
if(fpw(i,(n-1)/j,n)==1){
f=0;
break;
}
if(f)return i;
}
return -1;
}// BSGS，a 和 mod 互质
typedef unsigned long long ul;
const int N=2e6+5;
const ul B=793999;
struct BIT{
int n;
ul a[N];
void init(int m){
n=m;
for(int i=0;i<=n;i++) a[i]=0;
}
void upd(int x,ul y){
//cout<<"upd:"<<x<<" "<<y<<endl;
x++;
while(x<=n) a[x]+=y,x+=x&-x;
}
ul cnt(int x){
x++;
ul s=0;
while(x) s+=a[x],x-=x&-x;
return s;
}
}T;
ul pw[N];
int P,G,n,a[N],id[N];
int f[N];
ul cnt(int l,int r){
//cout<<"cnt:"<<l<<" "<<r<<" "<<T.cnt(r)-T.cnt(l-1)<<endl;
return (T.cnt(r)-T.cnt(l-1))*pw[P-1-r];
}
stack<int>q;
int sum;
void work(int x,int last,int end){
// cout<<x<<" "<<last<<" "<<end<<endl;
int cal=0;
while(last<end){
// cout<<"last="<<last<<endl;
cal++;
if(cal>P) return;
int l=1,r=end-last;
while(l<r){
int mid=(l+r)>>1;
if(cnt(last+1,last+mid)==cnt(last-x+1,last-x+mid)) l=mid+1;
else r=mid;
}
// cout<<"l="<<l<<endl;
if(cnt(last+1,last+l)==cnt(last-x+1,last-x+l)) last=end;
else{
//puts("!");
last=last+l;
//cout<<last<<endl;
if(!f[last]) q.push(last);
}
}
sum+=cal;
}
int main() {
cin>>P>>n;
pw[0]=1; for(int i=1;i<P;i++) pw[i]=pw[i-1]*B;
G=getG(P);
//if(n==100000) cout<<"G="<<G<<endl;
int s=1;
for(int i=0;i<P-1;i++,s=prd(s,G,P)) id[s]=i;
T.init(P-1);
int tot=0,ans=1,vs=0;
for(int i=1;i<=n;i++){
int op,x;
scanf("%d%d",&op,&x);
if(!x){
ans=0;
continue;
}
x=id[x];
//cout<<"x="<<x<<endl;
if(op==0){
vs=1;
if(f[x]) continue;
f[x]=1;
T.upd(x,pw[x]);
}
else a[++tot]=x;
}
// cout<<ans<<endl;
if(!vs){
cout<<P-1<<endl;
return 0;
}
for(int i=1;i<=tot;i++){
int x=a[i];
work(x,x-1,P-2);
work(x-(P-1),-1,x-1);
while(!q.empty()){
int u=q.top();
q.pop();
if(f[u]) continue;
f[u]=1;
T.upd(u,pw[u]);
}
//if(n==100000 && i%1000==0) cout<<"i="<<i<<" sum="<<sum<<endl;
}
for(int i=0;i<P-1;i++) if(!f[i]) ans++;
cout<<ans<<endl;
return 0;
}