[POJ2888]?Magic Bracelet

題目描述

簡要題意：給圓上個點染色，顏色有種，其中對顏色不能相鄰，循環(huán)同構(gòu)，多組數(shù)據(jù)，詢問染色方案數(shù)。

?

Solution

大概就是一道挺顯然的Burnside題（一般染色，循環(huán)同構(gòu)都醬紫做）。

對于一個圓上的循環(huán)同構(gòu)，顯然有個置換，用Burnside引理求解答案：

所以我們可以枚舉置換中的循環(huán)個數(shù)，令??? 為不考慮循環(huán)同構(gòu)時，個點種顏色，滿足所有限制的方案數(shù)，最后

現(xiàn)在的問題轉(zhuǎn)化為，如何求出??，這是一個經(jīng)典問題，可以解決。

令?為線段上個點，第個點的顏色為，滿足其他所有限制的方案數(shù)。

?

這樣的是??，直接矩陣乘法優(yōu)化成???。

最后的時間復(fù)雜度大概是——??。（實測需要卡常，實際速度和POJ測評機有關(guān)）

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=9973; const int MAXN=1000005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int flag[MAXN],phi[MAXN],prime[MAXN],pnum=0,n,m,k; int Phi(int x) {int cnt=x;if (x<=1e6) return phi[x];for (int i=1;prime[i]*prime[i]<=x;i++)if (!(x%prime[i])){cnt=cnt-cnt/prime[i];while (!(x%prime[i])) x/=prime[i];}return (x>1)?cnt-cnt/x:cnt; } void Init_Prime(int n) {flag[1]=phi[1]=1; for (int i=2;i<=n;i++){if (!flag[i]) prime[++pnum]=i,phi[i]=i-1;for (int j=1;j<=pnum&&prime[j]*i<=n;j++){flag[prime[j]*i]=1;if (!(i%prime[j])) { phi[prime[j]*i]=phi[i]*prime[j]; break; }phi[prime[j]*i]=phi[i]*phi[prime[j]];}} } int upd(int x,int y){ return x+y>=mods?x+y-mods:x+y; } struct Matrix {int n,A[10][10];Matrix(int n1=0) {n=n1;memset(A,0,sizeof A); }void Init() { memset(A,0,sizeof A); }void init() { for(int i=0;i<n;i++) A[i][i]=1; }Matrix operator * (const Matrix &b){Matrix ans(n);for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) ans.A[i][k]=upd(ans.A[i][k],A[i][j]*b.A[j][k]%mods);return ans;}Matrix operator ^ (const ll &b) {Matrix ret(n),x=*this; ret.init();for (ll y=b;y;y>>=1) {if (y&1) ret=ret*x;x=x*x;}return ret;}void print(){for (int i=0;i<n;i++){for (int j=0;j<n;j++) cout<<setw(4)<<A[i][j];cout<<endl;}cout<<endl;} } f,g; int getans(int x) {g=f^x;ll ans=0;for (int i=0;i<m;i++) ans+=g.A[i][i];return ans; } int solve(int x,int y) {if (y==0) return 1;int q=solve(x,y>>1);return (y&1)?1ll*q*q%mods*x%mods:1ll*q*q%mods; } int main() {Init_Prime(1000000);cout<<Phi(1000000000)<<endl;int Case=read();while (Case--){n=read(),m=read(),k=read();f.n=m;for (int i=0;i<m;i++)for (int j=0;j<m;j++) f.A[i][j]=1;for (int i=1;i<=k;i++) {int x=read()-1,y=read()-1;f.A[x][y]=0;f.A[y][x]=0;}ll ans=0;for (int i=1;i*i<=n;i++)if (n%i==0){ans=upd(ans,1ll*Phi(n/i)*getans(i)%mods);if (i*i!=n) ans=upd(ans,1ll*Phi(i)*getans(n/i)%mods); // cout<<ans<<endl;}printf("%d\n",1ll*ans*solve(n,mods-2)%mods);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的[POJ2888] Magic Bracelet的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。