UOJ #214 合唱队形 (概率期望计数、DP、Min-Max容斥)

红太狼 2021-12-03 07:49 231阅读 0赞

9个月的心头大恨终于切掉了！！！！  
非常好的一道题，不知为何uoj上被点了70个差评。

题目链接: [http://uoj.ac/problem/214][http_uoj.ac_problem_214]

题目大意: 请自行阅读。

题解:

官方题解讲得相当清楚，这里补充一下自己的一些理解。

首先来看\\(O(2^\{n-m\}\\times poly(n,m))\\)的做法。

一种理解方式是官方题解。

设\\(s\\)为总共的课程个数(\\(n\\)个字符串的总长度)，\\(p(S)\\)表示结尾位置为集合\\(S\\)的串全部匹配一共需要完成多少个不同的课程。设\\(f(t)\\)表示\\(t\\)时刻整个过程没有终止的概率，\\(prob(S,t)\\)表示\\(S\\)集合结尾的串在\\(t\\)时刻或者之前已经完成匹配的概率。\\(ans\\)为答案。

\\\[ans=\\sum^\{+\\inf\}\_\{t=0\} f(t)=\\sum^\{+\\inf\}\_\{t=0\} \\sum\_\{S, |S|\\ge 0\}(-1)^\{|S|\} prob(S,t)=\\sum^\{+\\inf\}\_\{t=0\} \\sum\_\{S,|S|\\ge 0\}(-1)^\{|S|\} \\sum^\{f(S)\}\_\{i=0\} (-1)^i\{f(S)\\choose i\}(\\frac\{s-i\}\{s\})^t\\\\ =\\sum^\{+\\inf\}\_\{t=0\} \\sum\_\{S,|S|\\ge 0\}(-1)^\{|S|\} \\sum^\{f(S)\}\_\{i=1\} (-1)^i\{f(S)\\choose i\}(\\frac\{s-i\}\{s\})^t\\\\ =\\sum\_\{S,|S|\\ge 0\}(-1)^\{|S|\} \\sum^\{f(S)\}\_\{i=0\} (-1)^i\{f(s)\\choose i\}\\sum^\{\\inf\}\_\{t=0\}(\\frac\{s-i\}\{s\})^t=\\sum\_\{S,|S|\\ge 0\}(-1)^\{|S|\} \\sum^\{f(S)\}\_\{i=0\} (-1)^i\{f(S)\\choose i\} \\frac\{s\}\{i\}\\\]

计算即可。

其实还有另外一种理解方式。我们要求的是所有串匹配时间**最小值**的期望，根据Min-Max容斥，我们可以通过枚举子集转化成对每个子集求该子集内串匹配时间**最大值**的期望，然后转化成每一时刻没结束的概率。

然后来看更难的\\(O(2^m\\times poly(n,m))\\)做法。

对于所有\\(p(S)\\)相同的\\(S\\), 其对答案的贡献没有区别。

因此对于所有\\(k\\)，考虑计算\\(p(S)=k\\)的\\(S\\)的个数。

然后直接dp即可。

代码错误记录: 注意solution1如果\\(n-m=16\\)的话数组要开到\\(2^\{17\}\\).

#### 代码 ####

#include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #define llong long long
    using namespace std;
    
    const int N = 30;
    const int S = 26;
    const int P = 998244353;
    bool ok[N+3];
    int f[N+3][S+3];
    char str[N+3];
    char a[N+3];
    llong fact[2000003],finv[2000003],inv[2000003];
    int cnt[(1<<17)+3];
    int n,m,s;
    
    llong quickpow(llong x,llong y)
    {
        llong cur = x,ret = 1ll;
        for(int i=0; y; i++)
        {
            if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}
            cur = cur*cur%P;
        }
        return ret;
    }
    llong comb(llong x,llong y) {return x<0 || y<0 || x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;}
    
    namespace Solution1
    {
        int ff[N+3][S+3];
        llong ans;
        void solve()
        {
            ans = 0ll;
            for(int i=1; i<(1<<(n-m+1)); i++)
            {
                llong cur = 0ll; bool gg = false;
                for(int j=0; j<=n-m; j++)
                {
                    if(i&(1<<j))
                    {
                        for(int k=0; k<m; k++)
                        {
                            ff[j+k][a[k]-96] = true;
                            if(f[j+k][a[k]-96]==false) {gg = true; break;}
                        }
                        if(gg==true) break;
                    }
                }
                if(gg)
                {
                    for(int j=0; j<n; j++)
                    {
                        for(int k=1; k<=S; k++)
                        {
                            ff[j][k] = false;
                        }
                    }
                    continue;
                }
                int num = 0;
                for(int j=0; j<n; j++)
                {
                    for(int k=1; k<=S; k++)
                    {
                        if(ff[j][k]==true) {num++;}
                    }
                }
                for(int j=1; j<=num; j++)
                {
                    llong tmp = (llong)s*inv[j]%P*comb(num,j)%P;
                    if(!(j&1)) {cur = (cur+tmp)%P;}
                    else {cur = (cur-tmp+P)%P;}
                }
                for(int j=0; j<n; j++)
                {
                    for(int k=1; k<=S; k++)
                    {
                        ff[j][k] = false;
                    }
                }
                if(cnt[i]&1) {ans = (ans-cur+P)%P;}
                else {ans = (ans+cur+P)%P;}
            }
            printf("%lld\n",ans);
        }
    }
    
    namespace Solution2
    {
        #define U ((1<<m)-1)
        const int M = 14;
        llong dp[N+3][(1<<M)+3][N*M+3];
        bool ff[N+3][M+3];
        void update(llong &x,llong y) {x = (x+y)%P;}
        void solve()
        {
            llong ans = 0ll;
            dp[m-1][0][0] = 1ll;
            for(int i=m-1; i<n; i++)
            {
                for(int j=0; j<(1<<m); j++)
                {
                    bool okk = true;
                    for(int k=0; k<m; k++) if((j&(1<<k)) && ok[i-k-1]==false) {okk = false; break;}
                    if(!okk) continue;
                    int p = 0;
                    for(int k=0; k<m; k++)
                    {
                        if(j&(1<<k))
                        {
                            for(int l=0; l<m; l++)
                            {
                                ff[i-k-1-m+1+l][a[l]-96] = true;
                            }
                        }
                    }
                    for(int l=0; l<m; l++)
                    {
                        if(ff[i-m+1+l][a[l]-96]==false)
                        {
                            p++;
                        }
                    }
                    for(int k=0; k<m; k++)
                    {
                        if(j&(1<<k))
                        {
                            for(int l=0; l<m; l++)
                            {
                                ff[i-k-1-m+1+l][a[l]-96] = false;
                            }
                        }
                    }
                    for(int k=0; k<=n*m; k++)
                    {
                        if(dp[i][j][k]==0) continue;
                        update(dp[i+1][(j<<1)&U][k],dp[i][j][k]);
                        update(dp[i+1][(j<<1|1)&U][k+p],P-dp[i][j][k]);
                        dp[i][j][k] = 0ll;
                    }
                }
            }
            for(int i=1; i<=n*m; i++)
            {
                llong coe = 0ll;
                for(int j=1; j<=i; j++)
                {
                    llong tmp = s*inv[j]%P*comb(i,j)%P;
                    if(j&1) {coe = (coe-tmp+P)%P;}
                    else {coe = (coe+tmp)%P;}
                }
                llong sum = 0ll;
                for(int j=0; j<(1<<m); j++)
                {
                    sum = (sum+dp[n][j][i])%P;
                    dp[n][j][i] = 0ll;
                }
                ans = (ans+sum*coe)%P;
            }
            printf("%lld\n",ans);
        }
    }
    
    int main()
    {
        fact[0] = 1ll; for(int i=1; i<=2000000; i++) fact[i] = fact[i-1]*i%P;
        finv[2000000] = quickpow(fact[2000000],P-2); for(int i=1999999; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;
        for(int i=1; i<=2000000; i++) inv[i] = finv[i]*fact[i-1]%P;
        cnt[0] = 0; for(int i=1; i<(1<<17); i++) cnt[i] = cnt[i>>1]+(i&1);
        int T; scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&n,&m); s = 0;
            for(int i=0; i<n; i++)
            {
                scanf("%s",str); int l = strlen(str);
                for(int j=0; j<l; j++)
                {
                    f[i][str[j]-96] = true; s++;
                }
            }
            scanf("%s",a); bool exist = false;
            for(int i=m-1; i<n; i++)
            {
                ok[i] = true;
                for(int j=0; j<m; j++)
                {
                    if(f[i-m+1+j][a[j]-96]==false) {ok[i] = false; break;}
                }
                if(ok[i]) {exist = true;}
            }
            if(exist==false) {printf("-1\n");}
            else
            {
                if(n-m<=16)
                {
                    Solution1::solve();
                }
                else
                {
                    Solution2::solve();
                }
            }
            for(int i=0; i<n; i++)
            {
                for(int j=1; j<=S; j++) f[i][j] = false;
                ok[i] = false;
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/suncongbo/p/11027093.html

[http_uoj.ac_problem_214]: http://uoj.ac/problem/214