codeforces 544C（完全背包求方案数）

题意描述

Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i-th of them makes exactly a i bugs in every line of code that he writes.

Let’s call a sequence of non-negative integers v 1, v 2, …, v n a plan, if v 1 + v 2 + … + v n = m. The programmers follow the plan like that: in the beginning the first programmer writes the first v 1 lines of the given task, then the second programmer writes v 2 more lines of the given task, and so on. In the end, the last programmer writes the remaining lines of the code. Let’s call a plan good, if all the written lines of the task contain at most b bugs in total.

Your task is to determine how many distinct good plans are there. As the number of plans can be large, print the remainder of this number modulo given positive integer mod.

第i个人写一行代码会出vi个bug，要求写m行代码，询问bug不超过b个的方案数

思路

由于每个人可以打多行代码，所以很明显的可以想到这是一道完全背包，所以可以用f[i][j]表示前i行代码bug不超过j个的方案的集合，由于要求的是方案数，所以我们知道两个状态间的计算方式肯定是相加的。从而得到状态转移方程：

转移方程

其余套用完全背包模板即可

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=505;
ll a[N],f[N][N];
void solve(){
    int n,m,b,mod;cin>>n>>m>>b>>mod;
    rep(i,1,n+1) cin>>a[i];
    f[0][0]=1;
    rep(i,1,n+1){
        rep(j,1,m+1){
            rep(k,a[i],b+1){
                f[j][k]=(f[j][k]+f[j-1][k-a[i]])%mod;
            }
        }
    }
    ll sum=0;
    rep(i,0,b+1) sum=(sum+f[m][i])%mod;
    cout<<sum<<endl;
}
int main(){
    IOS;
    solve();
    return 0;
}