A guess 解題報告

dp,集合标号後統計數量

A guess

題意

選一個\([1,n](n\le 500)\)的整數，可以詢問數是否屬于區間\([l,r]\)，多次詢問一起回答，統計有多少種詢問區間集合(無序)滿足可以猜出這個數，對\(p(2^{29}\le p<2^{30})\)取模

中文題解看不懂，看了一下午英文題解，還是感覺了解的不好，就按照現在的了解說一下吧（為啥這題是今天最簡單的啊...

首先你寫暴力的話有個結論

每個權值\(i\)都有過詢問區間集合\(S_i\)，\(S_i\)代表覆寫整個值的詢問集合。如果有某兩個值的詢問集合是一樣的，那麼就猜不出來，否則一定可以猜出來。

考慮按照這個把每個權值編号\(a_i\)，以最小表示法來編号，要求是若\(S_i=S_j\)，那麼有\(a_i=a_j\)

不必在乎這個怎麼編号的，反正一定可以編出來，可以發現\(\{S\}\)對\(\{a\}\)是一個單射，于是我們轉過去統計\(\{a\}\)的數量。

按照要求我們可以統計存在\(a_i=a_j\)的集合的數量，就是補集的數量。

如果對于一個集合，有一個\(a_i=a_j\)，那麼我們可以把\([i,j]\)區間内的給拿開統計，等價于把這個區間縮成一個點，點的權值為\(a_i\)，把所有類似這樣的區間都拿開的話，剩下的集合是沒有重複元素的，也就是我們最終需要求得的答案，記為\(f_i\)

注意了解一下為什麼縮掉區間構成的子問題是相同的。

然後我們需要得到把一個原來長度為\(L\)的問題縮到\(K\)的方案數，設為\(g_{L,K}\)

不妨先把有關\(f\)的轉移寫出來

\[f_i=2^{\binom{i+1}{2}}-\sum_{j=1}^{i-1}f_jg_{i,j}

\]

即全集減去所有可以縮掉的方案（可縮的話一定不合法）

然後再考慮如何計算\(g\)

按照一些常見組合意義的東西的遞推的方法，我們應該枚舉最後一個一個集合大小。

首先不産生一個新的可縮的即\(g_{i-1,j-1}\)對\(g_{i,j}\)的貢獻

然後枚舉産生的縮掉的區間的大小\(k\)，在這個區間裡的詢問集合是随意的，即為全集

那麼轉移就為

\[g_{i,j}=g_{i-1,j-1}+\sum_{k=0}g_{i-k-2,j-1}2^{\binom{k+1}{2}}

嗯，感覺還是沒了解到本質的東西...

如果非要寫一些思路的話

把擁有集合的性質通過編号轉換到元素統計上去，這點和字尾自動機狀态的建構好像有些相似，字尾自動機定義了每個子串的endpos集合，然後按照每個子串集合劃分狀态，進行統計。這種方法應該可以成為一種思路吧，這個題大概就是通過最小表示法編号。

#include <cstdio>
const int N=510;
int n,mod,po[N*N],g[N][N],f[N],d[N];
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
#define mul(a,b) (1ll*a*b%mod)
int main()
{
    scanf("%d%d",&n,&mod);
    po[0]=1;for(int i=1;i<=n*n;i++) po[i]=mul(po[i-1],2);
    for(int i=1;i<=n;i++) d[i]=i*(i+1)/2;
    g[0][0]=1;
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=i;j++)
        {
            g[i][j]=g[i-1][j-1];
            for(register int k=0;k<=i-2;k++)
                g[i][j]=add(g[i][j],mul(g[i-k-2][j-1],po[d[k]]));
        }
    for(register int i=1;i<=n;i++)
    {
        f[i]=po[d[i]];
        for(register int j=1;j<i;j++)
            f[i]=add(f[i],mod-mul(f[j],g[i][j]));
    }
    printf("%d\n",f[n]);
    return 0;
}