洛谷2396 yyy loves Maths VII

题意

有 $N$ 张卡片，使用过后会往前跳 $S_i$ 格。有 $M$ 个格子是厄运格，如果跳到就输了，求跳到终点的方案数。

$N\le 24 \ , \ M\le 2$ 。

题解

用 $cnt[i]$ 表示当前走到的格子，很容易想出状压方程：

$$f[i]=\begin{cases} 0 \ (cnt[i]\in M) \\ f[i]+f[i \ xor \ 2^{j-1}] \ (cnt[i]\notin M) \end{cases}$$

然后写了一发朴素做法，有 $60$ 分：

#include<bits/stdc++.h>
#define ha 1000000007

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,s[25],e[3],f[16777216],cnt[16777216];

signed main()
{
    n=read();
    const int N=1<<n;
    for (int i=1;i<=n;i++) s[i]=read();
    m=read();
    for (int i=1;i<=m;i++) e[i]=read();
    for (int i=1;i<N;i++) for (int j=0;j<n;j++) cnt[i]+=(i>>j&1)*s[j+1];
    f[0]=1;
    for (int i=1;i<N;i++)
    {
        bool flag=0;
        for (int j=1;j<=m;j++) if (cnt[i]==e[j]) flag=1;
        if (flag) continue;
        for (int j=0;j<n;j++)
        {
            if (!(i>>j&1)) continue;
            f[i]=(f[i]+f[i^(1<<j)])%ha;
        }
    }
    return !printf("%d",f[N-1]);
}

计算 $cnt[i]$ 的开销太大了。可以发现 $< i$ 状态的 $cnt$ 都被计算过了，所以可以直接从某个状态推过来。令 $j=i \ and \ -i$ ，则 $cnt[i]=cnt[j]+cnt[i \ xor \ j]$ 。

还有枚举 $j$ 会造成很多浪费，可以只枚举 $i$ 中的 $1$ 。

#include<bits/stdc++.h>
#define ha 1000000007

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,e[3],f[16777216],cnt[16777216];

signed main()
{
    n=read();
    const int N=1<<n;
    for (int i=0;i<n;i++) cnt[1<<i]=read();
    m=read();
    for (int i=1;i<=m;i++) e[i]=read();
    f[0]=1;
    for (int i=1;i<N;i++)
    {
        int j=i&-i;
        cnt[i]=cnt[j]+cnt[i^j];
        bool flag=0;
        for (int j=1;j<=m;j++) if (cnt[i]==e[j]) flag=1;
        if (flag) continue;
        for (int j=i,k;j;j^=k)
        {
            k=j&-j; //枚举 1
            f[i]=f[i]+f[i^k];
            if (f[i]>=ha) f[i]-=ha;
        }
    }
    return !printf("%d",f[N-1]);
}