本文共 928 字，大约阅读时间需要 3 分钟。
题意：
给你n个数，要求选一些数（可以不选），把它们加起来，使得和恰好是p的倍数（0也是p的倍数），求方案数。
- - 心好痛，又没想到动规
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;#define mod 1000000007int p[1005];int dp[1005][1005];const int inf = 0x3f3f3f3f;int main(){ int T,n,t; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&t); memset(p,0,sizeof(p)); for(int i = 1; i <= n; i++) { scanf("%d",&p[i]); p[i]=p[i]%t; if(p[i] < 0) p[i]=(p[i]+t)%t; } memset(dp,0,sizeof(dp)); dp[1][0] = 1; dp[1][p[1]] += 1; for(int i = 2; i <= n; i++) { for(int j = 0; j < t; j++) { dp[i][j] += dp[i-1][j]; dp[i][j] %= mod; dp[i][(j+p[i]) % t] += dp[i-1][j]; dp[i][(j+p[i]) % t] %= mod; } } printf("%d\n",dp[n][0] % mod); } return 0;}
转载于:https://www.cnblogs.com/Przz/p/5409745.html