Luogu3214 HNOI2011 卡农组合、DP

客官°小女子只卖身不卖艺 2021-11-26 09:40 191阅读 0赞

[传送门][Link 1]

--------------------

火题qwq

我们需要求的是满足元素个数为\\(M\\)、元素取值范围为\\(\[1,2^n-1\]\\)、元素异或和为\\(0\\)的集合的数量。

首先我们可以计算元素有序的方案数（即计算满足这些条件的序列的数量），然后除以\\(M!\\)。

设\\(dp\_i\\)表示大小为\\(i\\)的满足条件的序列个数

由"元素异或和为\\(0\\)"可以知道，如果确定了其中\\(i-1\\)个向量，第\\(i\\)个向量就可以知道了，选择\\(i-1\\)个向量的方案数是\\(A\_\{2^n-1\}^\{i-1\}\\)

然后考虑非法情况：当前元素为\\(0\\)时，前\\(i-1\\)个向量异或和为\\(0\\)，所以要减掉\\(dp\_\{i-1\}\\)；存在两个向量相同时，其他的向量的异或和就为\\(0\\)，因为选择这个向量的方案数是\\(i-1\\)，选择这两个向量的取值的方案数是\\(2^n-1-(i-2)\\)，所以这里需要减掉\\(dp\_\{i-2\} \\times (i-1) \\times (2^n-1-(i-2))\\)

那么DP方程就是\\(dp\_i = A\_\{2^n-1\}^\{i-1\} - dp\_\{i-1\} - dp\_\{i-2\} \\times (i-1) \\times (2^n-1-(i-2))\\)。

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cstring>
    #include<iomanip>
    #include<cmath>
    #include<cassert>
    //This code is written by Itst
    using namespace std;
    
    const int MOD = 1e8 + 7;
    int dp[1000003] , N , M;
    
    int poww(long long a , int b){
        int times = 1;
        while(b){
            if(b & 1) times = times * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return times;
    }
    
    signed main(){
        #ifndef ONLINE_JUDGE
        freopen("in","r",stdin);
        //freopen("out","w",stdout);
        #endif
        cin >> N >> M;
        int down = 1 , tms = 1 , tmp = 1 , jc = 1;
        for(int i = 1 ; i <= N ; ++i)
            down = (down << 1) % MOD;
        --down; tms = tmp = down;
        dp[0] = 1; dp[1] = 0;
        for(int i = 2 ; i <= M ; ++i){
            jc = 1ll * jc * i % MOD;
            dp[i] = (2ll * MOD + tms - dp[i - 1] - 1ll * dp[i - 2] * (i - 1) % MOD * (tmp - i + 2) % MOD) % MOD;
            tms = 1ll * tms * (--down) % MOD;
        }
        cout << 1ll * dp[M] * poww(jc , MOD - 2) % MOD;
        return 0;
    }

转载于:https://www.cnblogs.com/Itst/p/11032195.html

[Link 1]: https://www.luogu.org/problemnew/show/P3214