当前位置:网站首页>P1446 [hnoi2008] cards (Burnside theorem + DP count)
P1446 [hnoi2008] cards (Burnside theorem + DP count)
2022-04-23 09:43:00 【Zimba_】
The question :
To dye a deck of cards , Dyeing S r S_{r} Sr Zhang Hong , S b S_{b} Sb Zhang Lan Lan , S g S_{g} Sg Green Zhang . Now it is given m m m A shuffle ( substitution ), When a deck of cards can pass through this m m m A shuffle ( You can use a variety of washing methods , Each can be used multiple times ) When shuffled into another deck , Say the two sets of cards are the same . Ask how many different decks can be dyed .
m a x { S r , S b , S g } ≤ 20 , m ≤ 60 max\{S_{r},S_{b},S_{g}\}\leq20,m\leq60 max{
Sr,Sb,Sg}≤20,m≤60
Ideas :
Obviously B u r n s i d e Burnside Burnside The application of the theorem ( Whether it can be used is another matter ).
The formula :
N ( G , C ) = 1 ∣ G ∣ ∑ f ∈ G C ( f ) N(G,C)=\frac{1}{|G|}\sum_{f\in G}C(f) N(G,C)=∣G∣1f∈G∑C(f) Simple Introduce this formula , G G G It's a permutation group , C C C It's a coloring set , C ( f ) C(f) C(f) It's replacement f f f In the shading set C C C The number of fixed points under .
As for the requirements of permutation group , Is not very good .
The words here , G G G Inside is , Unit replacement and m m m Shuffle replacement . A coloring set is all the different permutations of three colors that satisfy the number of colors .
We consider counting the number of fixed points of a permutation .
And then you'll find out , A coloring that does not move under a displacement , Currently, only if the color in each loop section is the same . therefore , For each permutation , Find its cyclic section , And then use d p dp dp Just count .
Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int Sr,Sb,Sg,m,p;
int n;
int a[105];
int flag[105];
int dp[30][30][30];
int getC()
{
memset(flag,0,sizeof(flag));
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int i=1;i<=n;i++)if(!flag[i])
{
int now=i;
flag[now]=1;
int num=1;
while(!flag[a[now]])
{
num++;
now=a[now];
flag[now]=1;
}
for(int r=Sr;r>=0;r--)
{
for(int b=Sb;b>=0;b--)
{
for(int g=Sg;g>=0;g--)
{
if(r>=num)dp[r][b][g]=(dp[r][b][g]+dp[r-num][b][g])%p;
if(b>=num)dp[r][b][g]=(dp[r][b][g]+dp[r][b-num][g])%p;
if(g>=num)dp[r][b][g]=(dp[r][b][g]+dp[r][b][g-num])%p;
}
}
}
}
return dp[Sr][Sb][Sg];
}
int fpow(int a,int n,int p)
{
int sum=1,base=a;
while(n!=0)
{
if(n%2)sum=sum*base%p;
base=base*base%p;
n/=2;
}
return sum;
}
int main()
{
scanf("%d%d%d%d%d",&Sr,&Sb,&Sg,&m,&p);
n=Sr+Sb+Sg;
int ans=0;
for(int i=1;i<=n;i++)a[i]=i;
ans=(ans+getC())%p;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)scanf("%d",&a[j]);
ans=(ans+getC())%p;
}
printf("%d\n",ans*fpow(m+1,p-2,p)%p);
return 0;
}
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425107.html
边栏推荐
- Leetcode question bank 78 Subset (recursive C implementation)
- ABAP CDs view with association example
- 108. Convert an ordered array into a binary search tree
- How to render web pages
- SAP pi / PO function operation status monitoring and inspection
- 501. Mode in binary search tree
- AQS & reentrantlock implementation principle
- SAP RFC_ CVI_ EI_ INBOUND_ Main BP master data creation example (Demo customer only)
- 云身份过于宽松,为攻击者打开了大门
- Kernel PWN learning (3) -- ret2user & kernel ROP & qwb2018 core
猜你喜欢
Secrets in buffctf file 1
Applet error: cannot read property'currenttarget'of undefined
SAP 101K 411k inventory change
Kernel PWN learning (3) -- ret2user & kernel ROP & qwb2018 core
面试官:说几个PHP常用函数,幸好我面试之前看到了这篇文章
SAP pi / PO soap2proxy consumption external WS example
论文阅读《Integrity Monitoring Techniques for Vision Navigation Systems》——3背景
The sap export excel file opens and shows that the file format and extension of "XXX" do not match. The file may be damaged or unsafe. Do not open it unless you trust its source. Do you still want to
kernel-pwn学习(3)--ret2user&&kernel ROP&&QWB2018-core
MySQL of database -- Fundamentals
随机推荐
MySQL of database -- overview and installation
Installation of data cleaning ETL tool kettle
SAP ECC connecting SAP pi system configuration
STM32 and FreeRTOS stack parsing
亚马逊云科技入门资源中心,从0到1轻松上云
Kettle实验 (三)
理解作用域
SAP 101K 411k inventory change
SAP pi / PO soap2proxy consumption external WS example
Little girl walking
kernel-pwn学习(4)--Double Fetch&&0CTF2018-baby
Emuelec compilation summary
Kettle experiment
Kettle实验 转换案例
Creation of raid0 and RAID5 and Simulation of how RAID5 works
Random neurons and random depth of dropout Technology
Introduction to sap pi / PO login and basic functions
LeetCode 1611. The minimum number of operations to make an integer 0
JS scope, scope chain, global variables and local variables
Go language learning notes - structure | go language from scratch