合唱队形[uoj214]

发表于 分类于

题目链接

uoj

题解

可以说这道题超级超级毒瘤了。

刚开始还以为 $n,m\leq 30$ 是折半搜索，谁知道是这么毒瘤的。

既然 $n,m\leq 30$ 暂时看起来不可做，那就先试试80pts的部分分吧。

首先直接统计显然不可做。设这些长度为 $m$ 的集合为 $S$，现在需要统计的是最小值的期望。

由Min-Max容斥得到：

$$E(\min(S))=\sum_{T\not =\varnothing,T\in S}(-1)^{|T|-1}E(\max(T))$$

那么设 $g(T)$ 表示要使得 $T$ 集合中的点满足条件需要多少个覆盖，设总覆盖数为 $s$，那么现在需要求在 $s$ 个覆盖中，每次随机选择一个，问第一次出现 $T$ 集合中所有数时的期望次数。

然后你就可以枚举 $t$，表示当操作次数 $\leq t$ 时已经全部覆盖的期望。

还是容斥一下，枚举至少有 $i$ 个数没覆盖，那么就有：

$$ans=\sum_{T=\varnothing,T\in S}(-1)^{|T|-1}\sum_{t=0}^{\infty}\sum_{i=0}^{g(T)}(-1)^{i-1}\binom{g(T)}{i}(\frac{s-i}{s})^t$$

把 $t$ 移过去，化简得到：

$$ans=\sum_{T=\varnothing,T\in S}(-1)^{|T|-1}\sum_{i=0}^{g(T)}(-1)^{i-1}\binom{g(T)}{i}(\frac{s}{i})$$

时间复杂度 $O(2^{n-m+1}n)\sim O(2^{n-m+1}n^2)$。

这样子就有 80分了。也就只想到这里了。

可以发现，一旦 $g(T)$ 知道是多少了，那么也就可以算了。

因此转换为统计使得 $g(T)=j$ 的集合 $T$ 的 $(-1)^{|T|-1}$ 的和。

而对于一个点而言，他需要学哪些字母是由前面 $m$ 个点所决定的，如果前面 $m$ 个点中某个点 $i$ ，满足 $[i,i+m-1]$ 在 $T$ 中，那么这个点就需要选择对应的字母。

根据这个性质，状压DP即可。

时间复杂度 $O(2^mn^3)$。

跟前一个算法结合就可以100分了。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}

int n,m,ss;
bool bo[31][31],b[31];
char t[31];
ll fac[905],inv[905],s[905];
inline ll C(int n,int m) {return fac[n]*inv[m]%mod*inv[n-m]%mod;}
namespace Part1{
    ll ans;
    bool vis[31][31];
    inline ll work()
    {
        ans=0;
        int w=n-m+1,cnt=1<<w;
        fo(sta,0,cnt-1)
        {
            bool flag=1; int sum=0,tim=0;
            fo(j,1,n) fo(k,0,25) vis[j][k]=0;
            fo(j,0,w-1)
                if((1<<j)&sta)
                {
                    if(!b[j]) flag=0;
                    tim++;
                    fo(k,1,m)
                    {
                        if(!vis[j+k][t[k]-'a']) sum++;
                        vis[j+k][t[k]-'a']=1;
                    }
                }
            if(!flag) continue;
            ans=Add(ans,Mul(Pow(mod-1,tim),s[sum]));
        }
        return ans;
    }
}
namespace Part2{
    ll g[1<<12],f[2][1<<12][905],ans;
    inline ll work()
    {
        ans=0;
        int cnt=1<<m,w=n-m+1,d=0,tot=(1<<(m-1));
        memset(f,0,sizeof(f));
        fo(sta,0,cnt-1)
        {
            g[sta]=0;
            fo(i,1,m) if((1<<(i-1))&sta) g[sta]|=(1<<(t[i]-'a'));
            g[sta]=__builtin_popcount(g[sta]);
        }
        f[d=0][0][0]=1;
        fo(i,1,n)
        {
            d=1-d;
            memset(f[d],0,sizeof(f[d]));
            fo(sta,0,tot-1)
                fo(j,0,i*m)
                    if(f[1-d][sta][j])
                    {
                        (f[d][(sta<<1)&(tot-1)][j+g[sta<<1]]+=f[1-d][sta][j])%=mod;
                        if(b[i-1]) (f[d][(sta<<1|1)&(tot-1)][j+g[sta<<1|1]]+=mod-f[1-d][sta][j])%=mod;
                    }
        }
        fo(j,0,w*m)
            ans=Add(ans,Mul(f[d][0][j],s[j]));
        return ans;
    }
}
inline void init(int n)
{
    fac[0]=1;
    fo(i,1,n) fac[i]=fac[i-1]*i%mod;
    inv[n]=Pow(fac[n],mod-2);
    fd(i,n,1) inv[i-1]=inv[i]*i%mod;
}
int main()
{
    init(900);
    CASET
    {
        n=read(); m=read(); ss=0;
        fo(i,1,n)
        {
            scanf("%s",t+1);
            fo(j,1,strlen(t+1)) bo[i][t[j]-'a']=1;
            ss=ss+strlen(t+1);
        }
        fo(i,0,n*m)
        {
            s[i]=0;
            fo(j,1,i) s[i]=Add(s[i],Mul(Pow(mod-1,j),Mul(C(i,j),Pow(j,mod-2))));
            s[i]=Mul(s[i],ss);
        }
        scanf("%s",t+1);
        int w=n-m+1;
        bool flag=0;
        fo(i,0,w-1)
        {
            b[i]=1;
            fo(j,1,m) if(!bo[i+j][t[j]-'a']) {b[i]=0; break;}
            flag|=b[i];
        }
        if(!flag) printf("-1\n");
        else printf("%lld\n",(n-m)<=18?Part1::work():Part2::work());
        fo(i,1,n) fo(j,0,25) bo[i][j]=0;
        fo(i,0,w-1) b[i]=0;
    }
    return 0;
}