absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-21] poj 3128
[破碎的状态] [-16] 100503 B

[破碎的状态] [-19] BZOJ 1004

absi2011 posted @ Jul 03, 2016 12:37:36 PM in 网上比赛 with tags bzoj 数学题 瞎搞 小高考 , 570 阅读

这一题是Burnside引理的复习..

这一题根据Burnside..

除了要手动写个dp..求Burnside的东西..

思考了半天发现数据范围这么小为啥不dp..

PS:这是第三次过这题了..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int sr,sb,sg;
int dp[25][25][25];
int n;
int modo;
int a[65];
void trys_dp(int n,int y)
{
    int r,b,g;
    for (r=0;r<=n;r++)
    {
        if (r>sr) continue;
        for (b=0;r+b<=n;b++)
        {
            if (b>sb) continue;
            g=n-r-b;
            if (g>sg) continue;
            if (r>=y) dp[r][b][g]+=dp[r-y][b][g];
            if (b>=y) dp[r][b][g]+=dp[r][b-y][g];
            if (g>=y) dp[r][b][g]+=dp[r][b][g-y];
            dp[r][b][g]%=modo;
        }
    }
}
int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=t*t%modo;
    if (y%2==1) t=t*x%modo;
    return t;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d%d%d",&sr,&sb,&sg);
    n=sr+sb+sg;
    int m;
    scanf("%d",&m);
    scanf("%d",&modo);
    int i;
    int ans=0;
    for (i=0;i<=m;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            scanf("%d",&a[j]);
            a[j]--;
            if (i==m) a[j]=j;
        }
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
        int now=0;
        for (j=0;j<n;j++)
        {
            if (a[j]!=-1)
            {
                int x=j;
                int sum=0;
                for (;;)
                {
                    int temp=a[x];
                    a[x]=-1;
                    x=temp;
                    sum++;
                    if (x==j) break;
                }
                now+=sum;
                trys_dp(now,sum);
            }
        }
        ans+=dp[sr][sb][sg];
    }
    printf("%d\n",ans*power(m+1,modo-2)%modo);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter