子序列子序列子序列…

标签： 动态规划 背包DP

---

题目描述

给定 n,m,再给一个含有 n个正整数的序列 a1,a2,…,an问序列 a有多少个非空子序列（子序列的定义为能从原序列中去除任意个位置上的元素后得到的序列）是完美的。
一个由正整数组成的序列是完美的，当且仅当它的每个非空子序列中的整数之和m的倍数。
在本题中，两个子序列只要除去的元素中至少有一个的位置不同，就算不同。观看提示中的样例解释可能可以帮助你更了解题意。
题目来源：comet oj #3

输出描述

第一行有 2 个由空格分隔的整数 n,m。
第二行有 n 个由空格分隔的整数a1,a2,…,an表示给定的序列。
数据满足 1≤n≤5000，2≤m≤5000，0 < ai < m。

输出描述

输出一个数，表示答案对 1000000007取模后的结果。

样例

样例输入 1
3 8
1 2 3
样例输出 1
2

样例输入 2
3 2
1 1 1
样例输出 2
4

题解

通过一些简单的组合数学我们可以知道，一个子序列的和为：
$$2^{n-1}\ast (a_{k1}+a_{k2}+….a_{kn})$$
于是我们可以把m拆为$m=2^{r}\ast d$,然后我们枚举n，则只要保证$(a_{k1}+a_{k2}+….a_{kn})$是$m1=2^{max(0,r-n+1)}\ast d$的倍数就可以了。
首先来分析状态设计，因为必须是m的倍数，所以我们肯定需要一位状态记录数字和是多少。则：
$f[i][j][k]$表示前$i$个数字，选$j$个和为$k$（mod $ m^{‘}$意义下，不然肯定爆空间嘛, $m^{‘}=m/2^{j-1}$ ）的方案数，于是我们就可以用背包的思想，即选或者不选两种决策进行转移。当然，这只记录了一部分，个数超过$r$并且和为$m$倍数也是合法方案。
因此设$g[i][k]$表示前$i$个数字，选了至少$r+1$个数字，和为$k$的方案数，可以发现在后期转移的时候$g$和$f$数组可以合并到一起。
不过这样设计状态仍然会超空间，我们发现每次状态只和前一项有关，因此可以滚动优化掉第一位。
并且随着$j$的增大，$k$这一维也在逐渐减小，总复杂度为$O(nm\ast (1+1/2+1/4+….)=2*nm)$

代码

#include<bits/stdc++.h>
#define N 5010
#define p 1000000007
using namespace std;

int n, m, ans = 0;
int a[N], f[2][15][N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    int m1 = m, t = 1, i = 0;
    while(m1 % 2 == 0) t ++, m1 >>= 1;
    f[0][0][0] = 1;
    for(int l = 1; l <= n; l ++)
    {
        memset(f[i ^ 1], 0, sizeof(f[i ^ 1]));
        for(int j = 0; j < t; j ++)
        {
            m1 = m / (1 << max(0, (j - 1))); 
            int m2 = m / (1 << j);
            for(int k = 0; k < m1; k ++)
            {
                f[i ^ 1][j][k] = (f[i ^ 1][j][k] + f[i][j][k]) % p;
                f[i ^ 1][j + 1][(k + a[l]) % m2] = (f[i ^ 1][j + 1][(k + a[l]) % m2] + f[i][j][k]) % p;
            }
        }
        int m2 = m / (1 << (t - 1));
        for(int k = 0; k < m2; k ++)
        {
            f[i ^ 1][t][k] = (f[i ^ 1][t][k] + f[i][t][k]) % p;
            f[i ^ 1][t][(k + a[l]) % m2] = (f[i ^ 1][t][(k + a[l]) % m2] + f[i][t][k]) % p;
        }
        i ^= 1;
    }
    for(int j = 1; j <= t; j ++) ans = (ans + f[i][j][0]) % p;
    printf("%d\n", ans);
    return 0;
}

心得

看来有关倍数问题的DP总有一维是记录前j个数和为m的余数的状态。