题解：P17707 [ICPC 2019 Nanjing R] Space Station

心灵震荡 · 2026-11-13 08:10:30 · 题解

先把 a_i = 0 的拿出来单独处理贡献，它们可以在任意时刻被选，且不会产生任何影响。显然贡献是 {n \choose cnt_0} \times cnt_0!。

对剩下的部分，直接暴力 DP，维护一个 50 维的状态即可。只要当前选数的总和超过 50，后面就可以用阶乘快速计算了，不需要继续转移。

因此合法状态数是 P(50) 种，常数小的话可以通过。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, mod = 1e9 + 7;
int cnt[N], ans, a[N], n, fac[N], ifac[N];

struct node
{
    int x;
    vector<int> cs;

    bool operator < (const node &nd) const
    {
        if(x != nd.x) return x < nd.x;
        return cs < nd.cs;
    }

    bool operator == (const node &nd) const
    {
        return x == nd.x && cs == nd.cs;
    }
};

map<node, int> f, nf;

inline int ksm(int x, int y)
{
    int res = 1;
    while(y)
    {
        if(y & 1) res = 1ll * res * x % mod;
        y >>= 1, x = 1ll * x * x % mod;
    }
    return res;
}

inline int C(int n, int m)
{
    return 1ll * fac[n] * ksm(fac[m], mod - 2) % mod * ksm(fac[n - m], mod - 2) % mod;
}

signed main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    for(int i = 0; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cnt[a[i]]++;
    vector<int> st; st.resize(51);
    for(int i = 1; i <= 30; i++) st[i] = 0;

    f[(node){a[0], st}] = 1;

    int sum = n - cnt[0];   
    for(int dep = 1; dep <= sum; dep++)
    {
        nf.clear();
        for(auto &p : f)
        {
            auto u = p.first; int val = p.second;
            for(int i = 1; i <= u.x; i++)
            {
                if(u.cs[i] == cnt[i]) continue;

                int cs = u.cs[i];
                if(u.x + i >= 50)
                {
                    int vs = 1ll * val * (cnt[i] - cs) % mod;
                    ans += 1ll * vs * fac[sum - dep] % mod, ans %= mod;
                    continue;
                }
                node v = u;
                v.cs[i]++;
                v.x = u.x + i;
                nf[v] += 1ll * val * (cnt[i] - cs) % mod, nf[v] %= mod;
            }
        }       
        f = nf;
    }

    for(auto p : f)
    {
        node u = p.first;
        int val = p.second;
        ans += val;
        if(ans >= mod) ans -= mod;
    }


    cout << 1ll * ans * C(n, cnt[0]) % mod * fac[cnt[0]] % mod;
    return 0;
}