P1446 [HNOI2008]Cards

題意：

有n張牌，染三種顏色，每種顏色規定數目，給出m種不同的洗牌方法。兩種染色方法相同當且僅當其中一種可以通過任意的洗牌法（即可以使用多種洗牌法，而每種方法可以使用多次）洗成另一種。
求對P取模的結果

題解：

參考文章
置換群，Polya引理和burnside引理（等價類計數問題）
題目中說：輸入數據保證任意多次洗牌都可用這m種洗牌法種的一種代替。這句話是burnside引理使用的理由，這句話保證了置換群的大小只會是(m+1)種(這個1指的是自己映射自己)，否則置換群大小不能保證是(m+1)。
因為染色存在數量限制，所以不能用Polya定理
根據Burnside定理：等價類的個數 = 每個置換中不動元的個數和 ?置換群的大小
現在要找不動元的個數和，那么就要把置換的每個循環節都染上相同的顏色，看有多少方案
每個置換都有若干個循環，根據所給的置換求出循環節數，考慮用dp轉移來求出每個循環節染上相同的顏色，求每種顏色的總和符合題目要求的方案總數
對于每個置換，單獨考慮每個循環染什么顏色，可以通過背包的方式來求。f[i][j][k]表示三種顏色分別用了i，j，k的方案，每個循環看作一個物品，物品的重量作為循環元素的個數。
答案就是不動元的個數(f[r][b][g])除以總置換數

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=100; ll n,R,G,B,m; ll mod; ll a[maxn]; ll sz[maxn]; ll dp[maxn][maxn][maxn]; ll ans; ll cnt; ll vis[maxn]; ll poww(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; } ll solve(){memset(vis,0,sizeof(vis));cnt=0;for(int i=1;i<=n;i++){if(vis[i])continue;int x=i;int len=0;while(!vis[x]){len++;vis[x]=1;x=a[x];}sz[++cnt]=len;}memset(dp,0,sizeof(dp)),dp[0][0][0]=1;for(int t=1;t<=cnt;t++) //背包 for(int i=R;i>=0;i--)for(int j=G;j>=0;j--)for(int k=B;k>=0;k--){if(i>=sz[t]) (dp[i][j][k]+=dp[i-sz[t]][j][k])%=mod;if(j>=sz[t]) (dp[i][j][k]+=dp[i][j-sz[t]][k])%=mod;if(k>=sz[t]) (dp[i][j][k]+=dp[i][j][k-sz[t]])%=mod;}return dp[R][G][B]; } int main() {//rd_test();read(R,G,B,m,mod);n=R+G+B;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){read(a[j]);} ans=(ans+solve())%mod; }for(int i=1;i<=n;i++)a[i]=i;ans=(ans+solve())%mod;cout<<ans*poww(m+1,mod-2)%mod<<endl;//Time_test(); }

總結

以上是生活随笔為你收集整理的P1446 [HNOI2008]Cards的全部內容，希望文章能夠幫你解決所遇到的問題。

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