【校内模拟】Quests（组合数学）（反向计数）

传送门，肯定是没有的。

---

题解：

可以很显然地发现，只有当包含当前位置的询问集合不同的时候，我们能够区分这些位置。

定义一个不可识别子串$[l,r]$为其左右位置无法区分的子串。

定义一个极长不可识别子串$[l,r]$为一个不可识别子串，且不存在任何$l^{\prime }\le l,r^{\prime }\ge r$，$[l^{\prime },r^{\prime }]$为一个不可识别子串，上式两个等号不同时满足。

显然根据定义，一个单独位置为一个不可识别子串，且对于一种询问方式，所有极长不可识别子串不相交。同时，在任意一种询问方式下，原序列可以拆分为若干极长不可识别子串。

考虑令$f[i]$表示将一个长度为$i$的串完全区分的询问方案数。

然而直接转移并不容易，但是有总询问方案数为$2^{\left(\genfrac{}{}{0ex}{}{i+1}{2}\right)}$，考虑算有多少种情况非法。

显然唯一合法的情况就是将长度为$i$的串拆成$i$个极长不可识别串的并，少于$i$的所有拆分方式均为非法。

考虑钦定拆分为$j$个极长不可识别子串，注意到子串之间必须能够完全区分，发现其实就是子问题$f[j]$，设$g[i][j]$表示将长度为$i$的串拆分$j$个极长不相交子串的所有方案中，所有子串内部构造询问的方案数。

则我们有如下转移方程：

$$f[i]=2^{\left(\genfrac{}{}{0ex}{}{i+1}{2}\right)}-\sum _{j=1}^{i-1}f[j]\cdot g[i][j]$$

考虑计算$g[i][j]$。

显然每次考虑在最后接上一个长度为$k$的极长不可识别子串并且发现只要求左右不可区分，内部可以任意询问，有如下转移方程：

$$g[i+k][j+1]+=g[i][j]\cdot 2^{\left(\genfrac{}{}{0ex}{}{k-1}{2}\right)}$$

---

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

int mod=998244353;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline void Inc(int &a,int b){(a+=b)>=mod&&(a-=mod);}
inline void Dec(int &a,int b){(a-=b)<0&&(a+=mod);}

cs int N=4e2+7;
int n;
int f[N],g[N][N],pw[N*N];

signed main(){
#ifdef zxyoi
	freopen("quests.in","r",stdin);
#endif
	std::cin>>n>>mod;
	for(int re i=pw[0]=1,li=n*n;i<=li;++i)pw[i]=add(pw[i-1],pw[i-1]);
	g[0][0]=1;
	for(int re i=0;i<n;++i)
	for(int re j=0;j<=i;++j)
	for(int re k=1;k<=n-i;++k)
	Inc(g[i+k][j+1],mul(g[i][j],pw[(k-1)*(k-2)>>1]));
	f[0]=1;
	for(int re i=1;i<=n;++i){
		f[i]=pw[i*(i+1)>>1];
		for(int re j=1;j<i;++j)
		Dec(f[i],mul(f[j],g[i][j]));
	}
	std::cout<<f[n]<<"\n";
	return 0;
}