CF413D 【2048】

思路：

先考虑如果序列的形态全部已知，如何在线性的时间内判断该序列能否合并超过 \(2^k\) 。
可以记录一个和 \(sum\) 表示当前可能继续合并的后缀的和，那么这个后缀一定是最长不上升的。
例如这个后缀：16 8 4 2 4 ，最后一个 \(4\) 因为上升，无法合并到前面的序列中，与之前隔绝，所以不能加到前面的 \(sum\) 中。

那么分类讨论：

• 如果填的是 \(2\) ，由于 \(2\) 是最小的数，那么一定不会上升，直接将 \(sum+=2\) 即可。
• 如果填的是 \(4\) ，且 \(sum\) 中没有单独的 \(2\) ，即 \(sum\) 可以整除 \(4\)，那么在这之前就没有小于 \(4\) 的数，可以直接将 \(sum+=4\) ( 即使有 \(2\) ，因为所有 \(2\) 都是成对的，所有都可以合并为 \(4\) ) 。
• 如果填的是 \(4\) ，且 \(sum\) 中有单独的 \(2\)，即 \(sum \bmod{4} = 2\)，那么就意味着出现了上述例子的情况，新增的 \(4\) 无法参与到之前的合并中，所以只能重新记录，即 \(sum = 4\)

当 \(sum \ge 2^k\) 时，就意味着 \(2^k\) 可以被拼出来。

那么可以将这个过程写成 dp ，设 \(dp[i][j]\) 为填了前 \(i\) 个数，当前的 \(sum\) 为 \(j\) 时的方案数。
因为 \(sum\) 只要大于 \(2^k\)，\(2^k\) 就可以合并出来，所以我们可以把 \(sum \ge 2^k\) 时的答案也归入 \(sum = 2^k\) 中，即在 \(2^k\) 与更新完的 \(sum\) 中取 \(\min\)。

那么可以得出转移方程：
当填的是 \(2\) 时：

• \(dp[i][ \min(j+2,2^k)] += dp[i-1]j]\)

当填的是 \(4\) ，且 \(sum\) 中没有单独的 \(2\) 时：

• \(dp[i][\min(j+4,2^k)] += dp[i-1]j]\)

当填的是 \(4\) ，且 \(sum\) 中有单独的 \(2\) 时：

• \(dp[i][4] += dp[i-1]j]\)

当填的是 \(0\) 时：

• 既当成 \(2\) 转移一次，再当作 \(4\) 转移一次即可。

边界就是 \(dp[0][0] = 1\)
最后的答案就是 \(dp[n][2^k]\)

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<queue>
#include<map>
#include<set>

using namespace std;

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

const int N=2005,K=11,mod=1e9+7;
int n,k,a,dp[N][(1<<K)+5];

int main()
{
	n=read();k=read();
	dp[0][0]=1;
    // 边界
	for(int i=1;i<=n;++i)
	{
		a=read();
		for(int j=0;j<=(1<<k);++j)
       	// 枚举 sum
		{
			if(a==2||a==0)
            // 当填的是 2 或 0 时
				dp[i][min(j+2,1<<k)]=(dp[i][min(j+2,1<<k)]+dp[i-1][j])%mod;
			if(a==4||a==0)
			// 当填的是 4 或 0 时
			{
				if(j%4==2)
				// 当 sum 中有单独的 2 时
					dp[i][4]=(dp[i][4]+dp[i-1][j])%mod;
				else
				// 当 sum 中没有单独的 2 时
					dp[i][min(j+4,1<<k)]=(dp[i][min(j+4,1<<k)]+dp[i-1][j])%mod;
			}
		}
	}
	printf("%d",dp[n][1<<k]);
	return 0;
}