VJ傳送門

---

因為有每種顏色個數的限制，所以不能使用Polya

考慮退一步，使用Burnside引理求解

回憶一下Burnside引理，它需要求的是置換群中每一個置換的不動點個數，也就是施加一次置換之后新狀態與原狀態相同的狀態個數。而施加一次置換之后狀態不變的充要條件是：對于這個置換中的每一個循環，循環中所有位置的顏色都相同。

為了敘述方便，約定\(f(i,j,k,l) = \frac{i!}{j!k!l!}\)

首先考慮旋轉。假設某一種旋轉置換使得\(i\)位置的珠子變到\(i+k\)位置\((k \in [1,N] , N = a+b+c)\)，不難知道這個置換是由\(gcd(N,k)\)個\(\frac{N}{gcd(N,k)}\)階循環構成的。

假設\(\frac{N}{gcd(N,k)} | a\ \&\&\ \frac{N}{gcd(N,k)} | b\ \&\&\ \frac{N}{gcd(N,k)} | c\)（如果這個條件不成立顯然沒有方案），那么這\(gcd(N,k)\)個循環中有\(\frac{a}{\frac{N}{gcd(N,k)}}\)個是全白色，\(\frac{b}{\frac{N}{gcd(N,k)}}\)個是全灰色，\(\frac{c}{\frac{N}{gcd(N,k)}}\)個是全黑色，這是一個本質不同的可重排列計數問題，染色方案有\(f(gcd(N,k) , \frac{a}{\frac{N}{gcd(N,k)}} ,\frac{b}{\frac{N}{gcd(N,k)}}, \frac{c}{\frac{N}{gcd(N,k)}})\)種

接著考慮翻轉。這里需要分類討論一下：

①\(2 \not\mid N\)，意味著所有的軸會且只會經過一個珠子。在這種情況下，總共有\(N\)種翻轉置換，每一個置換都是由\(1\)個\(1\)階循環和\(\frac{N-1}{2}\)個\(2\)階循環組成。枚舉這一個\(1\)階循環的顏色，那么不動點個數為\((f(\frac{N - 1}{2} , \frac{a - 1}{2} , \frac{b}{2} , \frac{c}{2}) + f(\frac{N - 1}{2} , \frac{a}{2} , \frac{b - 1}{2} , \frac{c}{2}) + f(\frac{N - 1}{2} , \frac{a}{2} , \frac{b}{2} , \frac{c - 1}{2}) ) \times N\)

②\(2 | N\)，意味著有\(\frac{N}{2}\)個軸不經過珠子，有\(\frac{N}{2}\)個對稱軸經過\(2\)個珠子，跟上面一樣枚舉\(1\)階循環的顏色計算答案，式子太長不想寫了留給讀者自行思考

還有這道題似乎要寫高精

#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<cctype> #include<algorithm> #include<cstring> #include<iomanip> #include<queue> #include<map> #include<set> #include<bitset> #include<stack> #include<vector> #include<cmath> //This code is written by Itst using namespace std;inline int read(){int a = 0;char c = getchar();bool f = 0;while(!isdigit(c) && c != EOF){if(c == '-')f = 1;c = getchar();}if(c == EOF)exit(0);while(isdigit(c)){a = a * 10 + c - 48;c = getchar();}return f ? -a : a; }struct Bignum{int a[107];int& operator [](int x){return a[x];}Bignum(int b = 0){memset(a , 0 , sizeof(a));a[0] = 0;while(b){a[++a[0]] = b % 10;b /= 10;}}Bignum operator =(int b){return *this = Bignum(b);}void input(){string s;cin >> s;a[0] = s.size();for(int i = 1 ; i <= a[0] ; ++i)a[i] = s[s.size() - i] - '0';}void output(){if(!a[0])putchar('0');for(int i = a[0] ; i ; --i)putchar(a[i] + '0');putchar('\n');}Bignum operator +(Bignum b){Bignum c;c[0] = max(a[0] , b[0]);for(int i = 1 ; i <= c[0] ; ++i)if((c[i] += a[i] + b[i]) >= 10){c[i] -= 10;++c[i + 1];}if(c[c[0] + 1])++c[0];return c;}Bignum operator +=(Bignum b){return *this = *this + b;}Bignum operator -(Bignum b){Bignum c;c[0] = max(a[0] , b[0]);for(int i = 1 ; i <= c[0] ; ++i)if((c[i] += a[i] - b[i]) < 0){c[i] += 10;--c[i + 1];}while(c[0] && !c[c[0]])--c[0];return c;}Bignum operator -=(Bignum b){return *this = *this - b;}Bignum operator *(Bignum b){if(!b[0])return b;Bignum c;c[0] = a[0] + b[0] - 1;for(int i = 1 ; i <= a[0] ; ++i)for(int j = 1 ; j <= b[0] ; ++j)c[i + j - 1] += a[i] * b[j];for(int i = 1 ; i <= c[0] ; ++i)if(c[i] >= 10){c[i + 1] += c[i] / 10;c[i] %= 10;if(i == c[0])++c[0];}while(c[0] && !c[c[0]])--c[0];return c;}Bignum operator *=(Bignum b){return *this = *this * b;}Bignum operator ^(int a){Bignum times(1) , b(*this);while(a){if(a & 1)times *= b;b *= b;a >>= 1;}return times;}bool operator >(Bignum b)const{if(a[0] > b[0])return 1;if(a[0] < b[0])return 0;for(int i = a[0] ; i ; --i)if(a[i] > b[i])return 1;elseif(a[i] < b[i])return 0;return 0;}bool operator >= (Bignum b){if(a[0] > b[0])return 1;if(a[0] < b[0])return 0;for(int i = a[0] ; i ; --i)if(a[i] > b[i])return 1;elseif(a[i] < b[i])return 0;return 1;}Bignum operator /(Bignum b){Bignum c , d = *this , e;c[0] = a[0] - b[0] + 1;for(int i = c[0] ; i ; --i){e = b * (Bignum(10) ^ (i - 1));for(int j = 1 ; j <= 10 ; ++j)if((e * j) > d){d -= e * (j - 1);c[i] = j - 1;break;}}while(c[0] && !c[c[0]])--c[0];return c;}Bignum operator /=(Bignum b){return *this = *this / b;}Bignum operator %(Bignum b){return *this - *this / b * b;}Bignum operator %=(Bignum b){return *this = *this % b;} }jc[41]; int a , b , c , N; Bignum ans;inline int gcd(int a , int b){int r = a % b;while(r){a = b;b = r;r = a % b;}return b; }inline Bignum calc(int x , int a , int b , int c){if(a % x || b % x || c % x || a < 0 || b < 0 || c < 0)return 0;int N = a + b + c;return jc[N / x] / jc[a / x] / jc[b / x] / jc[c / x]; }int main(){ #ifndef ONLINE_JUDGE//freopen("in","r",stdin);freopen("out","w",stdout); #endifjc[0] = 1;for(int i = 1 ; i <= 40 ; ++i)jc[i] = jc[i - 1] * i;for(int T = read() ; T ; --T){ans = 0;a = read();b = read();c = read();N = a + b + c;for(int i = 1 ; i <= N ; ++i)ans += calc(N / gcd(i , N) , a , b , c);if(N & 1)ans += (calc(2 , a - 1 , b , c) + calc(2 , a , b - 1 , c) + calc(2 , a , b , c - 1)) * N;elseans += (calc(2 , a , b , c) + calc(2 , a - 1 , b - 1 , c) + calc(2 , a - 1 , b , c - 1) + calc(2 , a , b - 1 , c - 1)) * N;ans = ans / (2 * N);ans.output();}return 0; }

轉載于:https://www.cnblogs.com/Itst/p/10340883.html

總結

以上是生活随笔為你收集整理的UVA11255 Necklace Burnside、组合的全部內容，希望文章能夠幫你解決所遇到的問題。

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