传送门戳我 https://www.luogu.com.cn/problem/P1680
首先将 n 减去所有的 Ci, 于是是原问题转换为: n 个相同的球放入 m 个不同盒子里, 不能为空, 求方案数.
根据插空法: n 个球, 放到 m 个箱子里去不能为空, 也就是有 m-1 块板子放在 n-1 个空隙之间
那么组合数求解也就是 C(n-1,m-1)
除法求余有误差所以先求分母的逆元, 转化为分子 * 逆元 %mod 的形式
在模为素数 p 的情况下, 有费马小定理
a^(p-1)=1(mod p)
那么 a^(p-2)=a^-1(mod p)
也就是说 a 的逆元为 a^(p-2)
那么快速幂一下求逆元就好了.
- #include <bits/stdc++.h>
- using namespace std;
- const int mod=1000000007;
- const int maxn=1000009;
- typedef long long ll;
- int n,m;
- ll fc[maxn+10];
- ll quickpow(ll a,ll n)
- {
- ll ans=1;
- while(n)
- {
- if(n&1) ans=ans*a%mod;
- a=a*a%mod;
- n>>=1;
- }
- return ans;
- }
- ll C(int n,int k)
- {
- ll fm=fc[k]*fc[n-k]%mod;// 求 b 的逆元
- // 因为 a/b%mod, 除法取模会出现问题, 所以要求逆元
- return fc[n]*quickpow(fm,mod-2)%mod;
- }
- int main()
- {
- fc[0]=1;
- for(int i=1;i<=maxn;i++)
- fc[i]=fc[i-1]*i%mod;
- cin>>n>>m;
- for(int i=1;i<=m;i++)
- {
- ll l;cin>>l;
- n-=l;
- }
- //n 个苹果, 放到 m 个箱子里去不能为空
- // 也就是有 m-1 块板子放在 n-1 个空隙之间
- cout<<C(n-1,m-1);
- }
来源: http://www.bubuko.com/infodetail-3496871.html