P9131 [USACO23FEB] Problem Setting P 题解
IamZZ
·
·
题解
P组练习总结#3
题目大意
FJ 为 USACO 贡献了 n(n\leq10^5) 道题来恶心选手们，他也聘请了 m(m\leq20) 位验题人（怕不是奶牛，不然怎么出这么离谱）。
每一位验题人对 n 道题目都有一个难度评定（两种之一），E 和 H，代表题目简单或者困难。
如今，FJ 立志于出一场比赛，他需要选择几道题组合一下（不能不选），选出来的题可以任意排列。
排列后，需要满足一个条件：如果一个验题人觉得第 i 道题难，他也必须觉得 i+1 题难，相当于这个验题人认为这个排列的难度递增咯（怪良心的）。
现在 FJ 想要知道有多少套题可以满足条件，答案可能很大，对 10^9+7 取模。
题解思路（部分分）
这次我们一步步来，先从部分分入手。
这种题目，我们应该想到状态压缩 DP，考虑状压每一道题验题人对它的态度。
`H` 视为 1，`E` 反之，这样我们就压缩出了 $n$ 个长度为 $m$ 的 01 串，经过这样的转换，我们考虑限制条件怎样变化了。
首先，题目难度递增，我们发现，这个在 01 串上也表现为单调递增，因此 DP 可行。
而且，相同值的题可以放在一起处理，他们之间没有区别，因此我们统计每个值的个数 $c_i$。
至于另一个限制条件，我们设选取了 $p_1,p_2,p_3\dots sp_c$ 号题，依次排列，而第 $i$ 道题状压后的值为 $w_i$，则需要满足 $w_{p_i}\operatorname{and} w_{p_{i+1}}=w_{p_i}$。
观察可知，觉得 $p_i$ 难的人是觉得 $p_{i+1}$ 难的人的子集（部分分做法遍历子集时使用的方法很新，很高效）。
好了，有了这些条件，我们可以开始我们的 DP 了：
设 $f_i$ 为当前选中最后一道题为 $i$ 时的方案数。
首先，我们要找到上一次选择的最后一道题 $j$，统计 $v=1+\sum_{j\operatorname{and}i=i,j\neq i}f_j$（$+1$ 是因为可以选择直接作为开头）。
而当前的 $i$ 有多少种排列方式？我们可以从 $c_i$ 个中选择任意（不为 0）个，并任意排列，计算 $s=\sum_{i=0}^{c_i-1}\frac{c_i!}{i!}$，暴力算就好。
有了这些，我们已经可以看出来 $f_i$ 的转移方程了吧？没错，就是 $f_i=v\times s$，最后的答案将所有的 $f_i$ 加在一起即可。
### 参考代码（部分分）
真觉得遍历子集挺妙的……
```c++
#include<bits/stdc++.h>//60pts
using namespace std;
const int N=1e5+5,M=1<<20,d=1e9+7;
int n,m,a[N],f[M],v,s[N]={1},t[N],c[M],ans;
char ch[N];
int quickpow(int b,int p)
{
int w=1;
while(p)
{
if(p&1)
w=1ll*w*b%d;
b=1ll*b*b%d;
p=p>>1;
}
return w;
}
int calc(int p)
{
int i,v=0;
for(i=0;i<=p-1;++i)
v=(v+1ll*s[p]*t[i]%d)%d;
return v;
}
void init()
{
int i;
for(i=1;i<=n;++i)
s[i]=1ll*s[i-1]*i%d;
t[n]=quickpow(s[n],d-2);
for(i=n;i;--i)
t[i-1]=1ll*t[i]*i%d;
return ;
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
init();
for(i=1;i<=m;++i)
{
scanf("%s",ch+1);
for(j=1;j<=n;++j)
a[j]=a[j]|(ch[j]=='H'?1<<i-1:0);
}
for(i=1;i<=n;++i)
++c[a[i]];
f[0]=calc(c[0])%d;
ans=f[0];
for(i=1;i<1<<m;++i)
{
v=1;
for(j=i;j>=0;j=(j-1)&i)
{
if(j==i)
continue;
v=(v+f[j])%d;
if(!j)
break;
}
f[i]=1ll*v*calc(c[i])%d;
ans=(ans+f[i])%d;
}
printf("%d",ans);
return 0;
}
```
### 题解思路（正解）
但是，如你所见，上面的代码是不够优秀的。
考虑如何优化，现在我们转移的复杂度太慢了，导致最后有一个约为 $\Theta(3^m)$ 的总复杂度，无法通过全部测试点。
转移太慢，我们就把一部分工作分给前面的求值，提前把答案准备好了，优化时间复杂度，就快起来了不是吗？
是的，因此我们要引入辅助数组 $g_{i,j}$！
$g_{i,j}$ 代表当前状态为 $i$，$\sum_{k\operatorname{and}i=k,k\oplus i<2^{j}}f_k$ 的值，很抽象，是吧？
我来解释一下，找到那些题 $k$ 并求和，这些题 $k$ 满足是 $i$ 的子集且对 $k$ 和 $i$ 有不同意见的验题人最大编号恰好为 $j-1$，注意，是最大的**恰好**等于。
这样我们就可以用 $\Theta(m)$ 的复杂度实现来自 $f_i$ 子集的转移，只需要枚举最大不同的编号就可以全部统计了！
当然 $g_{i,j}$ 也有自己的转移，如下：
$g_{i,0}=f_i$，毕竟没有区别的也只有自己啦~
若 $i$ 的第 $j-1$ 位是 0，$g_{i,j}=g_{i,j-1}$，否则 $g_{i,j}=g_{i,j-1}+g_{i-2^{j-1},j-1}$，这个还比较好理解，一步步转移就好了。
这边处理也需要 $\Theta(m)$，但是我们已经成功将总复杂度分担之后降到了 $\Theta(m\times2^m)$！这已经足够通过这道题了（记得取模）。
完结撒花(●'◡'●)！
### 参考代码（正解）
```c++
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1<<20,d=1e9+7;
int n,m,a[N],f[M],v,s[N]={1},t[N],c[M],ans,g[M][21];
char ch[N];
int quickpow(int b,int p)
{
int w=1;
while(p)
{
if(p&1)
w=1ll*w*b%d;
b=1ll*b*b%d;
p=p>>1;
}
return w;
}
int calc(int p)//计算同一个值中的排列方式
{
int i,v=0;
for(i=0;i<=p-1;++i)
v=(v+1ll*s[p]*t[i]%d)%d;
return v;
}
void init()
{
int i;
for(i=1;i<=n;++i)
s[i]=1ll*s[i-1]*i%d;
t[n]=quickpow(s[n],d-2);
for(i=n;i;--i)
t[i-1]=1ll*t[i]*i%d;
return ;
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
init();
for(i=1;i<=m;++i)
{
scanf("%s",ch+1);
for(j=1;j<=n;++j)
a[j]=a[j]|(ch[j]=='H'?1<<i-1:0);
}
for(i=1;i<=n;++i)
++c[a[i]];
f[0]=calc(c[0])%d;
for(i=1;i<=m;++i)
g[0][i]=f[0];
ans=f[0];
for(i=1;i<1<<m;++i)
{
v=1;
for(j=1;j<=m;++j)//f[i]的转移
{
if(i&(1<<j-1))//枚举最大的位数
v=(v+g[i^(1<<j-1)][j])%d;
}
f[i]=1ll*v*calc(c[i])%d;
ans=(ans+f[i])%d;
g[i][1]=f[i];
for(j=1;j<m;++j)//g[i][j]的转移
{
g[i][j+1]=g[i][j];
if(i&(1<<j-1))
g[i][j+1]=(g[i][j+1]+g[i^(1<<j-1)][j])%d;
}
}
printf("%d",ans);
return 0;
}
```