题意：有n个数，a_0, a_1, ... a_(n-1)，从中选取一部分数(可以一个都不选)，使得其和为p的倍数，问方案数。
解：这题怎么说呢。。。就差在把背包这俩字甩我脸上了。。。but，昨天还是没有做出来。-_-!
#include#include #include #include #include #include #include #include #include using namespace std;typedef unsigned int uint;typedef long long LL;typedef unsigned long long uLL;const int N = 1005;const double PI = acos(-1.0);const double eps = 1e-6;const double INF = 1e9+7;const int MOD = 1000000007;int f[N][N];int a[N];int n, p;int main() { //freopen("data.in", "r", stdin); int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &p); memset(f, 0, sizeof(f)); //int off = N; for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); a[i] = (a[i]%p + p)%p; } f[0][0] = 1; for(int i = 1; i <= n; ++i) { for(int j = 0; j <= p; ++j) { f[i][j] = (f[i][j] + f[i-1][j])%MOD; //if(f[i-1][j + off] != 0) { f[i][(j + a[i])%p] = (f[i][(j + a[i])%p] % MOD + f[i-1][j] % MOD) % MOD; //} } } printf("%d\n", f[n][0] % MOD); } return 0;}