Comet OJ - contest #3 C DP

冷不防 2021-12-12 01:57 176阅读 0赞

题意：给你一个长度为n序列，和一个数m，问这个序列有多少个子序列，满足这个子序列的所有子序列的和是m的倍数？答案对1e9 + 7取模，n, m范围到5e3;

思路：容易发现，如果一个子序列的长度是n，子序列的所有的元素的和是sum的话，它的所有的子序列的和是sum \* 2 ^ (n - 1)，那么我们发现，一个序列的所有子序列的和与子序列的和以及子序列的长度有关，我们容易想O(n^2 \* m)的DP。设dp\[i\]\[j\]\[k\]为前i个数，长度为j的子序列中子序列的和是k的元素的个数。每扫到一个新的元素，有两种决策：1：不加这个数dp\[i + 1\]\[j\]\[k\] += dp\[i\]\[j\]\[k\]；2：加这个数dp\[i + 1\]\[j +1\]\[k + a\[i + 1\] += dp\[i\]\[j\]\[k\]。每次转移O(n \* m),总复杂度O(n ^ 2 \* m).

我们现在考虑优化一下dp。我们发现一个序列的子序和与2 ^ (n - 1)与sum有关，若要子序和是m的倍数，分两种情况：1：2不是m的因子，那么容易发现2 ^ (n - 1)不会影响子序和是否是m的倍数。2：2是m的因子，但是m最大范围是5e3,所以最大有2 ^ 12这个因子，而所以当n大于12的时候又变成了情况1.所以，实际上dp的第二维的大小只有十几，复杂度降为了O(n \* logn \* m),但是这样的复杂度仍然不够优秀，我们考虑继续优化。我们可以发现,dp\[i\]\[j\]\[k\]中，随着j的增加，k那一维的模数也在不断减少，模数是m + m / 2 + m / 4 ...这个复杂度是O(m)的，所以我们逐步优化之后，复杂度降低到了O(n \* m)。

代码：

#include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    const int maxn = 5010;
    const LL mod = 1000000007;
    int a[maxn], dp[2][15][maxn], p[20];
    void update(int &x, int y) {
    	x = ((long long)x + y) % mod;
    }
    int main() {
    	int n, m;
    	int ans = 0;
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= n; i++) {
    		scanf("%d", &a[i]);
    	}
    	int cnt = 0;
    	int tmp = m;
    	while(tmp % 2 == 0) {
    		tmp /= 2;
    		cnt++;
    	}
    	dp[0][0][0] = 1;
    	for (int i = 0; i < n; i++) {
    		memset(dp[(i + 1) & 1], 0, sizeof(dp[(i + 1) & 1]));
    		for (int j = 0; j <= cnt + 1; j++) {
    			memset(dp[(i + 1) & 1][j], 0, sizeof(int) * (m / (1 << max(0, j - 1))));
    		}
    		for (int j = 0; j <= cnt; j++) {
    			int mm = m / (1 << max(0, j - 1)), mmm = m / (1 << max(0, j));
    			for (int k = 0; k < mm; k++) {
    				if(!dp[i & 1][j][k]) continue;
    				update(dp[(i + 1) & 1][j][k], dp[i & 1][j][k]);
    				update(dp[(i + 1) & 1][j + 1][(k + a[i + 1]) % mmm], dp[i & 1][j][k]);
    			}
    		}
    		for (int j = 0; j < tmp; j++) {
    			if(!dp[i & 1][cnt + 1][j]) continue;
    			update(dp[(i + 1) & 1][cnt + 1][j], dp[i & 1][cnt + 1][j]);
    			update(dp[(i + 1) & 1][cnt + 1][(j + a[i + 1]) % tmp], dp[i & 1][cnt + 1][j]);
    		}
    	}
    	for (int i = 1; i <= cnt + 1; i++) {
    		update(ans, dp[n & 1][i][0]);
    	}
    	printf("%d\n", ans);
    	return 0;
    }

转载于:https://www.cnblogs.com/pkgunboat/p/10849494.html