MENU

洛谷P2396 yyy loves Maths VII

洛谷P2396

状压dp,随便从一个合法的地方转移过来算下路程,没踩坑的话枚举从哪里转移过来。

#include<cstdio>
int n, m, f[16777216], bad[2], g[16777216] = { 1 }, lim;
int main() {
    scanf("%d", &n), lim = (1 << n) - 1;
    for (int i = 0; i < n; ++i)scanf("%d", f + (1 << i));
    scanf("%d", &m);
    for (int i = 0; i < m; ++i)scanf("%d", bad + i);
    for (int i = 1, j, k; i <= lim; ++i) {
        f[i] = f[i - (i & -i)] + f[i & -i];
        if (f[i] == *bad || f[i] == bad[1])continue;
        j = i;
        while (j)k = j & -j, g[i] = (g[i] + g[i - k]) % 1000000007, j -= k;
    }
    printf("%d", g[lim]);
}
Leave a Comment

captcha
请输入验证码