【计数dp】quests

【描述】
有一天，球球和他的好朋友熊熊在玩一个猜数字的游戏。

这个游戏是这样子的：熊熊会先在 [1, n] 中选取一个数，然后问球球他选取的数是多少。球球当然不知 道啦，所以他会向熊熊提出若干个问题，每个问题形如：选取的数是否在[li,ri]之间？球球可以提出很 多的问题，而熊熊也会不厌其烦地回答他。形式化地，对于球球给出的一个询问集合 Q，熊 熊会返回一 个长为 |Q| 的 01 序列表示每次询问的答案。

球球很想猜出熊熊选取的数，因为这样就可以显得自己很厉害。虽然已经不会 #include 了，但是球球毕 竟身经百战，还是掌握一些组合数学的小知识。他知道自己多次询问相同的 是没有意义的，他也知 道询问的顺序对自己能否猜出熊熊选取的数没有影响。他甚至发现，自己可以提出的不同的询问最多只 有2C2n+1个，也就是说他可以提出的不同的询问集合只有2C2n+1个。

球球想知道这 个可以提出的询问集合中，有多少询问集合可以使他可以准确地猜出熊熊选取的 数。

由于答案可能很大，而球球不喜欢很大的数字，所以他希望你能告诉他答案对一个大质数 P 取模后的结 果。

【输入】
第一行两个正整数 n, P ，意义详见题目描述。

【输出】
一行一个整数，表示答案对 P 取模后的结果。

【样例输入】
7 998244353

【样例输出】
256097184

思路

这是一道暴力都不会打的计数问题。
首先一个简单的结论，要区别所有的位置，必须满足每个位置的询问集合不同。定义$f[i]$表示一共i个位置的合法方案数。折腾一下就可以发现，f之间不能直接转移。我们考虑计算补集。定义$g[i][j]$表示i个数分为j个极长不可识别段的方案。对于不可识别段的定义：左端点与右端点不能区别。这个状态定义很有意思，可以囊括所有的情况，转移所需的信息也足够。在进行g的转移时，我们先保证划分出的段为不可识别段。对于一个长度为k不可识别段，链端不可互相识别，但是中间的位置我们并不关心，所以中间的询问集合可以任意选取，也就是$2^{{\mathbb{C}}_{k-1}^2}$种选法。根据乘法原理，我们得到方程：
$$g[i+k][j+1]=g[i][j]\ast 2^{{\mathbb{C}}_{k-1}^2}$$
而当我们用g更新f时，我们需要考虑保证段为极长不可识别段。对于j个不可识别段，我们要保证它们都是极长的，也就是说这j个段要互相区别出来，等价于区分j个位置，所以方案数为$f[j]$。而$j==i$时情况合法，不属于补集。因此我们得到方程：
$$f[i]=2^{{\mathbb{C}}_{i+1}^2}-\sum _{j=1}^{i-1}f[j]\ast g[i][j]$$
代码：

#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=400+3;
inline int red()
{
    int data=0;int w=1; char ch=0;
    ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return data*w;
}
int n,nn,mod;
int f[N];
int g[N][N];
int lo[N*N];
int main()
{
	n=red();mod=red();nn=n*n;
	g[0][0]=1;lo[0]=1;
	for(int re i=1;i<=nn;i++)lo[i]=2ll*lo[i-1]%mod;
	for(int re i=0;i<=n;i++)
		for(int re j=0;j<=i;j++)
			if(g[i][j])
			for(int re k=1;k<=n-i;k++)
				g[i+k][j+1]+=1ll*g[i][j]*lo[(k-1)*(k-2)>>1]%mod,g[i+k][j+1]%=mod;
	for(int re i=1;i<=n;i++)
	{
		f[i]=lo[(i+1)*i>>1];
		for(int re j=1;j<i;j++)
			f[i]-=1ll*f[j]*g[i][j]%mod,f[i]=(f[i]%mod+mod)%mod;
	}
	printf("%d",f[n]);
}