Comet OJ - Contest #3 子序列子序列子序列...

题目链接：点我啊╭(╯^╰)╮

题目大意：

解题思路：

    对于子序列 $a_1 + a_2 + ... + a_k$a1​+a2​+...+ak​ 是完美序列，那么$2^{k-1}$2k−1 $* (a_1 + a_2 + ... + a_k)$∗(a1​+a2​+...+ak​) 是 $m$m 的倍数
    设 $m = m_0 * 2^c$m=m0​∗2c ，$m_0$m0​ 为奇数，则分类讨论如下：
    若 $j ≤ c$j≤c，则 $dp[j][k]$dp[j][k] 表示长度为 $j$j 的序列，求和后对 $m/2^{j-1}$m/2j−1 取模得k的子序列个数
    若 $j＞c$j＞c，则 $dp[c+1][k]$dp[c+1][k] 表示长度至少为 $c+1$c+1 的序列，求和后对 $m/2^c$m/2c 取模得 $k$k 的子序列个数
    对于子序列是否包含 $ai$ai ，递推求出 $i=1$i=1 ~ $n$n 的所有情况
    最后复杂度为 $O(nm)$O(nm)

核心：dp的优化

#include<bits/stdc++.h>
#define rint register short int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 1e9 + 7;
const int maxn = 5e3 + 10;
int a[maxn], b[maxn], dp[15][maxn];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d", a+i);
	int c = 0, ans = 0;
	for(int i=m; i%2==0; i/=2, c++);
	for(rint t=1; t<=c+1; t++) {	// 枚举前 c位
		memset(dp,0,sizeof(dp));
		int d = m / (1 << t-1);
		dp[0][0] = 1;
		for(rint i=1; i<=n; i++) {	// 逐个插入 a[i]
			for(rint k=0; k<d; k++) b[k] = dp[c+1][k];
			for(rint j=t-1; j>=0; j--) {
				for(rint k=0; k<d; k++) {
					dp[j+1][(k+a[i])%d] += dp[j][k];
					dp[j+1][(k+a[i])%d] %= mod;
				}
			}
			if(t==c+1)	// t > c 的情况 
				for(rint k=0; k<d; k++) {
					dp[c+1][(k+a[i])%d] += b[k];
					dp[c+1][(k+a[i])%d] %= mod;
				}
		}
		ans += dp[t][0];
		ans %= mod;
	}
	printf("%d\n", ans);
}