uva 11255Necklace

【题目】

Once upon a time, three girls|Winnie, Grace and Bonnie|owned a large number of pearls. However, each of them only had a single color of pearls. Winnie had white pearls, Grace had grey pearls and Bonnie had black pearls. One day, after a long discussion, they decided to make necklaces using the pearls. They are interested in knowing how many patterns can be formed using a certain number of pearls of each color, and have asked you to solve this problem for them. Note that rotating or ipping over a necklace cannot produce a different kind of necklace. i.e. The following gure shows three equivalent necklaces. The following gure shows all possible necklaces formed by 3 white pearls, 2 grey pearls and 1 black pearl.

Input The input begins with an integer N ( 2500) which indicates the number of test cases followed. Each of the following test cases consists of three non-negative integers a, b, c, where 3 a + b + c 40. Output For each test case, print out the number of different necklaces that formed by a white pearls, b grey pearls and c black pearls in a single line. Sample Input 2 3 2 1 2 2 2 Sample Output 6 11

---

【分析】

运用组合数学的知识，根据a+b+c的奇偶性大力讨论。

---

【代码】

//UVA 11255 Necklace #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 40 #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=45; int n,a,b,c; int C[mxn][mxn]; inline int gcd(int x,int y) {return x%y==0?y:gcd(y,x%y);} int main() { int i,j,T; fo(i,0,N) C[i][0]=1; fo(i,1,N) fo(j,1,i) C[i][j]=C[i-1][j-1]+C[i-1][j]; scanf("%d",&T); while(T--) { ll ans=0; scanf("%d%d%d",&a,&b,&c); n=a+b+c; fo(i,1,n) { int x=n/gcd(n,i); //循环节大小 if(a%x==0 && b%x==0 && c%x==0) ans+=C[n/x][a/x]*C[n/x-a/x][b/x]; } if((n&1) && (a&1)+(b&1)+(c&1)==1) ans+=C[n/2][a/2]*C[n/2-a/2][b/2]; if(!(n&1)) { if((a&1)+(b&1)+(c&1)==0) ans+=C[n/2][a/2]*C[n/2-a/2][b/2]*n; else if((a&1)+(b&1)+(c&1)==2) ans+=C[n/2-1][a/2]*C[n/2-1-a/2][b/2]*n; } printf("%lld\n",ans/n/2); } return 0; }