跳转至

251127 模拟赛

T1

多次询问 \(n\)，问有多少个转置相同的 01 阶梯矩阵，满足其所有位置的和为 \(n\)。

\(n,T\le 10^5\)

枚举中心矩形的边长（即主对角线上的极长 \(1\) 前缀），剩下的部分是一个分拆数。由于边长是根号级别，因此分拆数只需预处理前 \(\sqrt n\) 列即可。

热知识：最大 \(k\) 分拆数与 \(k\) 部分拆数相同，均为 \(p(n,k)\)。

T2

分块练习题

T3

给定一棵无根树，设全集 \(U=\{1,2,\cdots,k\}\)，每个点有一个值域为 \(U\) 的幂集的点权 \(a_u\)，且 \(a_u\) 非空。定义一个点集 \(S\) 的代价为

\[ w\Biggl(\Biggl|\bigcup_{i\in tr(S)}a_i\Bigg|\Bigg) \]

其中 \(w_{1\sim k}\) 是给定的序列，\(tr(S)\) 表示点集 \(S\) 的最小斯坦纳树（集合内点两两路径的并）。

定义点集 \(V\) 的一组划分 \(S_1,S_2,\cdots S_k\) 的代价为各个点集的代价之和。称两组划分不同当且仅当存在两个点在第一组划分中在同一个集合中，而在第二组中不在。求所有本质不同划分的代价之和。

\(n\le 5000,~k\le 10\)

考虑把贡献拆到每一个点集上。对于点集 \(S\)，贡献为 \(w\times Bell(n-|S|)\)。考虑 \(2^k\) 枚举 \(t=\bigcup_{i}a_i\)，问题转化为求满足条件的 \(S\) 的 \(Bell(n-|S|)\) 之和。发现恰好的限制不易满足，跑一遍 FMT 转化成枚举 \(t\) 然后计数 \(\bigcup_{i}a_i\subseteq t\) 的贡献，最后一遍 iFMT 求出恰好为 \(t\) 的贡献之和。

发现对于一个 \(t\)，满足 \(a_i\subseteq t\) 的 \(i\) 形成若干连通块。一个大小为 \(m\) 的连通块的代价为

\[ \sum_{i=1}^{m}\binom{m}{i}Bell(n-i) \]

于是先将上式预处理，然后每次 \(O(n)\) 扫一遍，把所有连通块的贡献全都加起来即可。贝尔数可以 \(O(n^2)\) 预处理。时间复杂度 \(O(n2^k+n^2)\)。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include<iostream>
#define ll long long
using namespace std;
const int N = 5010;
const int K = 10;
const int MOD = 1e9 + 7;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, k;
int bell[N], f[N];
int a[N], w[K + 2];

ll inv[N], fact[N], ifact[N];
inline ll C(int a, int b) {
    return fact[a] * ifact[a - b] % MOD * ifact[b] % MOD;
}

int ans;
int g[1 << K];
bool vis[N];

int mask;
int dfs(int u, int fa) {
    int res = 1;
    vis[u] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa || (a[v] | mask) != mask) continue;
        res += dfs(v, u);
    }
    return res;
}

int main() {

    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    inv[1] = fact[0] = ifact[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;

    bell[0] = 1;
    for(int i = 1; i < N; i++) {
        for(int j = 0; j <= i - 1; j++) {
            add(bell[i], bell[i - j - 1] * C(i - 1, j) % MOD);
        }
    }

    cin >> n >> k;
    for(int i = 1; i <= k; i++) cin >> w[i];
    for(int i = 1; i <= n; i++) {
        int t; cin >> t;
        while(t--) {
            int x; cin >> x;
            a[i] |= (1 << x - 1);
        }
    }
    for(int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            add(f[i], C(i, j) * bell[n - j] % MOD);
        }
    }

    for(int i = 0; i < (1 << k); i++) {
        mask = i;
        for(int j = 1; j <= n; j++) vis[j] = 0;
        for(int j = 1; j <= n; j++) {
            if(!vis[j] && (a[j] | mask) == mask) add(g[i], f[dfs(j, 0)]);
        }
    }

    for(int i = 0; i < k; i++) {
        for(int j = 0; j < (1 << k); j++) {
            if(j & (1 << i)) add(g[j], MOD - g[j ^ (1 << i)]);
        }
    }
    for(int i = 0; i < (1 << k); i++) {
        add(ans, (ll)w[__builtin_popcount(i)] * g[i] % MOD);
    }

    cout << ans << '\n';

    return 0;
}