建设城市(city)：组合数，容斥原理

想模一大堆人呢。考场上AC的大仙。

估计没人想给这题好好写一个题解吧，因为它的确挺简单的。。。

但是它对我来说一点都不简单啊！！！

至少出题人用脚写题解的时候肯定认为这道题是送分题了

容斥,枚举至少有 i 个不满足条件,方案数为C(n,i)*C(m-i*k-1,n-1)。

对着题解发了半个小时的呆。我真的就是不会啊我有什么办法。

为啥就不重不漏了啊？为啥就最少了啊？为啥就容斥了啊？为啥我抄了这个式子才30分啊？

我估计没多少人会看这一篇所以废话有点多。

其实容斥原理不难想到，考场上我就想到了。

但是我的思路清奇了一波，我在想通过容斥计算出“恰好有i个城市不满足条件的方案数”

一共要求出n个，每次复杂度是n，总复杂度n²。

然后就滚去打暴力了。

然而为什么要把每一个都求出来啊！它们之间跟没就没有递推的依赖啊。

所以说就是脑子不行。

所以问题其实只是求解我刚才那个问题在i=0时的值，求解一次就好。

考场上想不到就算了，诚当是攒exp了。

那么考虑如何求解。

问题中的“恰好”让人感到有些拘束，那么就别恰好了，至少0个好吧？

那就水极了，相当与没有上界限制，问题就是m物分n人，每人至少1。

挡板法的裸题。是 $ C^{n-1}_{m-1} $ 啦。这个还是比较简单的。

至少0个的处理完了，那么至少1个的呢？

首先在所有城市里选出1个， $ C^1_n $ 。

然后是在剩下空余的建设队里，选择k个先分给你选定的那个城市，剩下的m-k个分给所有的这n个城市。

还是挡板法： $ C^{n-1}_{m-k-1} $

注意，你选定的那个城市也要继续参与分配，至少再被分到1个，否则它就是恰好k个而并非超过k个了。

至少2个呢？算的过程和含义都一样： $ C^2_n × C^{n-1}_{m-k*2-1} $

至少i个呢？$ C^i_n × C^{n-1}_{m-k*i-1} $

至此我们终于得到了题解里面的式子。（我早就在半道上迷路了）

接下来就可以容斥了。剩下的就是一个容斥的裸题了。

然而我连容斥奇加偶减都不会了。。。

对于至少有1的情况中，里面会包括至少有2的情况。。。

啊。。。然后用二项式定理证它就是个容斥了嘛（其实是我不会了）

 #include<bits/stdc++.h>

 using namespace std;

 #define mod 998244353

 #define int long long

 int inv[],fac[],invv[],n,m,k;

 signed main(){

     scanf("%lld%lld%lld",&n,&m,&k);

     if(n>m){puts("");return ;}

     if(n==m){puts("");return ;}

 //    if(m>n*k){puts("0");return 0;}

     inv[]=inv[]=fac[]=fac[]=invv[]=;

     for(int i=;i<=m;++i)invv[i]=-mod/i*invv[mod%i]%mod,inv[i]=inv[i-]*invv[i]%mod,fac[i]=fac[i-]*i%mod;

     int ans=fac[m-]*inv[n-]%mod*inv[m-n]%mod;

     for(int i=;i<=n&&i*k+n<=m;++i)ans=(ans+((i&)?-:)*fac[n]*inv[i]%mod*inv[n-i]%mod*fac[m-i*k-]%mod*inv[n-]%mod*inv[m-i*k-n]%mod)%mod;

     printf("%lld\n",(ans%mod+mod)%mod);

 }

贴代码就跑

巴特西

建设城市(city)：组合数，容斥原理

最新文章

热门文章