大意: n种一元的奥利奥, m种2元的奥利奥, 求花恰好k元钱购买奥利奥的方案数.
可重组合问题, 直接dp即可.
#include <iostream> #include <sstream> #include <algorithm> #include <cstdio> #include <math.h> #include <set> #include <map> #include <queue> #include <string> #include <string.h> #include <bitset> #define REP(i,a,n) for(int i=a;i<=n;++i) #define PER(i,a,n) for(int i=n;i>=a;--i) #define hr putchar(10) #define pb push_back #define lc (o<<1) #define rc (lc|1) #define mid ((l+r)>>1) #define ls lc,l,mid #define rs rc,mid+1,r #define x first #define y second #define io std::ios::sync_with_stdio(false) #define endl ' ' #define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;}) using namespace std; typedef long long ll; const int N = 2e3+10; int n, m, k, p, ff[N], *f = ff+1; int main() { int t; scanf("%d", &t); f[0] = 1; while (t--) { scanf("%d%d%d%d", &n, &m, &k, &p); REP(i,1,1000) f[i]=0; REP(i,1,n) REP(j,1,k) f[j]=(f[j]+f[j-1])%p; REP(i,1,m) REP(j,1,k) f[j]=(f[j]+f[j-2])%p; printf("%d ", f[k]); } }