题意：有(n)首歌，每首歌有时间(t_i)，类型(g_i)。你需要选出若干首歌并将他们排成一排，满足相邻两首歌的类型不能相同，所有歌的时间总和为(T)。求方案数。
(n leq 50,T leq 2500,t_i leq 50,1 leq g_i leq 3)。
题解：我们可以考虑先将两个限制分开考虑，然后再尝试合并。
先考虑第二个限制。设(a_{i,t})表示第一种歌用了(i)个，总时长为(t)的方案数，(b_{i,j,t})表示第二种、第三种歌分别选了(i)，(j)个，总时长为(t)的方案数。转移时就用01背包的转移方式即可。时间复杂度是(O(n^3 imes T))的。
再考虑第一个限制。设(f_{i,j,k,l})表示三种歌各选了(i,j,k)次，最后一个选的是(l)的方案数。转移就每次枚举往序列最后放哪个数即可。时间复杂度是(O(n^3))的。
最后考虑将它们合并。我们枚举(i,j,k,t)，表示三种歌各选了(i,j,k)个，其中第一种歌的总时间是(t)。那么方案数为：
[a_{i,t} imes b_{j,k,T-t} imes i! imes j! imes k! imes f_{i,j,k,0/1/2}
]
累加一下就是答案了。
时间复杂度：(O(n^3 imes T))，常数非常小，可以通过本题。
代码：
#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;
}