每天写两道dp题，2020/07/03 打卡第一天 题目链接
题目描述 老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 NN 头奶牛中选出一支队伍。每只奶牛的能力为整数，第 ii 头奶牛的能力为Ri 。飞盘队的队员数量不能少于 11、大于NN。一支队伍的总能力就是所有队员能力的总和。约翰比较迷信，他的幸运数字是 FF ，所以他要求队伍的总能力必须是 F 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 10^8取模的值。
输入格式 第一行：两个用空格分开的整数：N 和 F。 第二行到 N+1 行：第 i+1i+1 行有一个整数Ri，表示第 ii 头奶牛的能力。
输出格式 第一行：单个整数，表示方案数对 10^8 取模的值。
输入输出样例 输入 #1
4 5 1 2 8 2
输出
3
用dp[i][j]表示前i个物品和模f余数为j时候的方法的最优解。
则状态转移方程为
dp[i][j]=dp[i][j]+dp[i-1][j]+dp[i-1][(j-a[i]+f)%f];
#include<bits/stdc++.h> #define pb push_back #define bp __builtin_popcount using namespace std; typedef unsigned long long ll; const int inf = 0x3f3f3f3f; const int maxn = 2e3 + 100; const int MOD = 1e8; int lowbit(int x) { return x & -x; } inline ll dpow(ll a, ll b) { ll r = 1, t = a; while (b) { if (b & 1)r = (r * t) % MOD; b >>= 1; t = (t * t) % MOD; }return r; } inline ll fpow(ll a, ll b) { ll r = 1, t = a; while (b) { if (b & 1)r = (r * t); b >>= 1; t = (t * t); }return r; } ll n,a[maxn],f,dp[maxn][maxn]; int main() { cin>>n>>f; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]=a[i]%f; } for(int i=1;i<=n;i++) dp[i][a[i]]=1; for(int i=1;i<=n;i++) { for(int j=0;j<f;j++) { dp[i][j]=dp[i][j]+dp[i-1][j]+dp[i-1][(j-a[i]+f)%f]; dp[i][j]%=MOD; } } cout<<dp[n][0]<<endl; system("pause"); return 0; }