UVA11255 Necklace Burnside、组合-白红宇

UVA11255 Necklace Burnside、组合

阅读量：5227 次

发布时间：2019-06-14

本文共 4930 字，大约阅读时间需要 16 分钟。

因为有每种颜色个数的限制，所以不能使用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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   //This code is written by Itstusing 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; else if(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; else if(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);#endif jc[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; else ans += (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

你可能感兴趣的文章