polya定理，环形涂色-白红宇

polya定理，环形涂色

阅读量：5899 次

发布时间：2019-06-19

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

环形涂色裸题

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
            7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 #include
                
                  12 #include
                 
                   13 #include
                  
                    14 #include
                   
                     15 #include
                    
                      16 #include
                     
                       17 #define A first 18 #define B second 19 #define mp make_pair 20 #define pb push_back 21 #define pw(x) (1ll << (x)) 22 #define sz(x) ((int)(x).size()) 23 #define all(x) (x).begin(),(x).end() 24 #define rep(i,l,r) for(int i=(l);i<(r);i++) 25 #define per(i,r,l) for(int i=(r);i>=(l);i--) 26 #define FOR(i,l,r) for(int i=(l);i<=(r);i++) 27 #define eps 1e-9 28 #define PIE acos(-1) 29 #define cl(a,b) memset(a,b,sizeof(a)) 30 #define fastio ios::sync_with_stdio(false);cin.tie(0); 31 #define lson l , mid , ls 32 #define rson mid + 1 , r , rs 33 #define ls (rt<<1) 34 #define rs (ls|1) 35 #define INF 0x3f3f3f3f 36 #define lowbit(x) (x&(-x)) 37 #define sqr(a) a*a 38 #define ll long long 39 #define ull unsigned long long 40 #define vi vector
                      
                        41 #define pii pair
                       
                         42 #define dd(x) cout << #x << " = " << (x) << ", " 43 #define de(x) cout << #x << " = " << (x) << "\n" 44 #define endl "\n" 45 using namespace std; 46 const int mod=1e9+7; 47 int n,m,k,c; 48 const int maxn=500+7; 49 int vis[maxn],lab[maxn]; 50 //********************************** 51 ll qpow(ll a,ll b) 52 { 53 ll ans=1; 54 while(b){ 55 if(b&1)ans=ans*a%mod; 56 a=a*a%mod; 57 b>>=1; 58 } 59 return ans; 60 } 61 ll getloop() 62 { 63 cl(vis,0); 64 int cnt=0; 65 FOR(i,1,n){ 66 if(vis[i])continue; 67 cnt++; 68 int j=i; 69 do{ 70 vis[j]=1; 71 j=lab[j]; 72 }while(!vis[j]); 73 } 74 return cnt; 75 } 76 void work() 77 { 78 if(!n){ 79 puts("0\n");return ; 80 } 81 ll ans=0; 82 rep(i,0,n){ 83 FOR(j,1,n)lab[j]=(j+i)%n+1; 84 ans+=qpow(k,getloop()); 85 // FOR(j,1,n/2)swap(lab[j],lab[n+1-j]);ans+=qpow(k,getloop()); 86 ans%=mod; 87 // de(ans); 88 } 89 ans=ans*qpow(n,mod-2)%mod; 90 // ans/=n; 91 // ans=ans*c%mod; 92 cout<
                        
                         <
                         
                          >m>>n>>c;101 k=qpow(c,m*m);102 // de(k);103 work();104 return 0;105 }