「一个人的桃花源」

CTS2019题解

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

随机立方体

$$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 =\frac{1}{i!}\prod_{j=0}^{i-1}(n-j)\times(m-j)\times(l-j)$$

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

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

$$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$次上升幂。

\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}

\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}

\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$$

/*
* 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;
}

珍珠

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

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

$$\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}$$

$$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)!}$$

\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}

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

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

\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}

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

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);
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;
}
/*
*/

氪金手游

\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}

/*
* 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);
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;
}