题解 CF1185G2 【Playlist for Polycarp (hard version)】
Purple_wzy
·
·
题解
CF1185G2 Playlist for Polycarp
题面
英文题面
题意：有n首歌，每首歌有时间t_i，类型g_i。你需要选出若干首歌并将他们排成一排，满足相邻两首歌的类型不能相同，所有歌的时间总和为T。求方案数。
题解：我们可以考虑先将两个限制分开考虑，然后再尝试合并。
先考虑第二个限制。设$a_{i,t}$表示第一种歌用了$i$个，总时长为$t$的方案数，$b_{i,j,t}$表示第二种、第三种歌分别选了$i$，$j$个，总时长为$t$的方案数。转移时就用01背包的转移方式即可。时间复杂度是$O(n^3 \times T)$的。
再考虑第一个限制。设$f_{i,j,k,l}$表示三种歌各选了$i,j,k$次，最后一个选的是$l$的方案数。转移就每次枚举往序列最后放哪个数即可。时间复杂度是$O(n^3)$的。
最后考虑将它们合并。我们枚举$i,j,k,t$，表示三种歌各选了$i,j,k$个，其中第一种歌的总时间是$t$。那么方案数为：
$$a_{i,t} \times b_{j,k,T-t} \times i! \times j! \times k! \times f_{i,j,k,0/1/2}$$
累加一下就是答案了。
时间复杂度：$O(n^3 \times T)$，常数非常小，可以通过本题。
代码：
```c++
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int Mod=1e9+7,N=55,M=2550;
int n,m,T,ans,fac[N],sum[3],cnt[3],t[N],s[N],a[N][M],b[N][N][M],f[N][N][N][4];
I add(int &x,int y){(x+=y)>=Mod?x-=Mod:0;}
IN Plus(int x,int y){(x+=y)>=Mod?x-=Mod:0;return x;}
int main(){
read(n);read(T);
F(i,1,n)read(t[i]),read(s[i]),s[i]--;
fac[0]=1;F(i,1,n)fac[i]=(ll)fac[i-1]*i%Mod;
a[0][0]=1;b[0][0][0]=1;
F(j,1,n){
cnt[s[j]]++;sum[s[j]]+=t[j];
if(s[j]==1)FOR(i,cnt[1],1)FOR(k,cnt[2],0)FOR(l,sum[1]+sum[2],t[j])add(b[i][k][l],b[i-1][k][l-t[j]]);
else if(s[j]==2)FOR(i,cnt[1],0)FOR(k,cnt[2],1)FOR(l,sum[1]+sum[2],t[j])add(b[i][k][l],b[i][k-1][l-t[j]]);
else FOR(i,cnt[0],1)FOR(k,sum[0],t[j])add(a[i][k],a[i-1][k-t[j]]);
}
if(cnt[0])f[1][0][0][0]=1;if(cnt[1])f[0][1][0][1]=1;if(cnt[2])f[0][0][1][2]=1;
F(s,2,n)F(i,0,min(cnt[0],s))F(j,0,min(cnt[1],s-i)){
re k=s-i-j;if(k>cnt[2])continue;
if(i)add(f[i][j][k][0],f[i-1][j][k][1]),add(f[i][j][k][0],f[i-1][j][k][2]);
if(j)add(f[i][j][k][1],f[i][j-1][k][0]),add(f[i][j][k][1],f[i][j-1][k][2]);
if(k)add(f[i][j][k][2],f[i][j][k-1][0]),add(f[i][j][k][2],f[i][j][k-1][1]);
}
F(i,0,cnt[0])F(j,0,cnt[1])F(k,0,cnt[2])f[i][j][k][3]=Plus(f[i][j][k][0],Plus(f[i][j][k][1],f[i][j][k][2]));
ans=0;
F(l,0,T)F(i,0,cnt[0]){
if(!a[i][l])continue;
F(j,0,cnt[1])F(k,0,cnt[2])if(b[j][k][T-l])add(ans,(ll)a[i][l]*b[j][k][T-l]%Mod*fac[i]%Mod*fac[j]%Mod*fac[k]%Mod*f[i][j][k][3]%Mod);
}
printf("%d",ans);
return 0;
}
```