猜数游戏

黑板上写有 \(n\) 个互不相等且都小于 \(p\) 的正整数 \(a_1, a_2, \cdots, a_n\)。小 J 想用这些数字和小 M 玩一个猜数游戏。

游戏规则十分简单：游戏开始时，小 J 会从这些数字中随机选择若干个让小 M 来猜，而小 M 则可以通过若干次询问来确定小 J 选择了哪些数字。

每一次询问的模式如下：小 M 可以任意指定一个数字 \(a_k\)，若它是小 J 所选择的数字之一，则小 J 会告诉小 M 他所选择的数字中所有能表示成 \((a_k)^m \bmod p\) 的数，其中 \(m\) 是任意正整数，\(\bmod\) 表示求二者做带余除法后的余数。反之，若 \(a_k\) 没有被小 J 选中，则小 J 只会告诉小 M \(a_k\) 没有被选中。

游戏会在小 M 确定小 J 所选中的所有数字后立刻结束。

例如，若 \(n=4\)，\(p=7\)，数字 \(\{a_n\}\) 按下标顺序依次为 \(\{1, 3, 4, 6\}\)，小 J 选定的数字为 \(\{1, 4, 6\}\)，一种可能的游戏进行的过程（并非是最优过程）如下：

\(3\) 次询问后小 J 所选出的所有数都已被小 M 确定，游戏结束。

小 M 还有作业没有写完，因此他需要对游戏进行的时间进行评估。他想知道为了使游戏结束，他所需要做出询问的最小次数的期望 \(S\) 是多少。

为了避免精度误差，你需要输出答案乘 \((2^n - 1)\) 后模 \(998244353\) 的余数。在本题中，你可以认为小 J 每次在选数时会在集合 \(\{a_1, a_2, \cdots, a_n\}\) 的全部非空子集中等概率地选择一个，在这个前提下可以证明 \((2^n - 1) \times S\) 一定是一个整数。

题解

暂时是LOJ和UOJ第一名还行。

int pow(int a,int b,int mod){
	int ans=1;
	for(;b;b>>=1,a=(int64)a*a%mod)
		if(b&1) ans=(int64)ans*a%mod;
	return ans;
}
int order(int a,int p,int phi,CO vector<int>&d){
	int o=phi;
	for(int x:d)while(o%x==0 and pow(a,o/x,p)==1) o/=x;
	return o;
}

unordered_map<int,int> cnt,deg;
vector<pair<int,int> > vec;

int main(){
	int n=read<int>(),p=read<int>();
	
	int q=p,k=1;
	for(int i=2;i*i<=p;++i)if(p%i==0){
		q=i,k=0;
		for(int x=p;x%i==0;x/=i) ++k;
		break;
	}
	
	int phi=q-1;
	for(int i=2;i<=k;++i) phi*=q;
	
	vector<int> d;
	if(k>1) d.push_back(q);
	int x=q-1;
	for(int i=2;i*i<=x;++i)if(x%i==0){
		d.push_back(i);
		while(x%i==0) x/=i;
	}
	if(x>1) d.push_back(x);
	
	for(int i=1;i<=n;++i){
		int a=read<int>();
		if(a%q!=0){
			int o=order(a,p,phi,d);
			++cnt[phi/o];
		}
		else{
			deg[a]=0;
			int e=0;
			for(int x=a;x%q==0;x/=q) ++e;
			vec.push_back({e,a});
		}
	}
	int ans=0;
	for(int i=1;i*i<=phi;++i)if(phi%i==0){
		int sum=-cnt[i];
		for(int j=1;j*j<=i;++j)if(i%j==0){
			sum+=cnt[j];
			if(i/j==j) continue;
			sum+=cnt[i/j];
		}
		ans=add(ans,mul(fpow(i2,sum),1+mod-fpow(i2,cnt[i])));
		if(phi/i==i) continue;
		sum=-cnt[phi/i];
		for(int j=1;j*j<=phi/i;++j)if(phi/i%j==0){
			sum+=cnt[j];
			if(phi/i/j==j) continue;
			sum+=cnt[phi/i/j];
		}
		ans=add(ans,mul(fpow(i2,sum),1+mod-fpow(i2,cnt[phi/i])));
	}
	sort(vec.begin(),vec.end());
	for(CO pair<int,int>&a:vec){
		ans=add(ans,mul(fpow(i2,deg[a.second]),i2));
		for(int x=a.second;x!=0;x=(int64)x*a.second%p)
			if(deg.count(x)) ++deg[x];
	}
	ans=mul(ans,fpow(2,n));
	write(ans,‘\n‘);
	return 0;
}

WC2020 猜数游戏

原文：https://www.cnblogs.com/autoint/p/13449343.html