题目地址：51Nod：子集价值 问题 – 51Nod

题目描述

lyk最近在研究位运算。它发现除了xor,or,and外还有很多运算。它新定义了一种运算符“#”。具体地，可以由4个参数来表示。ai,j表示ｉ＃ｊ。其中i,j与a的值均∈[0,1]。当然问题可以扩展为>1的情况，具体地，可以将两个数分解为p位，然后对于每一位执行上述的位运算，再将这个二进制串转化为十进制就可以了。例如当 a0,0=a1,1=0,a0,1=a1,0=1时,3#4在p=3时等于7,2#3在p=4时等于1（实际上就是异或运算）。
现在lyk想知道的是，已知一个数列b。它任意选取一个序列c，满足 c1<c2<…<ck，其中1≤c1且ck≤n ，这个序列的价值为 bc1 # bc2 #…# bck 的平方。这里我们假设k是正整数，因此满足条件的c的序列一定是 2n−1 。lyk想知道所有满足条件的序列的价值总和是多少。例如样例中，7个子集的价值分别为1,1,4,4,9,9,0。总和为28。
由于答案可能很大，只需对1,000,000,007取模即可。

输入输出格式

输入格式：
第一行两个整数n(1<=n<=50000),p(1<=p<=30)。
第二行4个数表示a0,0，a0,1，a1,0，a1,1。(这4个数都∈{0,1})
第三行n个数bi(0<=bi<2^p)。

输出格式：
一行表示答案。

输入输出样例

输入样例#1：

3 30
0 1 1 0
1 2 3

输出样例#1：

28

题解

又是一道喜闻乐见的数位DP。
首先这个平方给我们设置了一个障碍，我们如果不求平方只求和，那么我们可以设计状态dp[i][0/1]表示当前处理到第i个数，现在正在处理的这一位经过运算后为0或1的方案总数。我们从大到小枚举每一位，每一位对答案的贡献就是1<<数*dp[n][1]。
但是现在有一个平方，那我们考虑平方的意义。如果把每一位单独拆出来算，那么一个十进制数可以表示成一堆2的幂加起来的结果，又由于我们有下面的式子
(A_1+A_2+A_3+A_4+\cdots+A_n)^2 = A_1A_2 + \cdots + A_1A_n + A_2A_1 + \cdots + A_2A_n + \cdots + A_n^2
我们发现，平方后的结果的每一项只跟原来的两项有关系。换句话说，原来的数中两个位就能对平方后的答案产生一个位的贡献。那我们考虑把上面求和的DP状态扩展为dp[i][0/1][0/1]表示当前处理到第i个数，选定的两位分别为多少的方案总数。我们枚举选定哪两位来组合出答案，每枚举一次就DP一次，由于两位必须得都是1乘起来才非0，最后枚举的两位产生的贡献就是dp[n][1][1]*1<<(i+j)，其中i和j是枚举的两位。
这样做的时间复杂度是O(p^2n)的。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50005, MO = 1e9 + 7;

int n, p, op[2][2];
LL dp[MAXN][2][2], a[MAXN];

int main() {
    n = readint();
    p = readint();
    op[0][0] = readint();
    op[0][1] = readint();
    op[1][0] = readint();
    op[1][1] = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    LL ans = 0;
    for(int i = 0; i < p; i++) {
        for(int j = 0; j < p; j++) {
            memset(dp, 0, sizeof(dp));
            for(int k = 1; k <= n; k++) {
                int p1 = (a[k] >> i) & 1, p2 = (a[k] >> j) & 1;
                dp[k][p1][p2] = (dp[k][p1][p2] + 1) % MO;
                dp[k][op[0][p1]][op[0][p2]] = (dp[k][op[0][p1]][op[0][p2]] + dp[k - 1][0][0]) % MO;
                dp[k][0][0] = (dp[k][0][0] + dp[k - 1][0][0]) % MO;
                dp[k][op[0][p1]][op[1][p2]] = (dp[k][op[0][p1]][op[1][p2]] + dp[k - 1][0][1]) % MO;
                dp[k][0][1] = (dp[k][0][1] + dp[k - 1][0][1]) % MO;
                dp[k][op[1][p1]][op[0][p2]] = (dp[k][op[1][p1]][op[0][p2]] + dp[k - 1][1][0]) % MO;
                dp[k][1][0] = (dp[k][1][0] + dp[k - 1][1][0]) % MO;
                dp[k][op[1][p1]][op[1][p2]] = (dp[k][op[1][p1]][op[1][p2]] + dp[k - 1][1][1]) % MO;
                dp[k][1][1] = (dp[k][1][1] + dp[k - 1][1][1]) % MO;
            }
            ans = (ans + (1ll << (i + j)) % MO * dp[n][1][1] % MO) % MO;
        }
    }
    printf("%lld", ans);
    return 0;
}