诚聘网站开发人员,免费网站生成器,四川省建行网站,互联网销售公司[POJ2888] Magic Bracelet
题目描述
简要题意#xff1a;给圆上个点染色#xff0c;颜色有种#xff0c;其中对颜色不能相邻#xff0c;循环同构#xff0c;多组数据#xff0c;询问染色方案数。 Solution
大概就是一道挺显然的Burnside题#xff08;一般染色#x…[POJ2888] Magic Bracelet
题目描述
简要题意给圆上个点染色颜色有种其中对颜色不能相邻循环同构多组数据询问染色方案数。 Solution
大概就是一道挺显然的Burnside题一般染色循环同构都酱紫做。
对于一个圆上的循环同构显然有个置换用Burnside引理求解答案 所以我们可以枚举置换中的循环个数令 为不考虑循环同构时个点种颜色满足所有限制的方案数最后 现在的问题转化为如何求出 这是一个经典问题可以解决。
令 为线段上个点第个点的颜色为满足其他所有限制的方案数。 这样的是 直接矩阵乘法优化成 。
最后的时间复杂度大概是—— 。实测需要卡常实际速度和POJ测评机有关
#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;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods9973;
const int MAXN1000005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int flag[MAXN],phi[MAXN],prime[MAXN],pnum0,n,m,k;
int Phi(int x)
{int cntx;if (x1e6) return phi[x];for (int i1;prime[i]*prime[i]x;i)if (!(x%prime[i])){cntcnt-cnt/prime[i];while (!(x%prime[i])) x/prime[i];}return (x1)?cnt-cnt/x:cnt;
}
void Init_Prime(int n)
{flag[1]phi[1]1; for (int i2;in;i){if (!flag[i]) prime[pnum]i,phi[i]i-1;for (int j1;jpnumprime[j]*in;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 xymods?xy-mods:xy; }
struct Matrix
{int n,A[10][10];Matrix(int n10) {nn1;memset(A,0,sizeof A); }void Init() { memset(A,0,sizeof A); }void init() { for(int i0;in;i) A[i][i]1; }Matrix operator * (const Matrix b){Matrix ans(n);for(int i0;in;i) for(int j0;jn;j) for(int k0;kn;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 yb;y;y1) {if (y1) retret*x;xx*x;}return ret;}void print(){for (int i0;in;i){for (int j0;jn;j) coutsetw(4)A[i][j];coutendl;}coutendl;}
} f,g;
int getans(int x)
{gf^x;ll ans0;for (int i0;im;i) ansg.A[i][i];return ans;
}
int solve(int x,int y)
{if (y0) return 1;int qsolve(x,y1);return (y1)?1ll*q*q%mods*x%mods:1ll*q*q%mods;
}
int main()
{Init_Prime(1000000);coutPhi(1000000000)endl;int Caseread();while (Case--){nread(),mread(),kread();f.nm;for (int i0;im;i)for (int j0;jm;j) f.A[i][j]1;for (int i1;ik;i) {int xread()-1,yread()-1;f.A[x][y]0;f.A[y][x]0;}ll ans0;for (int i1;i*in;i)if (n%i0){ansupd(ans,1ll*Phi(n/i)*getans(i)%mods);if (i*i!n) ansupd(ans,1ll*Phi(i)*getans(n/i)%mods);
// coutansendl;}printf(%d\n,1ll*ans*solve(n,mods-2)%mods);}return 0;
}
