M. 810975 题解(容斥)

题目链接

题目思路

题目可以转化为有\(n-m+1\)个数，每个数\(0\leq x_i \leq k\) 并且这些数的和为\(m\) 且数的最大值为\(k\)

那么可以再转化为

有\(n-m+1\)个数，每个数\(0\leq x_i \leq k\) 并且这些数的和为\(m\)

减去有\(n-m+1\)个数，每个数\(0\leq x_i \leq k-1\) 并且这些数的和为\(m\)

就是这个问题

代码

#include
#define fi first
#define se second
#define debug cout<<"I AM HERE"<>1;
    }
    return ans;
}
void init(int n){
    fac[0]=finv[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    finv[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=1;i--){
        finv[i]=finv[i+1]*(i+1)%mod;
    }
}
ll c(ll a,ll b){
    if(a