Luogu P2396 yyy loves Maths VII

题目传送门

“电脑运行速度很快！24的阶乘也不过就620448401733239439360000,yyy你快写个程序来算一算”

我想你可能需要神威·太湖之光

因为一共就24张卡片，可以状压
设f[S]，表示使用集合\(S\)的卡片的方案数，dis[S]表示使用集合\(S\)的卡片所能到达的距离
转移就很简单了，但这道题比较卡常，所以要用\(lowbit\)来快速找出所有的‘\(1\)‘

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define mod 1000000007
#define lb(__a) (__a & (-__a)) 
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int f[1 << 25], dis[1 << 25];
LL b[3];
int main() {
    int n = read();
    for(int i = 1; i <= n; ++i) dis[1 << i-1] = read();
    int m = read();
    for(int i = 1; i <= m; ++i) b[i] = read();
    f[0] = 1; int cnt = (1 << n) - 1;
    for(int i = 1; i <= cnt; ++i) {
        int k = lb(i);
        dis[i] = dis[k] + dis[i^k];
        if(dis[i] == b[1] || dis[i] == b[2]) continue;
        for(int j = i; j; j ^= k) {
            k = lb(j); f[i] = f[i] + f[i^k];
            while(f[i] >= mod) f[i] -= mod;
        }
    }
    printf("%d\n", f[cnt]);
    return 0;
}

双倍经验：CF327E

Luogu P2396 yyy loves Maths VII

原文：https://www.cnblogs.com/morslin/p/11855904.html