BZOJ1004: [HNOI2008]Cards(Burnside引理 背包dp)

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 4255  Solved: 2582

[Submit][Status][Discuss]

Description

  小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有 多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方 案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案. 两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗 成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).

Input

  第一行输入 5 个整数:Sr,Sb,Sg,m,p(m<=60,m+1<p<100)。n=Sr+Sb+Sg。 接下来 m 行,每行描述一种洗牌法,每行有 n 个用空格隔开的整数 X1X2...Xn,恰为 1 到 n 的一个排列, 表示使用这种洗牌法,第 i位变为原来的 Xi位的牌。输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代 替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

Output

  不同染法除以P的余数

Sample Input

1 1 1 2 7 2 3 1 3 1 2

Sample Output

2

HINT

  有2 种本质上不同的染色法RGB 和RBG,使用洗牌法231 一次可得GBR 和BGR,使用洗牌法312 一次 可得BRG  和GRB。 100%数据满足 Max{Sr,Sb,Sg}<=20。

Source

这题非常的妙啊。

第一眼看过去应该是P♂lya定理,但是考虑到P♂lya定理是用颜色数做底数计算的,而此题有颜色数的限制,

所以我们考虑它最原始的版本—Burnside引理

这题置换的个数直接给出了($M$)

因此我们只需要求出每个置换中不动点的方案再乘上$M$Z在模$P$意义下的逆元就行了

考虑如何求每个置换中的不动点

联想P♂lya定理。我们在每个循环节中都必须要放同样的颜色,这题也是一样的,只不过多了个数的限制

那么我们直接把个数的限制当做状态dp就行了

设$f[i][a][b]$表示前$i$个循环节,用了$a$个红颜色,$b$个蓝颜色,$c$个黄颜色

转移的时候判断当前放的个数时候大于循环节长度,背包转移

注意最初的状态也算一种方案

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long  
const int MAXN = 1e5 + 10;
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int Sr, Sb, Sg, N, M, mod, change[MAXN];
int f[61][21][21], len[101], vis[101], num = 0; // f[i][j][k]前i个循环节,用了j个红,k个蓝, i - j - k个绿 len[i]第i个循环节有几个元素 
int F(int *a) {
    memset(f, 0, sizeof(f));
    memset(len, 0, sizeof(len));
    memset(vis, 0, sizeof(vis));
    num = 0;
    for(int i = 1; i <= N; i++) {
        if(!vis[i]) {
            int cur = i; num++;
            while(!vis[i]) len[num]++, vis[i] = 1,  i = a[i];
        }
    }
    f[0][0][0] = 1;
    for(int i = 1; i <= num; i++) {
        for(int a = 0; a <= Sr; a++) {
            for(int b = 0; b <= Sb; b++) {
                int c = i - a - b, sum = 0;
                if(c < 0 || c > Sg) continue;
                if(a >= len[i]) sum = (sum + f[i - 1][a - len[i]][b] ) % mod;
                if(b >= len[i]) sum = (sum + f[i - 1][a][b - len[i]] ) % mod;
                if(c >= len[i]) sum = (sum + f[i - 1][a][b]) % mod;
                f[i][a][b] = sum % mod;
            }
        }
    }
    return f[num][Sr][Sb] % mod;
}
int inv(int a, int p, int mod) {
    int base = 1;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
main() {
    Sr = read(); Sb = read(); Sg = read(); M = read(), mod = read();
    N = Sr + Sb + Sg;
    int ans = 0;
    for(int i = 1; i <= M; i++) {
        for(int j = 1; j <= N; j++) change[j] = read();
        ans += F(change);
    }
    for(int i = 1; i <= N; i++) change[i] = i;
    ans += F(change);
    printf("%d", ans * inv(M + 1, mod - 2, mod) % mod);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(下)

在上一篇里,我们学习了“自主角色”的一些基本行为:寻找(seek)、避开(flee)、到达(arrive)、追捕(pursue)、躲避(evade)、漫游(wa...

290100
来自专栏数据结构与算法

P2658 汽车拉力比赛

题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

28580
来自专栏潇涧技术专栏

Problem: Delete Number Problem

这题可以使用贪心策略,每次从高位向低位数,删除高位比低位数字小的那位上的数字,直到删除了k位之后,得到的数字肯定是最大值。

9820
来自专栏数据结构与算法

清北集训Day1T3 LYK loves jumping(期望DP)

题目描述 LYK在玩一个魔法游戏,叫做跳跃魔法。 有n个点,每个点有两个属性hi和ti,表示初始高度,和下降高度。也就是说,它初始时高度为hi,一旦LYK踩在这...

29350
来自专栏Pulsar-V

用不动点法和牛顿迭代法求解函数根-Julia

29820
来自专栏小樱的经验随笔

POJ 1741 Tree(树的点分治,入门题)

Tree Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 21357 ...

33260
来自专栏PPV课数据科学社区

数据挖掘知识脉络与资源整理(十)–箱线图

? ? 箱线图的简介 箱形图(Box-plot)又称为盒须图、盒式图或箱线图,是一种用作显示一组数据分散情况资料的统计图。因形状如箱子而得名。在各种领域也经常...

35380
来自专栏ACM算法日常

当七夕遇上算法竞赛

  七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去T...

15920
来自专栏ml

由判断三一点是否在三角形内部而引发的思考.....

判断一个点是否在三角形里面(包括边界上),这个问题对于许多初学者来说,可谓是一头雾水,如何判断呢? 假如有四个点A(x0,y0),B(x1,y1),C(x2,y...

31380
来自专栏PHP在线

PHP CodeBase: 生成N个不重复的随机数

有25幅作品拿去投票,一次投票需要选16幅,单个作品一次投票只能选择一次。前面有个程序员捅了漏子,忘了把投票入库,有200个用户产生的投票序列为空。那么你会如何...

34950

扫码关注云+社区

领取腾讯云代金券