YACS 2023年8月月赛甲组 T1 不定方程题解

Xy_top / 2023-08-25 / 原文

题目链接

背包

首先想到背包，$f_{i,j}$ 为前 $i$ 个数和为 $j$ 的方案数，但时间复杂度为 $O(n\cdot 20000000)$，会炸。

如果背包跑的时候只跑到当前的 $sum$，就能得到常数的优化，但仍然不足以通过。

插板法

先来考虑一个更简单的问题，每个 $a_i$ 只有下界为 $1$ 该怎么做，不妨想象有 $m$ 个花盆，需要在其中插 $n-1$ 个板子将它们分成 $n$ 个部分。

这样就是答案了吧，所以没有上界时的答案为 $C(m-1,n-1)$。

上界相同的解法

如果对于每个 $a_i$ 除了有下界 $1$，还有一个共同的上界 $k$，那又该如何解决呢？显然能够想到容斥。

答案就是只有下界的方案数-有一个越界剩下只有下界的方案数+有两个越界剩下只有下界的方案数-有三个越界剩下只有下界的方案数......

其中有 $m$ 个越界的方案数就是 $C(n,m)*C(sum-i*k,n-1)$。

上界不同的解法

直接进行容斥原理 $dfs$ 即可，但 $m$ 很大，有 $1e9$，算 $C$ 会超时。

但容易发现即使 $a_i$ 都取到 $1000000$，$n$ 个加起来也只有 $2e7$，所以 $m>2e7$ 时无解，剩下预处理即可。

代码：

#include<iostream>
#define int long long
using namespace std;
int n,m;
int a[21],fac[20000001];
const int mod=1000000007;
int q_pow(int x,int y){
    if(y==0)return 1;
    if(y&1)return x*q_pow(x*x%mod,y>>1)%mod;
    return q_pow(x*x%mod,y>>1);
}
int inv(int x){return q_pow(x,mod-2);}
int C(int n,int m){
    if(n<m)return 0;
    if(n==m)return 1;
    return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;
}
int dfs(int x,int r){
    //x：目前是第几个
    //r：目前还有几个 1 没分配
    if(x==n+1)return C(r-1,n-1);
    return (dfs(x+1,r)-dfs(x+1,r-a[x])+mod)%mod;
}
signed main(){
    fac[0]=1;
    for(int i=1;i<=20000000;i++)fac[i]=fac[i-1]*i%mod;
    cin>>n>>m;
    if(m>20000000){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<dfs(1,m);
    return 0;
}