題目大意：一串項鏈由n個戒指組成，對于每個戒指，一共有M個點，R種顏色，且旋轉后相同的戒指是相同的，然后一串項鏈又由N個戒指組成，同時要滿足相鄰的兩個戒指不能相同，這串項鏈上某個位置插入了一個特殊的東西，且如果特殊的東西插入的地方不同，即使戒指都是相同的，這兩串項鏈也是不同的，求一共有多少不同的愛之項鏈。

思路：首先可以求出一共有多少種不同的戒指，又由于有那個特殊的東西，相當于這串項鏈即使旋轉后相同，但特殊的東西插入的位置也肯定是不同的，因此即不考慮旋轉，只考慮相鄰位置不同的愛之項鏈的方案數。

令ans表示有多少種不同的戒指。

然后這樣就可以運用容斥原理。對于第i個戒指和第i+1個戒指相同，可以看成第i個限制，然后第n個限制即第n個戒指和第1個限制不同，那么即要求滿足所有限制的方案數。令Si為滿足第i個限制的方案數的集合，那么即求S1~Sn的交，也就是其補集的并，那么就是總方案數減去所有不滿足任意一個限制數加上所有不滿足任意二個限制數......

然后這個式子是怎樣的呢，首先總方案數顯然就是ans^n，然后不滿足任意一個限制數即有兩個相鄰的相同，可以看成一條邊連接的兩個點相同，就是C(n,1)*ans^(n-1)，以此類推，然后可以得到：sigma(0<=i<=n,(-1)^i*C(n,i)*ans^(n-i))，然后發現這就是二項式定理，就可以得到(ans-1)^n， 但真的就是這樣嗎？當i=n時，就會有一個Bug，用公式算得的答案是(-1)^n，然而n個限制均不滿足時的情況即所有顏色都一樣，有ans種，因此還要加上(n&1?1-m:m-1)才行。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define p 3214567 8 #define maxn 200020 9 10 int m,r,tot; 11 int prime[maxn],phi[maxn]; 12 bool isprime[maxn]; 13 long long n; 14 15 int power(int a,long long k){ 16 if (k==0) return 1; 17 if (k==1) return a%p; 18 int x=power(a,k/2),ans=1ll*x*x%p; 19 if (k&1) ans=1ll*a*ans%p; 20 return ans; 21 } 22 23 int fphi(int x){ 24 int ans=x; 25 for (int i=2;i*i<=x;i++) 26 if (x%i==0){ 27 ans=ans-ans/i; 28 while (x%i==0) x/=i; 29 } 30 if (x!=1) ans=ans-ans/x; 31 return ans; 32 } 33 34 int main(){ 35 scanf("%lld%d%d",&n,&m,&r);tot=0,memset(isprime,1,sizeof(isprime)),phi[1]=1; 36 for (int i=2;i<maxn;i++){ 37 if (isprime[i]) prime[++tot]=i,phi[i]=i-1; 38 for (int j=1;j<=tot && i*prime[j]<maxn;j++){ 39 isprime[i*prime[j]]=0; 40 if (i%prime[j]==0){ 41 phi[i*prime[j]]=phi[i]*prime[j]; 42 break; 43 } 44 phi[i*prime[j]]=phi[i]*(prime[j]-1); 45 } 46 } 47 int ans=0; 48 for (int i=1;i*i<=m;i++) 49 if (m%i==0){ 50 ans=(ans+1ll*power(r,i)*fphi(m/i)%p)%p; 51 if (i*i!=m) ans=(ans+1ll*power(r,m/i)*phi[i]%p)%p; 52 } 53 ans=1LL*ans*power(m,p-2)%p; 54 int t=(1ll*power(ans-1,n)+(n&1?1-ans:ans-1))%p; 55 printf("%d\n",(t+p)%p); 56 return 0; 57 } View Code

轉載于:https://www.cnblogs.com/DUXT/p/5951747.html

總結

以上是生活随笔為你收集整理的bzoj4330：JSOI2012 爱之项链的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。