「一个人的桃花源」

文章最后更新时间为：2021 年 02 月 15 日 23:18:55

CTS/CTSC2019题解，只是象征性的选了几道计数题做，并不是完整的题解。

随机立方体

直接做好像不太星，考虑容斥。

设$f_i$表示至少有$i$个极大的数的方案数，$N = n \times m \times l$。则有：

$$ f_i=\binom{N}{g_i}b_i\times h_i\times (N - g_i)! $$

$b_i$表示选出$i$个三维坐标都不相同的点的方案数。($i$个极大的数)

$g_i$表示和$i$个极大的数中任意一个至少有一维坐标相同的点的个数。

$h_i$表示将$g_i$个数字分配给$g_i$的个点的合法分配的方案数。(合法指的是$i$个极大的数可以同时存在)

我们一个一个考虑。

考虑$b_i$怎么算：

你每选择出来一个点$(x_0,y_0,z_0)$并钦定它为极大的，$x=x_0,y=y_0,z=z_0$这三个平面上的点都不能再作为极大的点了，相当于立方体从$n \times m \times l$变成了$(n-1)\times (m-1)\times (l-1)$。所以显然有：

$$ b_i =\frac{1}{i!}\prod_{j=0}^{i-1}(n-j)\times(m-j)\times(l-j) $$

考虑$g_i$怎么算：

都知道$b_i$怎么算了，显然有

$$ g_i=n\times m\times l-(n-i)\times (m-i)\times (l-i) $$

考虑$h_i$怎么算：

设需要比第$i$个极大的点要小的点上数字集合为$S_i$，$a_i$表示第$i$个极大的点上的数字。

我们先钦定$i$个极大的点上的数字的大小关系。我们由数字从小到大的顺序依次考虑这个$i$个极大的点。考虑加入第$j$个极大的点后方案数的变化：

因为新加入极大的点$j$比已经加入的$j-1$个极大的点都要大，所以有：

$$ a[j] > k, \forall k\in {S_j{\large\cap} S_r}(r\in [1,j-1]) $$

所以我们只用考虑：$S_j$和前$j-1$极大的点的集合不交的部分。并且这部分和前$j-1$个极大的点的集合的交集没有明确的大小关系。设$S_i$和前$i-1$个集合的并集的不交部分的大小为$R$，则有：

$$ h_i=h_{i-1}\times \left(\left|{\large\cup}_{j=1}^{i-1}S_j\right|+1\right)^{\overline{R}} $$

PS：$x^{\overline{n}}$表示$x$的$n$次上升幂。

并且有$R=g_i-g_{i-1}-1, \left|{\large\cup}_{j=1}^{i-1}S_j\right| = g_i$。所以：

$$ \begin{aligned}h_i&=h_{i-1}\times (g_{i-1}+1)^{\overline{g_{i}-g_{i-1}}}\\&=h_{i-1} \times \frac{(g_i-1)!}{g_{i-1}!}\\&=\prod_{j=1}^i\frac{(g_{j}-1)!}{g_{j-1}!}\end{aligned} $$

记得最后我们对于$h_i$还要乘上$i$的阶乘，因为一开始我们钦定了大小顺序。

然后把所有的东西都代回去，则有：

$$ \begin{aligned}f_i&=\binom{N}{g_i}b_i\times i!\prod_{j=1}^i\frac{(g_j-1)!}{g_{j-1}!}\times (N - g_i)!\\&=\frac{N!}{(N-g_i)!g_i!}\times i!\prod_{j=1}^i\frac{(g_j-1)!}{g_{j-1}!}\times (N - g_i)!\times b_i\end{aligned} $$

发现我们最后算概率的时候要乘上$\frac{1}{N!}$并且式子的最后有一个$(N-g_i)!$，则有：

$$ \begin{aligned}f_i&=\frac{i!}{g_i!}\times \prod _{j=1}^i\frac{(g_j-1)!}{g_{j-1}!}\\&=i!\prod_{j=1}^i\frac{(g_j-1)!}{g_j!}\\&=i!\prod_{j=1}^i\frac{1}{g_j}\end{aligned} $$

最后二项式反演一下有：

$$ ans = \sum_{i=k}^{\min(n,m,l)}(-1)^{i-k}\binom{i}{k}f_i $$

然后有因为我们最多只能选出$\min(n,m,l)$个极大的点并且要求一个$g_i$的逆元，所以现在复杂度为$O(T\min(n,m,l)\log P)$。可以获得$80$分的好成绩....

然后这个地方我们有一个小$\text{trick}$：我们预处理出来$g_i$的前缀积，求最后一项的逆元后可以逆推每一个前缀积的逆元....就和逆推阶乘的逆元是一个道理。最终复杂度为$O(T\min(n,m,l))$。

代码：

/*
 * 3119.cpp
 * This file is part of 3119
 *
 * Copyright (C) 2019 - ViXbob
 *
 * 3119 is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * 3119 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with 3119. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * There is no end though there is a start in space. ---Infinity.
 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
 * Only the person who was wisdom can read the most foolish one from the history.
 * The fish that lives in the sea doesn't know the world in the land.
 * It also ruins and goes if they have wisdom.
 * It is funnier that man exceeds the speed of light than fish start living in the land.
 * It can be said that this is an final ultimatum from the god to the people who can fight.
 *
 * Steins;Gate
 */
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))
#define getd(i) (1ll * (n - (i)) * (m - (i)) % P * (l - (i)) % P)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 5e6 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
    char ch = getchar(); int u = 0, f = 1;
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
    while(isdigit(ch))  { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, m, l, k, N, T, c[maxn], g[maxn], h[maxn], f[maxn], ifac[maxn], fac[maxn], mn, b[maxn], pre[maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; }
inline int ksm(int x, int k, int rnt = 1) { 
    for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
    return rnt;
}

int main() {
//    freopen("1.in", "r", stdin);
//    freopen("my.out", "w", stdout);
    T = read(); fac[0] = 1;
    rep(i, 1, maxn - 1) fac[i] = 1ll * fac[i - 1] * i % P;
    ifac[maxn - 1] = inv(fac[maxn - 1]);
    dep(i, maxn - 2, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
    while(T--) {
        n = read(); m = read(); l = read(); k = read(); h[0] = 1; b[0] = 1; pre[0] = 1;
        N = n * m * l; mn = min(n, min(m, l));
//        rep(i, 1, mn) c[i] = (n - i + 1) * (m - i + 1) * (l - i + 1) - (n - i) * (m - i) * (l - i);
        rep(i, 1, mn) g[i] = pls(g[i - 1], dec(getd(i - 1), getd(i)));
        rep(i, 1, mn) pre[i] = 1ll * pre[i - 1] * g[i] % P;
            // g[i] = nml - (n - i) * (m - i) * (l - i)
            // 
        rep(i, 1, mn) b[i] = 1ll * b[i - 1] * getd(i - 1) % P;
//        rep(i, 1, mn) g[i] = g[i - 1] + getd(i - 1) - getd(i);
//        h[1] = fac[g[1] - 1];
//        rep(i, 1, mn) h[i] = 1ll * h[i - 1] * fac[g[i] - 1] % P * ifac[g[i - 1]] % P;
//        rep(i, 1, mn) f[i] = 1ll * b[i] * h[i] % P * fac[N - g[i]] % P * C(N, g[i]) % P;
//        rep(i, 1, mn) h[i] = 1ll * h[i - 1] * inv(g[i]) % P;
        pre[mn] = inv(pre[mn]);
        dep(i, mn, 1) pre[i - 1] = 1ll * pre[i] * g[i] % P;
        rep(i, 1, mn) f[i] = 1ll * b[i] * pre[i] % P;
        int ans = 0;
        rep(i, k, mn) if((i - k) & 1) ans = dec(ans, 1ll * C(i, k) * f[i] % P);
                else ans = pls(ans, 1ll * C(i, k) * f[i] % P);
        cout << 1ll * ans % P << endl;
    }
    return 0;
}

珍珠

这道题好像对不会生成函数的选手不太友好啊....(比如我)

设$cnt_i$表示第$i$种颜色的珠子的数量，那么就变成了求$\sum_{i=1}^D[cnt_i \bmod 2] \le n-2m$的序列的个数。然后这个显然可以$\text{dp}$，不过有两种：

第一种：

$f_{i,j,k}$表示考虑了前$i$种珠子一共选出了$j$个，为个数为奇数的珠子的种数为$k$的$\frac{1}{\prod_{j=1}^icnt_j}$的和。

最后答案直接就是：

$$ n!\sum_{i=0}^{n-2m}f_{D,n,i} $$

这个东西嘛，珠子显然都是等价的，转移又是个卷积，应该是可以多项式快速幂的。(我当时是这么想得，但是并不会处理后面的那个奇偶)

复杂度$O(D^3n)$。

第二种：

显然状态不需要这么暴力，设$f_{i,j}$表示选了$i$个珠子有$j$种珠子的个数为奇数的方案数。显然有转移：

$$ \begin{cases}f_{i,j} \times (D-j) \to f_{i+1,j+1}&j \le D\\f_{i,j} \times j \to f_{i+1,j-1}&j>0\end{cases} $$

复杂度$O(Dn)$，矩阵快速幂优化一下就是$O(D^3\log n)$。但我不懂$\text{laofu}$那档$D \le 300$的部分分是什么意思，考怎么卡常吗？

然后第二种$\text{dp}$好像就没什么优化空间了。然后我也就不会了。转战题解

到处学习了一下姿势发现第一种$\text{dp}$有很大的优化空间。

如果把第一种$\text{dp}$值搞成生成函数，那么转移显然就是卷上$e^x$。但是后面的奇偶的东西要容斥一下。

然后我们先了解一些神奇的$\text{EGF}$：

$$ e^{-x}=\sum_{i=0}^{\infin}(-1)^{i}\frac{x^i}{i!} $$

$$ \frac{e^{x}-e^{-x}}{2}=\sum_{i=0}^{\infin}\frac{x^{2i+1}}{(2i+1)!} $$

$$ \frac{e^{x}+e^{-x}}{2}=\sum_{i=0}^{\infin}\frac{x^{2i}}{(2i)!} $$

设$f_i$表示至少有$i$种珍珠的个数为奇数的$\frac{1}{\prod_{j=1}^icnt[j]}$的和。

设$g_i$表示恰好有$i$种珍珠的个数为奇数的$\frac{1}{\prod_{j=1}^icnt[j]}$的和。

则有：

$$ \begin{aligned}f_i&=\binom{D}{i}[x^n]\left(\frac{e^x-e^{-x}}{2}\right)^ie^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n](e^x-e^{-x})^ie^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{i-j}e^{jx}e^{(j-i)x}e^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{i-j}e^{(D-2(i-j))x}\end{aligned} $$

然后把里面的$j$设成$i-j$等式不变。

$$ f_i=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{j}e^{(D-2j)x} $$

然后现在又有一个神奇的$\text{EGF}$：

$$ e^{cx}=\sum_{i=0}^{\infin}c^i\frac{x^i}{i!} $$

又因为最后答案要乘上$n$的阶乘，我们现在先乘进去：

$$ \begin{aligned}f_i&=\frac{1}{2^i}\binom{D}{i}\sum_{j=0}^i\binom{i}{j}(-1)^j(D-2j)^n\\\frac{f_i}{i!}&=\frac{1}{2^i}\binom{D}{i}\sum_{j=0}^i\frac{(-1)^j(D-2j)^n}{j!}\frac{1}{(i-j)!}\end{aligned} $$

显然是个卷积的形式。

最后二项式反演一下有：

$$ \begin{aligned}g_i&=\sum_{j=i}^D(-1)^{j-i}\binom{j}{i}f_j\\g_i \times i!&=\sum_{j=i}^D\frac{(-1)^{j-i}}{(j-i)!}f_j\times j!\end{aligned} $$

然后我们把$g_i \times i!$和$f_i \times i!$都$\text{reverse}$一下就是一个卷积的形式了。最后答案为：

$$ \sum_{i=0}^{n-2m}g_i $$

复杂度为$O(D \log D)$。

PS ： 要先判一下$n - 2m < 0$和$n - 2m \ge D$的情况。

代码：

/*
 * 3120.cpp
 * This file is part of 3120
 *
 * Copyright (C) 2019 - ViXbob
 *
 * 3120 is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * 3120 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with 3120. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * There is no end though there is a start in space. ---Infinity.
 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
 * Only the person who was wisdom can read the most foolish one from the history.
 * The fish that lives in the sea doesn't know the world in the land.
 * It also ruins and goes if they have wisdom.
 * It is funnier that man exceeds the speed of light than fish start living in the land.
 * It can be said that this is an final ultimatum from the god to the people who can fight.
 *
 * Steins;Gate
 */
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 2;

inline int read() {
    char ch = getchar(); int u = 0, f = 1;
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
    while(isdigit(ch))  { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int D, n, m, ans, fac[maxn], ifac[maxn], f[maxn], g[maxn], ipow2[maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; }
inline int ksm(int x, int k, int rnt = 1) { 
    for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
    return rnt;
}

namespace NTT {
    const int G = 3, invG = inv(G);
    
    int s, l, rev[maxm], E[maxm], H[maxm], inv;
    
    inline void init(int n) {
        s = 2; l = 1;
        while(s <= n) s <<= 1, l++; inv = inv(s);
        rep(i, 0, s - 1) rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
        memset(E, 0, sizeof(int) * (s + 5));
        memset(H, 0, sizeof(int) * (s + 5));
    }
    
    inline void dft(int *a, int n, int f) {
        rep(i, 0, n - 1) if(i < rev[i]) swap(a[i], a[rev[i]]);
        for(int i = 1; i < n; i <<= 1) {
            int Wn = ksm(f, (P - 1) / (i << 1));
            for(int j = 0; j < n; j += (i << 1)) {
                int w = 1;
                for(int k = 0; k < i; k++, w = 1ll * w * Wn % P) {
                    int A1 = a[j + k], A2 = 1ll * w * a[j + k + i] % P;
                    a[j + k] = pls(A1, A2); a[j + k + i] = dec(A1, A2);
                }
            }
        }
    }
    
    inline void conv() {
        dft(E, s, G); dft(H, s, G);
        rep(i, 0, s - 1) E[i] = 1ll * E[i] * H[i] % P;
        dft(E, s, invG);
        rep(i, 0, s - 1) E[i] = 1ll * E[i] * inv % P;
    }
}

const int inv2 = inv(2);

int main() {
//    freopen("1.in", "r", stdin);
//    freopen("my.out", "w", stdout);
    D = read(); n = read(); m = read();
    if(n - 2 * m < 0) { cout << 0 << endl; return 0; }
    if(n - 2 * m >= D) { cout << ksm(D, n) << endl; return 0; }
    fac[0] = 1; ipow2[0] = 1;
    rep(i, 1, D) fac[i] = 1ll * fac[i - 1] * i % P, ipow2[i] = 1ll * ipow2[i - 1] * inv2 % P;
    ifac[D] = inv(fac[D]);
    dep(i, D - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
    
    NTT :: init(D << 1);
    for(int i = 0, ty = 1; i <= D; i++, ty = (ty == 1 ? P - 1 : 1))
        NTT :: E[i] = 1ll * ty * ksm(pls(D - 2 * i, P), n) % P * ifac[i] % P, NTT :: H[i] = ifac[i];
    NTT :: conv();
    rep(i, 0, D) f[i] = 1ll * ipow2[i] * fac[i] % P * C(D, i) % P * NTT :: E[i] % P;
    
    NTT :: init(D << 1);
    for(int i = 0, ty = 1; i <= D; i++, ty = (ty == 1 ? P - 1 : 1))
        NTT :: E[i] = 1ll * f[D - i] * fac[D - i] % P, NTT :: H[i] = 1ll * ty * ifac[i] % P;
    NTT :: conv();
    rep(i, 0, D) g[i] = 1ll * NTT :: E[D - i] * ifac[i] % P;
    rep(i, 0, n - 2 * m) ans = pls(ans, g[i]);
    cout << ans << endl;
    return 0;
}
/*
*/

无处安放

题答题先咕着...

田野

我是计算几何垃圾，只会凸包，告辞。

重复

做不动了，坑先挖着。顺便膜拜rqy。

氪金手游

一开始$\text{naive}$了，以为二元组$u_i \to v_i$连出来的一定是一颗外向树。后来发现有反边。

我索性先来考虑一下外向树的这种情况吧。对于第$i$个点设其子树的$w_i$和为$Sw$, 所有点的和为$Sum$。因为除了$i$子树中的点要比$i$晚抽到外，剩余所有的点都可比$i$早抽到。所以$i$比子树中的所有卡牌都要早抽到的概率为：

$$ \begin{aligned}&\frac{w_i}{Sum}\sum_{i=0}^n\left(\frac{Sum-Sw}{Sum}\right)^i\\=&\frac{w_i}{Sum}\times \frac{Sum}{Sw}=\frac{w_i}{Sw}\end{aligned} $$

这个只与子树信息有关。我们考虑设计状态$f_{i,j}$表示处理完$i$这个子树，子树中$w_i$和为$j$的概率和。转移直接背包就好了。

然后考虑反向边：

反向边我们不好直接处理，考虑容斥。反向边的若干个二元组就是一些条件而已我们想要它们都满足，直接大力容斥有：

至少$0$个条件不满足$-$至少一个条件不满足$+$至少两个条件不满足$-\cdots$

我们发现至少$i$个不满足就是选择任意$i$条反向边后将这些边反向，另外的边删掉(不考虑这些条件就是至少)。这样会构成一个外向树森林。我们枚举每一条反向边的状态后也可以$\text{dp}$，复杂度$O(2^nn^2)$。

考虑优化一下这个过程，我们其实没有必要知道是每条边具体的状态，我们只用考虑最后被反向的反向边的个数，我们直接把这个东西压入状态，设$f_{i,j,k}$表示处理完$i$的子树后子树$w_i$和为$j$，被反向的反向边的个数为$k$的概率和。(注意到由反向边相连的子树的大小视为$0$)最终的复杂度为$O(n^3)$。

实际上我们没有必要最后用第三维状态$k$来统计答案(计算容斥系数)，可以直接在$\text{dp}$转移中就直接考虑容斥系数就好了，选择一条反向边并将其反向实则就是将$\text{dp}$乘上$-1$，然后就可以直接转移了。复杂度$O(n^2)$。

代码：

/*
 * 3124.cpp
 * This file is part of 3124
 *
 * Copyright (C) 2019 - ViXbob
 *
 * 3124 is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * 3124 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with 3124. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * There is no end though there is a start in space. ---Infinity.
 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
 * Only the person who was wisdom can read the most foolish one from the history.
 * The fish that lives in the sea doesn't know the world in the land.
 * It also ruins and goes if they have wisdom.
 * It is funnier that man exceeds the speed of light than fish start living in the land.
 * It can be said that this is an final ultimatum from the god to the people who can fight.
 *
 * Steins;Gate
 */
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e3 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
    char ch = getchar(); int u = 0, f = 1;
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
    while(isdigit(ch))  { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, a[maxn], b[maxn], c[maxn], s[maxn], f[maxn][maxn * 3], rt, size[maxn], ans, tmp[maxn * 3];
int inv[maxn * 3];
vector<pair<int, int> > G[maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) { 
    for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
    return rnt;
}

inline void dfs(int x, int fr) {
    size[x] = 1;
    f[x][1] = 1ll * a[x] * s[x] % P;
    f[x][2] = 1ll * b[x] * s[x] % P * 2 % P;
    f[x][3] = 1ll * c[x] * s[x] % P * 3 % P;
    for(auto v : G[x]) if(v.first != fr) {
        dfs(v.first, x);
        rep(i, 1, size[x] * 3) rep(j, 1, size[v.first] * 3) {
            int res = 1ll * f[x][i] * f[v.first][j] % P;
            if(v.second) tmp[i + j] = dec(tmp[i + j], res), tmp[i] = pls(tmp[i], res);
            else tmp[i + j] = pls(tmp[i + j], res);
        }
        size[x] += size[v.first];
        rep(i, 1, 3 * size[x]) f[x][i] = tmp[i], tmp[i] = 0;
    }
    rep(i, 1, size[x] * 3) f[x][i] = 1ll * f[x][i] * inv[i] % P;
}

int main() {
//    freopen("1.in", "r", stdin);
//    freopen("my.out", "w", stdout);
    n = read();
    rep(i, 1, 3 * n) inv[i] = inv(i);
    rep(i, 1, n) a[i] = read(), b[i] = read(), c[i] = read(), s[i] = inv(a[i] + b[i] + c[i]);
    rep(i, 1, n - 1) {
        int x = read(), y = read();
        G[y].pb(mp(x, 1)); G[x].pb(mp(y, 0));
    }
    dfs(1, 1);
    rep(i, 1, size[1] * 3) ans = pls(ans, f[1][i]);
    cout << ans << endl;
    return 0;
}

标签: 数论, DP, 计数, 概率, 生成函数, 矩阵乘法, 二项式反演, 反演, 容斥原理

添加新评论

Hitokoto

“
”

分类

归档

友情链接

其它