題目鏈接

https://www.luogu.org/problem/P4708

題解

看上去Luogu P4706-4709是Sdchr神仙出的一場比賽，一道水題和三道很有趣的題終于全過了紀念QAQ(然而后三道都看了題解)
以及為啥這題AC代碼幾乎全是打表。。

前置題目: BZOJ1488 求\(n\)個點無標號無向圖個數。(歡迎閱讀 https://www.cnblogs.com/suncongbo/p/11295453.html )
沒做過的建議先去做一下那題。

這道題依然是枚舉拆分數，然后現在的問題就是給定一些長度的輪換求有多少個點度均為偶數的圖滿足經過這些輪換作用后依然不變。
首先一個性質是，同一輪換內的所有點度數相同。(顯然)
考慮輪換內部的邊，假設這個輪換長度為\(L=2s+1\), 那么則有\(s\)種不同的邊組，每一種邊組會使得輪換內所有點度數\(+2\); 若輪換長度為\(2s\), 則有\(s\)種不同的邊組，其中\((s-1)\)種(除了對角的之外)使得所有點度數\(+2\), \(1\)種使得所有點度數\(+1\). 度數\(+2\)不改變奇偶性的顯然可以不考慮，直接答案乘以\(2\).
再考慮輪換之間的邊，假設兩輪換長度分別為\(a,b\)則有\(\gcd(a,b)\)種邊組，每種邊組內包含\(\text{lcm}(a,b)\)條邊，會給\(a\)中的點度數\(+\frac{\text{lcm}(a,b)}{a}\)，給\(b\)中的點度數\(+\frac{\text{lcm(a,b)}}{b}\). 若二者都為偶數，答案乘以\(2^{\gcd(a,b)}\). 若二者中恰有一個為奇數，則相當于有\(\gcd(a,b)\)次機會給奇數的那個輪換改變奇偶性。若二者都是奇數，則相當于有\(\gcd(a,b)\)次機會給兩個輪換同時改變奇偶性。

于是問題轉化為: 有一張新圖(新圖里的點代表一個輪換)，初始點權都為\(0\), 對每個點有\(c_i\)次機會改變它的奇偶性，對每條邊有\(d_i\)次機會同時改變兩端點的奇偶性。求有多少種方案使得最終所有點的點權為\(0\).
這個結論是，對于每一種改變點權總次數為偶數次的方案，都存在\(2^{\sum d_i-cnt+1}\)種邊操作方案(\(cnt\)為點數)與之對應。
感性理解，改變點權如果是奇數次顯然不行，偶數次的話可以構建一棵DFS樹，非樹邊任意操作之后樹邊按照自下而上操作總能操作完。
注意這里官方題解寫的是錯的！官方題解直接寫成\(2^{\sum d_i}\)坑了我一晚上……
那么答案就是\(2^{\sum c_i-1}\times 2^{\sum d_i-cnt+1}\).
問題解決。

時間復雜度同BZOJ 1488.

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 50; const int P = 998244353; llong fact[N*N*N+3],finv[N*N*N+3],inv[N*N*N+3],pw2[N*N*N+3]; int gcd[N+3][N+3];int GCD(int x,int y) {return y==0 ? x : GCD(y,x%y);}llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; }void initmath(int n) {fact[0] = 1ll; for(int i=1; i<=n; i++) fact[i] = fact[i-1]*i%P;finv[n] = quickpow(fact[n],P-2); for(int i=n-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;for(int i=1; i<=n; i++) inv[i] = finv[i]*fact[i-1]%P;pw2[0] = 1ll; for(int i=1; i<=n; i++) pw2[i] = pw2[i-1]*2ll%P; }int a[N+3],num[N+3]; int uf[N+3]; int c[N+3]; int n,cnt; llong ans;int findfa(int u) {int i = u;while(u!=uf[u]) {u = uf[u];}while(u!=uf[i]){int j = uf[i]; uf[i] = u; i = j;}return u; }void unionfa(int u,int v) {int x = findfa(u),y = findfa(v);if(x!=y) {uf[x] = y;} }llong calc() {for(int i=1; i<=cnt; i++) uf[i] = i,c[i] = 0;llong ret = fact[n];for(int i=1; i<=cnt; i++) {ret = ret*inv[a[i]]%P;}for(int i=1; i<=n; i++) {ret = ret*finv[num[i]]%P;}llong retp = 0ll;for(int i=1; i<=cnt; i++){for(int j=i+1; j<=cnt; j++){int g = gcd[a[i]][a[j]],lcm = a[i]*a[j]/g;int ci = lcm/a[i],cj = lcm/a[j];if((ci&1)==(cj&1)){retp += g;if(ci&1) {unionfa(i,j);}}}}for(int i=1; i<=cnt; i++){for(int j=i+1; j<=cnt; j++){int g = gcd[a[i]][a[j]],lcm = a[i]*a[j]/g;int ci = lcm/a[i],cj = lcm/a[j];int x = findfa(i),y = findfa(j);if((ci&1)!=(cj&1)){if(ci&1) {c[x]+=g;}else if(cj&1) {c[y]+=g;}}}}for(int i=1; i<=cnt; i++){int x = findfa(i);retp += ((a[i]-1)>>1);if(!(a[i]&1)) {c[x]++;}}retp -= cnt;for(int i=1; i<=cnt; i++) {if(uf[i]==i) retp++;}for(int i=1; i<=cnt; i++){if(uf[i]==i && c[i]>0){retp += c[i]-1;}}ret = ret*pw2[retp]%P;return ret; }void dfs(int sum) {if(sum==0){ans = (ans+calc())%P;}for(int i=a[cnt]; i<=sum; i++){cnt++; a[cnt] = i; num[i]++;dfs(sum-i);num[i]--; a[cnt] = 0; cnt--;} }int main() {initmath(N*N*N);for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) gcd[i][j] = GCD(i,j);scanf("%d",&n);a[0] = 1; dfs(n);ans = ans*finv[n]%P;printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Luogu P4708 画画 (Burnside引理、组合计数)的全部內容，希望文章能夠幫你解決所遇到的問題。

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