专栏首页数据结构与算法BZOJ2339: [HNOI2011]卡农(dp 容斥)

BZOJ2339: [HNOI2011]卡农(dp 容斥)

题意

从$1 - n$中任意选择一些数,选$m$次构成$m$个集合

保证:

  • 集合不为空
  • 任意两个集合不相同
  • 集合内各个元素xor起来等于0

Sol

神仙题Orz

我看到两种做法,一种是洛谷题解上的直接dp,另一种是yyb的神仙转化。

其实都差不多吧。。

我简单说一下,设$f[i]$表示选了$i$个集合,满足条件的方案

直接转移会非常麻烦,因为要同时限制集合不同 xor不为0,我们又不知道集合的具体元素。

因此我们考虑容斥。

为了方便考虑,我们先不考虑每个元素的位置,最后再除以$M!$

因为xor的性质,若我们已经知道了前$i - 1$个元素,那么我们这时候选什么是确定的。

先确定出前$i - 1$个数,方案数为$A_{2^n - 1}^{i - 1}$,

考虑若此时选了一个空的集合,那我们要保证前$i - 1$个集合满足条件,方案数为$f[i - 1]$

若选了重复的集合(这是最难理清楚的),剩下的$i - 2$个元素很定要满足条件,方案数为$f[i - 2]$,然后我们枚举一个集合,方案数为$2^{n} - (i - 2)$,这样看似就可以了。但是我们在递推的时候是没有考虑顺序的,因此另一个元素有$i - 1$种取值,因此还要乘$i - 1$

得到递推式

f[i]=A_{2^n-1}^{i-1}-f[i-1]-(i-1)\times f[i-2]\times(2^n-1-(i-2))

// luogu-judger-enable-o2
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
#define LL long long 
//#define int long long
using namespace std;
const int MAXN = 3 * 1e6;
const LL mod = 1e8 + 7;//fuck
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 N, M;
LL ifac[MAXN], fac[MAXN], f[MAXN], A[MAXN];
LL fastpow(LL a, LL p) {
    LL base = 1;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
main() {
    N = read(); M = read(); LL base = fastpow(2, N) % mod;
    fac[0] = A[0] = 1; for(int i = 1; i <= M; i++) fac[i] = 1ll * i * fac[i - 1] % mod;
    ifac[M] = fastpow(fac[M], mod - 2);
    for(int i = 1; i <= M; i++) A[i] = 1ll * A[i - 1] * (base - i + mod) % mod;
    f[0] = 1; f[1] = 0; 
    for(int i = 2; i <= M; i++) f[i] = ((A[i - 1] - f[i - 1] + mod) % mod - 1ll * f[i - 2] * (i - 1) % mod * (base - i + 1) % mod + mod) % mod;
    printf("%lld", f[M] * ifac[M] % mod);
    return 0;
}
/*
99999 99999
*/

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ4766: 文艺计算姬

    Description "奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺 术细胞。普通计算机能计算一个带...

    attack
  • BZOJ1008: [HNOI2008]越狱(组合数)

    监狱有连续编号为 1…N1…N 的 NN 个房间,每个房间关押一个犯人,有 MM 种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱...

    attack
  • 洛谷P2044 [NOI2012]随机数生成器

    题目描述 栋栋最近迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列...

    attack
  • HDU----(4291)A Short problem(快速矩阵幂)

    A Short problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

    Gxjun
  • 欧里几德及扩展欧里几德算法

    欧几里德算法 欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。 基本算法:设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd...

    Angel_Kitty
  • STC单片机没法下载程序解决办法汇总

    上一篇推文里已经对STC单片机下载程序过程做了简述,今天的问题是解决有部分小伙伴没法下载程序的问题的,在解答这个问题之前,小编觉得有必要对STC_ISP 软件的...

    单片机技术宅
  • E3 2017第二发:做不了最强王者的你,何不另寻它欢

    VRPinea
  • springboot研究:springboot自带监控actuator

    springboot中自带监控工具actuator,在对监控要求不高的情况下,使用actuator就可以满足系统监控要求了。使用actuator,需要添加依赖

    jinjunzhu
  • 从零开始学C++之模板(二):类模板、Stack的类模板实现(自定义链栈方式,自定义数组方式)

    一、类模板 类模板:将类定义中的数据类型参数化 类模板实际上是函数模板的推广,可以用相同的类模板来组建任意类型的对象集合 (一)、类模板的定义 templ...

    s1mba
  • C语言经典习题100例(三)11-15

    实现思路: 从第1个月起,兔子对数分别为1、1、2、3、5、8、13、21…,显然是斐波拉契数列。

    cutercorley

扫码关注云+社区

领取腾讯云代金券