本文主要是介绍msc的背包（挡板法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://ac.nowcoder.com/acm/contest/217/D
来源：牛客网
题目描述
msc是个可爱的小女生，她喜欢许许多多稀奇古怪的小玩意。
一天，msc得到了一个大小为k的背包，她决定去买东西。
商店里有n种大小为1的物品和m种大小为2的物品。
由于msc希望买的东西尽量多，所以msc不希望买完东西之后背包还有空位（即买的所有东西的体积和必须等于k）。
她想知道自己有多少种购买物品的方案。
两种方案不同当且仅当存在一种物品在两种方案中的数量不同。
输入描述:
一行三个整数n,m,k，分别表示大小为1的物品的种类数和大小为2的物品的种类数以及背包的容量。输出描述:
一行一个整数表示答案，由于答案可能很大，所以请对998244353取模后输出。
示例1
输入
复制
4 5 454输出
复制
605690007思路：我们考虑体积为1的物品，对每一种体积为1的物品要么拿奇数件，要么拿偶数件。如果我知道哪些体积为1的物品拿偶数件，那样我们就能把两件体积为1的物品捏成一件体积为2的物品，这样就能和体积为2的物品合起来，然后用挡板法计算啦。
其实这个问题如果用生成函数来表示的话，它的生成函数可以表示为1/ （1-x）^a * 1/(1-x*x)^b
然后上下同乘以（1+x）^a 得到 （1+x）^a * [ 1 / (1-x*x)^(a+b)],这样就能枚举前面的次方数，后面用挡板法。
那么这个题的复杂度与a相关。即本题中枚举体积为1的物品奇数件的种类数，两种方法从两个角度说明了这个相同的问题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+777;
const ll mod = 998244353LL;ll fac[maxn],dev[maxn];
ll C(ll n, ll m)
{return fac[n]*dev[m]%mod*dev[n-m]%mod;
}
ll qm(ll a, ll n)
{ll ans = 1;while(n){if(n%2) ans = ans*a%mod;a = a*a%mod;n/=2LL;}return ans;
}
int main()
{for(ll i = 0; i <= 2000000; i++) fac[i] = i == 0 ? 1LL : fac[i-1]*i%mod;for(ll i = 2000000; i >= 0; i--) dev[i] = i == 2000000 ? qm(fac[i],mod-2) : dev[i+1]*(i+1)%mod;ll a,b,k,num1,num2;scanf("%lld%lld%lld",&a,&b,&k);ll ans = 0;ll tmp = 1;ll cur = a+b+k/2LL-1,curm = k/2LL;for(ll i = curm+1LL; i <= cur; i++) tmp = tmp*(i)%mod;tmp *= dev[a+b-1];tmp %= mod;for(ll i = 0; i <= a; i++){if((k-i)%2 == 0){ans += C(a,i)*tmp%mod;ans %= mod;tmp = tmp*curm%mod*qm(cur,mod-2)%mod;cur--;curm--;}}printf("%lld\n",ans);return 0;
}
这篇关于msc的背包（挡板法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
