题解：P4640 [BJWC2008] 王之财宝

· · 题解

题解：P4640 [BJWC2008] 王之财宝

前言

计数模拟赛中 T1 放了这个，场切了。感觉比较简单，也用不着生成函数。

分析

注意到有一些特殊的只能选不超过 a_i 个。这个不超过，感觉很难计数，然后再观查到 m\leq 15 大概就能知道是容斥了。

那么答案一定是 \sum_S (-1)^{|S|}\times f(S)。f(S) 就表示 S 集合内的元素选择大于 a_i 其他的数随便选的方案数。那么显然就可以变成了另外一个简单的问题。

令 sum=\sum_{i\in S} a_i+1，那么现在要求容量为 V-sum 的背包，有 n 个互不相同的数，询问背包中数的方案数。

于是你可以进行一个打表：

1 0 0 0 ...
1 1 1 1 ...
1 2 3 4 ...
1 3 6 10 ...

设每行从 1 开始，表示数字个数，每列从 0 开始，表示背包被占用的容量。你发现这个单个点的值是什么呢？就是网格图计数的值。

那么再对一行的前缀求和，就可以化简成最后的式子 \binom{n+V}{n}。

所以 f(S)=\binom{n+V-sum}{n}。

这样就做完了。

CODE

#include <bits/stdc++.h>
#define int long long
#define ppc __builtin_popcount
using namespace std;
constexpr int M=20;
int n,m,V,mod;
int a[M];
int ans;
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
constexpr int N=1e6+5;
int fs[N],inv[N];
void init()
{
    fs[0]=inv[0]=1;
    for(int i=1;i<mod;i++)
        fs[i]=1ll*fs[i-1]*i%mod,inv[i]=qpow(fs[i],mod-2);
}
int C(int n,int m)
{
    if(n<0 || m<0 || n<m)return 0;
    return 1ll*fs[n]*inv[m]%mod*inv[n-m]%mod;
}
int lucas(int n,int m)
{
    if(n<0 || m<0 || n-m<0)
        return 0;
    if(m==0)return 1;
    return 1ll*lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
signed main()
{
    // freopen("sign.in","r",stdin);
    // freopen("sign.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>V>>mod;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    init();
    for(int S=0;S<(1<<m);S++)
    {
        int fl=(ppc(S)&1)?(mod-1):1;
        int sm=0;
        for(int i=1;i<=m;i++)
            if(S>>(i-1)&1)
                sm+=a[i]+1;
        if(sm>V)continue;
        int k=V-sm;
        (ans+=1ll*fl*lucas(n+k,n)%mod)%=mod;
    }
    cout<<ans;
    return 0;
}

TIPS

注意开 long long。