CF1185G2 Playlist for Polycarp (hard version) 题解

题目链接：Playlist for Polycarp (hard version)

题意：

你现在正在选择歌曲。现在共有 \(n\) 首歌，每首歌有一个时长 \(t_i\) 和一个编号 \(g_i\) 。

您需要求出有多少种选出若干首歌排成一排的方案，

使得任意相邻两首歌的编号不同，且所有歌的时长和恰好为 \(T\) 。

输入格式

第一行是两个整数 \(n,t ~(1\le n\le 50,1\le T\le 2500)\)。

接下来 \(n\) 行，每行两个正整数 \(t_i , g_i\) ，表示第 \(i\) 首歌曲的时长和编号。\((1\le t_i\le 50,1\le g_i\le 3)\)

输出格式

输出一个整数表示方案数。答案对 \(10^9 + 7\) 取模。

注意到歌总共就三种，考虑提前 dp 出一些有用的东西方便后面合并。

设 \(a_{i,t}\) 为第一种歌用了 \(i\) 次，总时长为 \(t\) 的方案数。

设 \(b_{i,j,t}\) 为第二种、第三种歌分别用了 \(i,j\) 次，总时长为 \(t\) 的方案数。

这俩都可以用类似 01 背包的形式转移，转移方程就不写了，这里复杂度 \(\mathcal{O}(n^3T)\) 。

设 \(f_{i,j,k,l}\) 为这三种歌分别用了 \(i,j,k\) 次，最后一个选的是第 \(l\) 种的方案数。转移略，这里是 \(\mathcal{O}(n^3)\) 的。

最后把他们合并起来，考虑枚举歌用了 \(i,j,k\) 次，第一种歌时间为 \(t\) ，那么答案就是 \[ \mathrm{Ans} = \sum_{i,j,k,t} i!\ j!\ k!\ a_{i,t}\ b_{j,k,T-t}\left(\sum_{0 \le l \le 2} f_{i,j,k,l}\right) \] 时间复杂度 \(\mathcal{O}(n^3T)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(55))
#define M ((int)(3e3 + 15))

int sum[N], cnt[N], fac[N], t[N], s[N], a[N][M], b[N][N][M], f[N][N][N][4];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, T; cin >> n >> T;
    rep(i, 1, n) { cin >> t[i] >> s[i], --s[i]; }
    fac[0] = 1; rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    a[0][0] = 1; b[0][0][0] = 1;
    rep(j, 1, n)
    {
        ++cnt[s[j]]; sum[s[j]] += t[j];
        if(s[j] == 1) {
            Rep(i, cnt[1], 1) Rep(k, cnt[2], 0) 
                Rep(l, sum[1] + sum[2], t[j]) { add(b[i][k][l], b[i - 1][k][l - t[j]]); }
        }else if(s[j] == 2) {
            Rep(i, cnt[1], 0) Rep(k, cnt[2], 1)
                Rep(l, sum[1] + sum[2], t[j]) { add(b[i][k][l], b[i][k - 1][l - t[j]]); }
        }else {
            Rep(i, cnt[0], 1) Rep(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;
    rep(s, 2, n) rep(i, 0, min(cnt[0], s)) rep(j, 0, min(cnt[1], s - i))
    {
        const int 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]); }
    }
    rep(i, 0, cnt[0]) rep(j, 0, cnt[1]) rep(k, 0, cnt[2])
        f[i][j][k][3] = (f[i][j][k][0] + f[i][j][k][1] + f[i][j][k][2]) % mod;
    int res = 0;
    rep(l, 0, T) rep(i, 0, cnt[0]) if(a[i][l] > 0) {
        rep(j, 0, cnt[1]) rep(k, 0, cnt[2]) if(b[j][k][T - l] > 0) {
            add(res, a[i][l] * b[j][k][T - l] % mod * fac[i] % mod * fac[j] % mod * fac[k] % mod * f[i][j][k][3] % mod);
        }
    }
    cout << res << '\n';
    return 0;
}