bzoj 1004 [HNOI2008]Cards && poj 2409 Let it Bead ——置换群

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1004

   http://poj.org/problem?id=2409

学习材料:https://www.cnblogs.com/nietzsche-oier/p/6883880.html

     https://files-cdn.cnblogs.com/files/HocRiser/Burnside.pdf

bzoj 1004:这道题注意考虑单位元的那个置换。

然后用 polya 定理即可。不动点个数是 dp 出来的,以保证合法。 dp 时注意 res -= tot 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=,M=;
int n,m,mod,s0,s1,s2,a[N],f[N],dp[][M][M][M],ans;
bool vis[N];
void upd(int &x){x>=mod?x-=mod:;}
int pw(int x,int k)
{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}
int solve()
{
memset(vis,,sizeof vis);
memset(dp[],,sizeof dp[]); dp[][s0][s1][s2]=;
bool fx=; int res=n;
for(int i=;i<=n;i++)
if(!vis[i])
{
int tot=,cr=i;
while(!vis[cr])
{
tot++; vis[cr]=;
cr=a[cr];
}
bool tf=!fx; memset(dp[tf],,sizeof dp[tf]);
for(int x0=s0;x0>=;x0--)
for(int x1=s1;x1>=;x1--)
{
int x2=res-x0-x1,d;
if(x2>s2||!(d=dp[fx][x0][x1][x2]))continue;
if(x0>=tot)dp[tf][x0-tot][x1][x2]+=d,upd(dp[tf][x0-tot][x1][x2]);
if(x1>=tot)dp[tf][x0][x1-tot][x2]+=d,upd(dp[tf][x0][x1-tot][x2]);
if(x2>=tot)dp[tf][x0][x1][x2-tot]+=d,upd(dp[tf][x0][x1][x2-tot]);
}
fx=tf; res-=tot;
}
return dp[fx][][][];
}
int main()
{
scanf("%d%d%d%d%d",&s0,&s1,&s2,&m,&mod);
n=s0+s1+s2;
for(int j=;j<=n;j++)a[j]=j;
ans+=solve(); upd(ans);
for(int i=;i<=m;i++)
{
for(int j=,d;j<=n;j++)scanf("%d",&d),a[d]=j;
ans+=solve(); upd(ans);
}
ans=(ll)ans*pw(m+,mod-)%mod;
printf("%d\n",ans);
return ;
}

poj 2409:polya模板。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=;
int n,m; ll ans;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll pw(ll x,int k)
{ll ret=;while(k){if(k&)ret*=x;x*=x;k>>=;}return ret;}
int main()
{
while()
{
scanf("%d%d",&m,&n);if(!n&&!m)return ;
ans=;
for(int i=;i<=n;i++)ans+=pw(m,gcd(n,i));
if(n&) ans+=n*pw(m,n+>>);
else ans+=(n*pw(m,n>>)>>)+(n*pw(m,(n>>)+)>>);
printf("%lld\n",ans/(n<<));
}
return ;
}
上一篇:[BZOJ 1004] [HNOI2008] Cards 【Burnside引理 + DP】


下一篇:win10上部署Hadoop-2.7.3——非Cygwin、非虚拟机