app与网站的区别是什么,电商网站 投诉,logo免费下载网站,做网站的装饰标语P1446 [HNOI2008]Cards
题意#xff1a;
有n张牌#xff0c;染三种颜色#xff0c;每种颜色规定数目#xff0c;给出m种不同的洗牌方法。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法#xff08;即可以使用多种洗牌法#xff0c;而每种方法可以使用多次…P1446 [HNOI2008]Cards
题意
有n张牌染三种颜色每种颜色规定数目给出m种不同的洗牌方法。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法即可以使用多种洗牌法而每种方法可以使用多次洗成另一种。 求对P取模的结果
题解
参考文章 置换群Polya引理和burnside引理等价类计数问题 题目中说输入数据保证任意多次洗牌都可用这m种洗牌法种的一种代替。这句话是burnside引理使用的理由这句话保证了置换群的大小只会是(m1)种(这个1指的是自己映射自己)否则置换群大小不能保证是(m1)。 因为染色存在数量限制所以不能用Polya定理 根据Burnside定理等价类的个数 每个置换中不动元的个数和 ➗置换群的大小 现在要找不动元的个数和那么就要把置换的每个循环节都染上相同的颜色看有多少方案 每个置换都有若干个循环根据所给的置换求出循环节数考虑用dp转移来求出每个循环节染上相同的颜色求每种颜色的总和符合题目要求的方案总数 对于每个置换单独考虑每个循环染什么颜色可以通过背包的方式来求。f[i][j][k]表示三种颜色分别用了ijk的方案每个循环看作一个物品物品的重量作为循环元素的个数。 答案就是不动元的个数(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 pairint, 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 maxn100;
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 ans1;while(b){if(b1)ansans*a%mod;aa*a%mod;b1;}return ans%mod;
}
ll solve(){memset(vis,0,sizeof(vis));cnt0;for(int i1;in;i){if(vis[i])continue;int xi;int len0;while(!vis[x]){len;vis[x]1;xa[x];}sz[cnt]len;}memset(dp,0,sizeof(dp)),dp[0][0][0]1;for(int t1;tcnt;t) //背包 for(int iR;i0;i--)for(int jG;j0;j--)for(int kB;k0;k--){if(isz[t]) (dp[i][j][k]dp[i-sz[t]][j][k])%mod;if(jsz[t]) (dp[i][j][k]dp[i][j-sz[t]][k])%mod;if(ksz[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);nRGB;for(int i1;im;i){for(int j1;jn;j){read(a[j]);} ans(anssolve())%mod; }for(int i1;in;i)a[i]i;ans(anssolve())%mod;coutans*poww(m1,mod-2)%modendl;//Time_test();
}
