原帖

我的思路

下面是我改过的代码

//sum s1~st∈[0,1](prod [si=1](1+pi*(k-1))*prod pi|r(n/t)/gcd(r(n/t),t)((pi^2-1)*pi^(4ai-2)+1)*prod pi|gcd(r(n/t),t)(pi^2(pi^2-1)(pi^4(ai-1)-1)/(pi^4-1)+1))
//o(i,si)=(pi^4(ai-si)-1)/(pi^4-1)
//o(i,si)=1+pi^4+...+pi^4(ai-si-1)
//vi=pi^2(pi^2-1)o(i,1)+1
//yi=(pi^2-1)*pi^(4ai-2)+1
//wi=1+pi*(k-1)
//sum s|r(n)(prod pi|s(wi)*prod pi|r(n/t)/gcd(r(n/t),t)(yi)*prod pi|gcd(r(n/t),t)(vi))
#include<bits/stdc++.h>
using namespace std;
typedef __int128_t li;
typedef long long ll;
#define gc getchar()
inline li rd(){li x=0;char c=gc;while(c<48||c>57) c=gc;while(c>47&&c<58) x=(x<<3)+(x<<1)+(c^48),c=gc;return x;}
li T,k,m,t,p[19],a[19],u[19],v[19],y[19],w[19],ans;//π(67)=18,2*3*5*...*67*71>1e24
inline li q(li a,li b){return !b?1:b==1?a:b&1?q(a*a%m,b>>1)*a%m:q(a*a%m,b>>1);}
inline li o(li p,int a){li r=0;for(int i=0;i<=a;++i) r=(r*p+1)%m;return r;}
inline void dfs(int x,li e){
	if(x==t){
		ans+=e;
		return;
	}
	dfs(x+1,e*y[x]%m);//sx=0
	if(a[x]==1) dfs(x+1,e*w[x]%m);//sx=1
	else dfs(x+1,e*w[x]%m*v[x]%m);
}
int main(){
	T=rd();
	while(T--){
		k=rd(),m=rd(),t=rd();
		for(int i=0;i<t;++i) p[i]=rd(),a[i]=rd();
		for(int i=0;i<t;++i){
			w[i]=(1+p[i]*(k-1))%m;
			v[i]=(p[i]%m*p[i]%m*((p[i]%m*p[i]%m+m-1)%m)%m*o(p[i]%m*(p[i]%m)%m*(p[i]%m)%m*(p[i]%m)%m,a[i]-2)+1)%m;
			y[i]=(((p[i]%m*p[i]%m+m-1)%m)%m*q(p[i]%m,4*a[i]-2)+1)%m;
		}
		ans=0,dfs(0,1);
		cout<<(int)(ans%m)<<"\n";
	}
	return 0;
}