题目描述:
$T$组询问,每次给出$n$,$m$与$k$组关系,要求用$m$种颜色染长为$n$的手链,且$k$对颜色不能相邻。
题解
这是个坑,我认为它是对的但是$poj$不认为它是对的。
$T$的很惨。
代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MOD = 9973; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } int fastpow(int x,int y) { int ret = 1; while(y) { if(y&1)ret=ret*x%MOD; x=x*x%MOD; y>>=1; } return ret; } int T,n,m,k,pri[500050],phi[500050],cnt; bool vis[500050]; void init() { phi[1] = 1; for(int i=2;i<=500000;i++) { if(!vis[i]) { phi[i] = i-1; pri[++cnt] = i; } for(int j=1;i*pri[j]<=500000;j++) { vis[i*pri[j]] = 1; if(i%pri[j]) { phi[i*pri[j]] = phi[i]*(pri[j]-1); }else { phi[i*pri[j]] = phi[i]*pri[j]; break; } } } } struct mt { int s[12][12]; mt(){memset(s,0,sizeof(s));} mt operator * (const mt&a) { mt ret; for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) for(int k=1;k<=10;k++) ret.s[i][j]=(ret.s[i][j]+s[i][k]*a.s[k][j]%MOD)%MOD; return ret; } }x0; mt operator ^ (mt x,int y) { mt ret = x; y--; while(y) { if(y&1)ret=ret*x; x=x*x; y>>=1; } return ret; } int get_phi(int x) { if(x<=500000) return phi[x]; int ret = 1; for(int j=1,i=pri[j];i*i<=x;j++,i=pri[j])if(x%i==0) { ret*=(i-1); x/=i; while(x%i==0) { ret*=i; x/=i; } } if(x!=1) ret*=(x-1); return ret; } int inv(int x) { x%=MOD; return fastpow(x,MOD-2); } int fc(int x) { mt now = x0^x; int ret = 0; for(int i=1;i<=m;i++) ret = (ret+now.s[i][i])%MOD; return ret%MOD; } int main() { init(); read(T); while(T--) { read(n),read(m),read(k); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) x0.s[i][j]=1; for(int x,y,i=1;i<=k;i++) { read(x),read(y); x0.s[x][y]=x0.s[y][x]=0; } int ans = 0; for(int i=1;i*i<=n;i++)if(n%i==0) { int tmp = get_phi(n/i); tmp = tmp * fc(i); ans = (ans+tmp)%MOD; if(i*i==n)continue; tmp = get_phi(i); tmp = tmp * fc(n/i); ans = (ans+tmp)%MOD; } printf("%d\n",ans*inv(n)%MOD); } return 0; }