Fork me on GitHub

Uoj#214.【UNR 1】合唱队形

Uoj#214.【UNR #1】合唱队形 题解

题意:

  • 有$n$个小朋友要教唱歌,每个小朋友可能会学某一些音,每一秒发生的所有事件都是等概率的(包括已经发生的),事件即某个小朋友学(会)了某个音。问连续的一段长度为$m$的区间的小朋友会唱一段歌的期望事件。
  • $1\le m\le n\le 30$

题解:

  • 参考的大佬的博客地址
  • 首先考虑一个问题:如果总共有$sum$,需要完成其中的$k$个课程的期望事件是:
  • 长度为$m$的区间有$n−m+1$个,考虑枚举这些区间的完成情况,通过容斥计算贡献。
  • 设$f_t$表示事件$t$之前任务没有完成的概率。
  • 设$p_{S,t}$ 表示事件$t$之前区间集合$S$未被完成的概率。
  • 则可以知道:
  • 这个我们考虑复杂度,发现他是一个$O(2^{n−m+1}n^2)$的复杂度,似乎并不能怎么样。
  • 但是当$n,m$较为接近时,这个算法还是比较靠谱的。
  • 当$n−m$比较大时,我们考虑直接计算$F(k)$的贡献。
  • 这个应该是可以$dp$的。设$dp[i][j][k]$表示考虑到第$i$个小朋友,到现在为止他需要学的音的集合是$j$,已经需要发生$k$个事件的贡献。那么最后只要将$\sum_{j}dp[n][j][k]$乘上$F(k)$加入答案即可。
  • 初始状态$dp[0][0][0]=1$,转移方程分两种:
    • $i$这个点开始的区间不在集合$S$中:
    • $i$这个点开始的区间在集合$S$中(得是可以在):
  • 这样的复杂度是 $O(2^mn^3)$ 的。
  • 平衡两边复杂度后至少可以得到一个 $O(2^{\frac{n}{2}}n^3)$ 的做法,然后似乎就可以过了。

代码:

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
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define N 32
using namespace std;
int n,m,len[N],c[N],q[N],cnt,Ans,F[N*N],sum_len,inv[N*N],study[N][N],dp[2][1<<13][N*N];
int number[1<<13];
bool vis[N][N],ok[N],used[N];
char a[N][N],b[N];
void add(int &x,int y)
{
x=(x+y>=mod)?(x+y-mod):(x+y);
}
int main()
{
inv[1]=1;
for (int i=2;i<N*N;i++)
inv[i]=(ll)inv[mod%i]*(mod-mod/i)%mod;
for (int i=1;i<N*N;i++)
{
F[i]=0;
for (int j=0;j<i;j++)
F[i]=(F[i]+inv[i-j])%mod;
}
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin>>T;
while (T--)
{
sum_len=Ans=0;
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>a[i];
cin>>b;
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++)
{
len[i]=strlen(a[i]);
for (int j=0;j<len[i];j++)
vis[i][a[i][j]-'a']=1;
sum_len+=len[i];
}
for (int i=0;i<m;i++) c[i]=b[i]-'a';
cnt=0;
memset(ok,0,sizeof(ok));
for (int i=1;i<=n-m+1;i++)
{
ok[i]=1;
for (int j=0;j<m;j++)
if (!vis[i+j][c[j]])
{
ok[i]=0;
break;
}
if (!ok[i]) continue;
q[++cnt]=i;
}
if (cnt==0)
{
cout<<"-1\n";
continue;
}
if (n-m<=17)
{
for (int i=0;i<(1<<cnt);i++)
{
int size=0,num=0;
memset(study,0,sizeof(study));
for (int j=1;j<=cnt;j++)
if ((i>>(j-1))&1)
{
for (int k=q[j];k<q[j]+m;k++)
{
if (!study[k][c[k-q[j]]])
{
study[k][c[k-q[j]]]=1;
num++;
}
}
size++;
}
if (size&1) Ans=(Ans+(ll)F[num]*sum_len%mod)%mod;
else Ans=(Ans+mod-(ll)F[num]*sum_len%mod)%mod;
}
cout<<Ans<<"\n";
}
else
{
memset(number,0,sizeof(number));
for (int i=0;i<(1<<m);i++)
{
memset(used,0,sizeof(used));
for (int j=0;j<m;j++)
if (i>>j&1)
if (!used[c[j]]) used[c[j]]=1,number[i]++;
}
memset(dp,0,sizeof(dp));
int now=1,last=0;
dp[now][0][0]=1;
sum_len=0;
for (int i=1;i<=n;i++)
{
last=now,now^=1;
memset(dp[now],0,sizeof(dp[now]));
for (int j=0;j<(1<<m);j++)
for (int k=0;k<=sum_len;k++)
if (dp[last][j][k])
{
int nxt=(j<<1)&((1<<m)-1);
if (ok[i]) add(dp[now][nxt|1][k+number[nxt|1]],(mod-dp[last][j][k])%mod);
add(dp[now][nxt][k+number[nxt]],dp[last][j][k]);
}
sum_len+=len[i];
}
for (int i=1;i<=sum_len;i++)
{
int sum=0;
for (int j=0;j<(1<<m);j++)
add(sum,dp[now][j][i]);
add(Ans,(ll)sum*((ll)F[i]*sum_len%mod)%mod);
}
Ans=(mod-Ans)%mod;
cout<<Ans<<"\n";
}
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#214.【UNR 1】合唱队形

文章作者:wzf2000

发布时间:2018年01月26日 - 16:01

最后更新:2018年03月14日 - 18:03

原始链接:https://wzf2000.github.io/2018/01/26/Uoj214/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。