【校内模拟】Quests（組合數學）（反向計數）

傳送門，肯定是沒有的。

題解：

可以很顯然地發現，隻有當包含目前位置的詢問集合不同的時候，我們能夠區分這些位置。

定義一個不可識别子串 [ l , r ] [l,r] [l,r]為其左右位置無法區分的子串。

定義一個極長不可識别子串 [ l , r ] [l,r] [l,r]為一個不可識别子串，且不存在任何 l ′ ≤ l , r ′ ≥ r l'\leq l ,r'\geq r l′≤l,r′≥r， [ l ′ , r ′ ] [l',r'] [l′,r′]為一個不可識别子串，上式兩個等号不同時滿足。

顯然根據定義，一個單獨位置為一個不可識别子串，且對于一種詢問方式，所有極長不可識别子串不相交。同時，在任意一種詢問方式下，原序列可以拆分為若幹極長不可識别子串。

考慮令 f [ i ] f[i] f[i]表示将一個長度為 i i i的串完全區分的詢問方案數。

然而直接轉移并不容易，但是有總詢問方案數為 2 ( i + 1 2 ) 2^{i+1\choose 2} 2(2i+1​)，考慮算有多少種情況非法。

顯然唯一合法的情況就是将長度為 i i i的串拆成 i i i個極長不可識别串的并，少于 i i i的所有拆分方式均為非法。

考慮欽定拆分為 j j j個極長不可識别子串，注意到子串之間必須能夠完全區分，發現其實就是子問題 f [ j ] f[j] f[j]，設 g [ i ] [ j ] g[i][j] g[i][j]表示将長度為 i i i的串拆分 j j j個極長不相交子串的所有方案中，所有子串内部構造詢問的方案數。

則我們有如下轉移方程：

f [ i ] = 2 ( i + 1 2 ) − ∑ j = 1 i − 1 f [ j ] ⋅ g [ i ] [ j ] f[i]=2^{i+1\choose 2}-\sum_{j=1}^{i-1}f[j]\cdot g[i][j] f[i]=2(2i+1​)−j=1∑i−1​f[j]⋅g[i][j]

考慮計算 g [ i ] [ j ] g[i][j] g[i][j]。

顯然每次考慮在最後接上一個長度為 k k k的極長不可識别子串并且發現隻要求左右不可區分，内部可以任意詢問，有如下轉移方程：

g [ i + k ] [ j + 1 ] + = g [ i ] [ j ] ⋅ 2 ( k − 1 2 ) g[i+k][j+1]+=g[i][j]\cdot 2^{k-1\choose 2} g[i+k][j+1]+=g[i][j]⋅2(2k−1​)

代碼：

#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;
}