傳送門

題意：

相鄰珠子不能相同，旋轉(zhuǎn)等價。$n$個珠子$k$中顏色，求方案數(shù)

---

?

首先中間珠子$k$種選擇，$k--$
如果沒有相鄰不同的限制，就和$POJ\ 2154$一樣了
$|C(f)|=k^{\#(f)}$
但是有了相鄰不同的限制，每種循環(huán)的顏色就不能任意選擇了
旋轉(zhuǎn)等價循環(huán)個數(shù)是$gcd(n,i)$，同一個循環(huán)的元素相差$i$步
容易得到只要滿足長度$gcd(n,i)$的一段相鄰顏色不同整個環(huán)就不同了，因為這樣的一段正好每個循環(huán)有一個元素
考慮$DP$，$f[i]$表示$i$個元素組成的環(huán)染色方案數(shù)
$f[i]=(k-2)*f[i-1]+(k-1)*f[i-2]$
因為這時候$i-1$是可以和$1$相同的，那樣$i$有$k-1$種選擇，所以加上后面的一塊
顯然可以用矩陣快速冪
計算的時候使用和和$POJ\ 2154$同樣的技巧
最后的式子為：
$\frac{k}{n}\sum\limits_{d \mid n}{f(d)*\phi(\frac{n}ze8trgl8bvbq)},\ d \neq 1$

?

注意：$Candy?$把矩陣的構(gòu)造函數(shù)里加上了每個矩陣都初始化為單位矩陣，認為這樣就不用在做矩陣快速冪前初始化了。

然后就被坑慘了......矩陣乘法里還需要零矩陣啊啊啊啊啊啊啊?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+5,P=1e9+7; typedef long long ll; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}return x*f; } int n; ll k; int p[N]; bool notp[N]; void sieve(int n){for(int i=2;i<=n;i++){if(!notp[i]) p[++p[0]]=i;for(int j=1;j<=p[0]&&i*p[j]<=n;j++){notp[i*p[j]]=1;if(i%p[j]==0) break;}} } inline int phi(int n){int re=n,m=sqrt(n);for(int i=1;i<=p[0]&&p[i]<=m&&p[i]<=n;i++) if(n%p[i]==0){re=re/p[i]*(p[i]-1);while(n%p[i]==0) n/=p[i];}if(n>1) re=re/n*(n-1);return re%P; } struct Matrix{ll a[2][2];ll* operator [](int x){return a[x];}Matrix(){a[0][0]=a[1][1]=a[0][1]=a[1][0]=0;}void ini(){a[0][0]=a[1][1]=1;} }a,b; Matrix operator *(Matrix a,Matrix b){Matrix c;for(int k=0;k<2;k++)for(int i=0;i<2;i++) if(a[i][k])for(int j=0;j<2;j++) if(b[k][j])(c[i][j]+=a[i][k]*b[k][j])%=P;return c; } Matrix operator ^(Matrix a,int b){Matrix re;re.ini();for(;b;b>>=1,a=a*a)if(b&1) re=re*a;return re; } ll F[5]; ll f(int x){if(x<=3) return F[x];Matrix re=a^(x-3);re=re*b;return re[0][0]; } inline void mod(int &x){if(x>=P) x-=P;} inline ll Pow(ll a,int b){ll re=1;for(;b;b>>=1,a=a*a%P)if(b&1) re=re*a%P;return re; } inline ll Inv(ll a){return Pow(a,P-2);} void solve(){int m=sqrt(n),ans=0;for(int i=1;i<=m;i++) if(n%i==0){if(i!=1) mod(ans+= f(i)*phi(n/i)%P);if(i*i!=n) mod(ans+= f(n/i)*phi(i)%P);}printf("%lld\n",ans*Inv(n)%P*(k+1)%P); } int main(){freopen("in","r",stdin);sieve(32000);while(scanf("%d%lld",&n,&k)!=EOF){k--;F[1]=k;F[2]=k*(k-1)%P;F[3]=k*(k-1)%P*(k-2)%P;a[0][0]=k-2; a[0][1]=k-1;a[1][0]=1; a[1][1]=0;b[0][0]=F[3];b[0][1]=0;b[1][0]=F[2];b[1][1]=0;solve();} }

?

總結(jié)

以上是生活随笔為你收集整理的HDU 2865 Birthday Toy [Polya 矩阵乘法]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。