【2025广东省队集训day1】操作 做题记录

给定一个 质数 $p$ 和 $n$ 个操作，操作有如下两种：

• 给定 $x$，将 $w$ 修改为 $x$；
• 给定 $x$，将 $w$ 修改为 $(w\times x)\text{ mod } p$；

其中 $w$ 是一个初始为 $1$ 的变量。

你可以任意安排 $n$ 个操作的顺序，求有多少个 $[0,p-1]$ 中的数 $x$ 满足无论怎么安排操作的顺序最终的 $w$ 都不能等于 $x$。

$1\le p,n\le 10^6$。

首先乘法很累，由于质数必定存在原根故可以找到 $p$ 的原根把乘法变成加法。单次判断一个数是否原根需要 $O(\sqrt p\log p)$ 的复杂度，而最小原根的大小大约是 $O(p^{0.25})$ 的，所以这部分的复杂度可以接受。

接下来问题转化为下标取模的 bool 版 01 背包，可以用 bitset 优化到 $O(\frac{np}{\omega})$，但还是不能接受。

然后我就不会了，实际上注意到有效更新只有至多 $p$ 次，所以一个想法是每次快速找到当前的有效更新。

考虑分治，断环为链后可以每次判断 $[l,r]$ 的哈希和 $[l+x,r+x]$ 的哈希是否相等，如果不相等就代表 $[l,r]$ 里可能存在有效更新，那么分治的时候只往可能存在有效更新的一半递归即可。

其实这样做还是存在一点问题，因为哈希值不同可能有 $0$ 向 $1$ 更新的情况，这种其实也是无效更新。但是考虑 $i$ 向 $(i+x)\text{ mod }p$ 连边后肯定形如若干个环，所以若存在 $0\to 1$ 那么环上也一定存在 $1\to 0$，故总更新次数最多只有 $2p$ 次，还是对的。

那么时间复杂度 $O(p\log ^2p)$，还有一个 $\log$ 来自于树状数组求区间哈希。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <bitset>

using namespace std;

const int S=2000005,MS=200005;

#define p1 998244353
#define p2 1000000007
#define bse 5

int pw1[S],pw2[S];
int m,n;
int gg,gln[S];
bool res[S];
int tr1[S],tr2[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%m) res=y&1?1ll*res*x%m:res;
	return res;
}

inline int getg()
{
	if(m==2) return 1;
	vector<int> vec;
	for(int i=2;i*i<=m-1;i++)
		if((m-1)%i==0) vec.push_back(i),vec.push_back((m-1)/i);
	for(int i=2;i<m;i++)
	{
		int fl=true;
		for(int x:vec)
			if(qpow(i,x)==1)
			{
				fl=false;
				break;
			}
		if(fl) return i;
	}
	return -1; // should not run this
}

inline void add(int p)
{
	int pos=p;
	for(int i=p;i<=m*2;i+=i&-i)
	{
		tr1[i]=(tr1[i]+pw1[pos])%p1;
		tr2[i]=(tr2[i]+pw2[pos])%p2;
	}
}

inline pair<int,int> que(int p)
{
	int r1=0,r2=0;
	for(int i=p;i>=1;i-=i&-i)
	{
		r1=(r1+tr1[i])%p1;
		r2=(r2+tr2[i])%p2;
	}
	return make_pair(r1,r2);
}
inline pair<int,int> quelr(int l,int r)
{
	auto rr=que(r),rl=que(l-1);
	return make_pair((rr.first-rl.first+p1)%p1,
					 (rr.second-rl.second+p2)%p2);
}
inline bool cmp(int l1,int r1,int l2,int r2)
{
	if(l1>l2) swap(l1,l2),swap(r1,r2);
	auto x1=quelr(l1,r1),x2=quelr(l2,r2);
	return 1ll*x1.first*pw1[l2-l1]%p1==x2.first&&
		   1ll*x1.second*pw2[l2-l1]%p2==x2.second;
}

inline void upd(int p)
{
	add(p+1);
	add(p+(m-1)+1);
}

inline bool cmp(int l,int r,int x)
{
	return cmp(l+1,r+1,l+x+1,r+x+1);
}

void doit(int l,int r,int x,vector<int> &vec)
{
	if(l==r)
	{
		if(res[l]) vec.push_back((l+x)%(m-1));
		return;
	}
	int mid=l+r>>1;
	if(!cmp(l,mid,x)) doit(l,mid,x,vec);
	if(!cmp(mid+1,r,x)) doit(mid+1,r,x,vec);
}

inline void slove()
{
	cin>>m>>n;
	gg=getg();
	int gpw=1;
	for(int i=0;i<m-1;i++) gln[gpw]=i,gpw=1ll*gpw*gg%m;
	for(int i=0;i<m-1;i++) res[i]=false;
	vector<int> vec;
	bool f0=false,ff=true;
	for(int i=1;i<=n;i++)
	{
		int op,x;
		cin>>op>>x;
		if(op==0) ff=false;
		if(x==0)
		{
			f0=true;
			continue;
		}
		if(op==0) res[gln[x]]=1;
		else vec.push_back(gln[x]);
	}
	if(ff)
	{
		cout<<m-1<<"\n";
		return;
	}
	for(int i=1;i<=m*2;i++) tr1[i]=tr2[i]=0;
	for(int i=0;i<m-1;i++) if(res[i]) upd(i);
	// for(int i=0;i<m-1;i++) cout<<res[i];
	// cout<<'\n';
	for(int x:vec)
	{
		vector<int> pos;
		// cout<<x<<":\n";
		doit(0,m-2,x,pos);
		for(int i:pos) if(!res[i]) res[i]=true,upd(i);
		// for(int i=0;i<m-1;i++) cout<<res[i];
		// cout<<'\n';
	}
	int cnt=f0;
	for(int i=0;i<m-1;i++) cnt+=res[i];
	cout<<m-cnt<<'\n';
}

int main()
{
	pw1[0]=pw2[0]=1;
	for(int i=1;i<=S-3;i++) pw1[i]=1ll*pw1[i-1]*bse%p1;
	for(int i=1;i<=S-3;i++) pw2[i]=1ll*pw2[i-1]*bse%p2;
	freopen("operation.in","r",stdin);
	freopen("operation.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T-->0) slove();
	return 0;
}
/*
找原根
然后就变成循环卷积的exp了
找原根可以暴力枚举然后判断
并不是exp
是百度之星分治
是副公主的背包
考办
循环卷积版
不幸
兰了
分治
*/