更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19631424

大意

给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 $\gcd(x,y)=d$ 的二元组 $(x,y)$ 的数量。

思路

也就是说，我们要统计的答案是 $\sum_{x = 1} ^ a \sum_{y = 1} ^ b [\gcd(x, y) = d]$。

我们考虑莫比乌斯反演。

我们令 $x = d \times x', y = d \times y'$，那么原式可化为 $\sum_{x' = 1} ^ {\lfloor \frac{x}{d} \rfloor} \sum_{y' = 1} ^ {\lfloor \frac{y}{d} \rfloor} [\gcd(x', y') = 1]$，我们再利用恒等式 $[\gcd(x, y) = 1] = \sum_{k | \gcd(x, y)} \mu(k)$ 代入，得到答案为 $\sum_{x' = 1} ^ {\lfloor \frac{x}{d} \rfloor} \sum_{y' = 1} ^ {\lfloor \frac{y}{d} \rfloor} \sum_{k | \gcd(x, y)} \mu(k)$，接下来，我们再改变一下，先枚举 $k$，再看那些情况符合的，答案就变为了 $\sum_{k = 1} ^ {\min(\lfloor \frac{x}{d} \rfloor, \lfloor \frac{y}{d} \rfloor)} \mu(k) \lfloor \frac{x}{d} \rfloor \lfloor \frac{y}{d} \rfloor$。

代码

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

const int MAXN = 50005;
int mu[MAXN], pr[MAXN];
bool vis[MAXN];
int sum[MAXN], tot = 0;

void init(int n){
	mu[1] = 1;
	for(int i = 2;i <= n;i ++){
		if(!vis[i]){
			pr[++ tot] = i;
			mu[i] = -1;
		}
		for(int j = 1;j <= tot && pr[j] * i <= n;j ++){
			vis[pr[j] * i] = 1;
			if(i % pr[j] == 0){
				mu[pr[j] * i] = 0;
				break;
			}
			mu[pr[j] * i] = -mu[i];
		}
	}
	for(int i = 1;i <= n;i ++){
		sum[i] = sum[i - 1] + mu[i];
	}
}

int solve(){
	int a, b, d, ans = 0;
	cin >> a >> b >> d;
	if(a > b) swap(a, b);
	a /= d, b /= d;
	for(int l = 1, r;l <= a;l = r + 1){
		r = min(a / (a / l), b / (b / l));
		ans += (sum[r] - sum[l - 1]) * (a / l) * (b / l);
	}
	return ans;
}

int main(){
	init(50000);
	int t; cin >> t;
	while(t --){
		cout << solve() << '\n';
	}
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19640930

大意

从 $1$ 号点到第 $n$ 号点，每个地方是一个站点，有 $k$ 条路线，每个路线的车都有起始点和到达点，起始时间和到达时间，在等车的过程中他会哈气，问哈气值最小是什么？

思路

我们发现如果我们按时间进行排序，处理每个站点的航线的话，我们发现这样的话，后面的站点只能从前航线时间转移过来，那么这样的话我们做 DP 是没有后效性的，我们的转移是这样的，对于一个站点，若两条航线 $v_j = u_i$，那么有：$dp[i] = \min_{j \in \text{valid}} \{ dp[j] + A(p_i - q_j)^2 + B(p_i - q_j) + C \}$

我们不妨把这个转移式子拆开：$dp[i] = dp[j] + Ap_i^2 - 2Ap_iq_j + Aq_j^2 + Bp_i - Bq_j + C$

再把和 $i$ 与 $j$ 有关的项分开：$dp[i] = \underbrace{(dp[j] + Aq_j^2 - Bq_j)}_{\text{跟 } j \text{ 有关}} - \underbrace{2Ap_iq_j}_{i, j \text{ 混合}} + \underbrace{(Ap_i^2 + Bp_i + C)}_{\text{跟 } i \text{ 有关}}$

我们发现其实是可以做斜率优化的，我们将其化为 $y = kx + b$ 的形式：$\underbrace{dp[j] + Aq_j^2 - Bq_j}_{y} = \underbrace{(2Ap_i)}_{k} \cdot \underbrace{q_j}_{x} + \underbrace{(dp[i] - Ap_i^2 - Bp_i - C)}_{b}$

接下来维护一个下凸壳即可，由于是静态的，我们可以考虑直接用单调队列维护，但是有个很大的问题是，这些站点的东西要混起来吗？？？那怎么能知道哪个站点的能转移的点在哪呢？很简单的方式就是，我们直接维护 $n$ 个单调队列即可。每次对于每个站点进行转移即可。

代码

#include<iostream>
#include<queue>
#include<algorithm> 
using namespace std;

#define ll long long
const int MAXN = 2 * 1e5 + 5;
int n, m;
ll A, B, C;
ll u[MAXN], v[MAXN], q[MAXN], p[MAXN], dp[MAXN];
int id1[MAXN], id2[MAXN];
deque<int> Q[MAXN >> 1];

double X(int x){
    return q[x];
}
double Y(int x){
    return dp[x] + A * q[x] * q[x] - B * q[x];
}
double slope(int a, int b){
    if(X(a) == X(b)) return Y(a) >= Y(b) ? 1e18 : -1e18;
    return (Y(a) - Y(b)) / (X(a) - X(b));
}
bool cmp1(int a, int b){
    return p[a] < p[b];
}
bool cmp2(int a, int b){
    return q[a] < q[b];
}


int main(){
    // freopen("rout.in", "r", stdin);
    // freopen("rout.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m >> A >> B >> C;
    for(int i = 1;i <= m;i ++){
        cin >> u[i] >> v[i] >> p[i] >> q[i];
        id1[i] = id2[i] = i;
        dp[i] = 1e18;
    }
    sort(id1 + 1, id1 + m + 1, cmp1);
    sort(id2 + 1, id2 + m + 1, cmp2);
    dp[0] = q[0] = 0; v[0] = 1;
    Q[1].push_back(0);
    int nxt = 1;
    for(int k = 1;k <= m;k ++){
        int i = id1[k];
        while(nxt <= m && q[id2[nxt]] <= p[i]){
            int j = id2[nxt ++];
//            cout << j << '\n';
            if(dp[j] == 1e18) continue;
            int st = v[j];
            while(Q[st].size() > 1 && slope(j, Q[st][Q[st].size() - 2]) <= slope(Q[st][Q[st].size() - 2], Q[st][Q[st].size() - 1])){
                Q[st].pop_back();
            }
            Q[st].push_back(j);
        }
        int st = u[i];
        if(Q[st].empty()) continue;
        while(Q[st].size() > 1 && slope(Q[st][0], Q[st][1]) <= 2.0 * A * p[i]){
            Q[st].pop_front();
        }
		int j = Q[st][0];
//		cout << "i : " << i << ' ' << "j : " << j << '\n';
		dp[i] = dp[j] + A * (p[i] - q[j]) * (p[i] - q[j]) + B * (p[i] - q[j]) + C; 
    }
    ll ans = 1e18;
    for(int i = 1;i <= m;i ++){
        if(v[i] == n && dp[i] != 1e18){
            ans = min(dp[i] + q[i], ans);
        }
    }
    cout << ans << '\n';
    return 0;
} 

[统一省选 2020] 组合数问题 题解

宣传我的博客

说明

本题解整理自完整数学推导过程，重点在于如何从定义严格推出可计算的递推式， 并说明该递推如何对应到最终实现代码。$$\newcommand{\binom}[2]{{#1 \choose #2}}$$

注意： 本题解包含较多组合恒等式与求和变形，请耐心阅读。

简要题意

给定整数 $n,x,p$，以及一个 $m$ 次多项式

$$ f(k)=\sum_{i=0}^{m}a_i k^i $$

要求计算：

$$ \left(\sum_{k=0}^{n} f(k)\cdot x^k \cdot \binom{n}{k}\right)\bmod p $$

先说结论

定义：

$$ F(a,b)=\sum_{k=0}^{a}k^b x^k\binom{a}{k} $$

核心递推式

$$ F(n,m)=n\left(F(n,m-1)-F(n-1,m-1)\right) $$

边界条件

$$ F(k,0)=(x+1)^k $$

最终答案

$$ \text{ans}=\sum_{i=0}^{m}a_i F(n,i) $$

证明

前置公式

$$ k\binom{n}{k}=n\binom{n-1}{k-1} $$ $$ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} $$ $$ (x+1)^p=\sum_{i=0}^{p}\binom{p}{i}x^i $$

推导一：直接展开（$O(m^2)$）

$$ F(n,m)=\sum_{k=0}^{n}k^m x^k\binom{n}{k} $$ $$ \begin{aligned} F(n,m) &=\sum_{k=0}^{n}k^{m-1}x^k\cdot k\binom{n}{k} \\ &=\sum_{k=0}^{n}k^{m-1}x^k\cdot n\binom{n-1}{k-1} \\ &=n\sum_{k=1}^{n}k^{m-1}x^k\binom{n-1}{k-1} \end{aligned} $$ $$ F(n,m) =n\sum_{j=0}^{n-1}(j+1)^{m-1}x^{j+1}\binom{n-1}{j} $$ $$ F(n,m) =nx\sum_{j=0}^{n-1}(j+1)^{m-1}x^{j}\binom{n-1}{j} $$ $$ (j+1)^{m-1}=\sum_{i=0}^{m-1}\binom{m-1}{i}j^i $$ $$ F(n,m)=nx\sum_{i=0}^{m-1}\binom{m-1}{i}F(n-1,i) $$

推导二：关键递推

$$ \begin{aligned} F(n,m) &=\sum_{k=0}^{n}k^m x^k\binom{n}{k} \\ &=\sum_{k=0}^{n}k^m x^k\binom{n-1}{k} +\sum_{k=0}^{n}k^m x^k\binom{n-1}{k-1} \end{aligned} $$ $$ F(n,m)=F(n-1,m)+x\sum_{i=0}^{m}\binom{m}{i}F(n-1,i) $$ $$ F(n,m)=(1+x)F(n-1,m) +x\sum_{i=0}^{m-1}\binom{m}{i}F(n-1,i) $$ $$ x\sum_{i=0}^{m-1}\binom{m-1}{i}F(n-1,i) =F(n,m-1)-F(n-1,m-1) $$

最终结论

$$ \boxed{ F(n,m)=n\left(F(n,m-1)-F(n-1,m-1)\right) } $$

证毕。

与代码的对应关系（简述）

• f[j] 表示 $F(\cdot,j)$
• 递推式直接对应循环更新
• 初值 f[0]=(x+1)^n 是边界条件

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638913

$\newcommand{\binom}[2]{{#1 \choose #2}}$

大意

求$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p$的值。其中 $n$, $x$, $p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$。$\binom{n}{k}$ 为组合数，其值为 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$。

思路

好题！

我们先考虑这个式子的暴力处理方式，我们发现是外层枚举 $k$，内层枚举 $f(k)$ 的k $k$，这样是 $\mathcal{O}(nm)$ 的，但是我们发现 $1 \le n \le 10 ^ 9$，但是我们的 $m$ 是 $1 \le m \le 10 ^ 3$ 的，我们首先考虑的是把复杂度中的 $n$ 化为用 $m$ 的复杂度能解决的事情。

我们发现原始的式子中，只有 $f(k)$ 是需要我们额外处理的，所以我们先看这个东西，我们考虑化简，这个时候需要用到 $k$ 次下降幂的东西，众所周知 $x ^ k = x \times x \times \ldots $，那么我们的 $x ^ {\underline{k}} = x(x - 1)(x - k + 1)$，为什么我们需要知道这个东西呢？因为我们发现 $f(k)$ 中的 $k ^ j$ 无法很好的运算，我们考虑幂的转化，即利用**第二类斯特林数**将 $x ^ k \to x ^ {\underline{k}}$，如何做呢？我们有这样的恒等式：$k ^ i = \sum_{j = 0}^{i} {i \brace j} k ^ {\underline{j}}$。

那这个时候就有人要问了，主播主播什么是**第二类斯特林数**？我们考虑组合意义，是这样的： ${i \brace j}$ 表示将 $i$ 个互不相同的球放到 $j$ 个相同的盒子里（每个盒子都不为空）的方案数。那递推式就是：${i \brace j} = {i - 1 \brace j - 1} + j \times {i - 1 \brace j}$，那这个式子我们可以用组合的方式去理解一下，就是左边的 ${i - 1 \brace j - 1}$ 就是开一个新的盒子，而右边的 $j \times {i - 1 \brace j}$ 就是用旧的盒子。

好，回到正题，我们考虑将原始的 $f(k)$ 优化代换一下，用 $k ^ {\underline{j}}$ 替代 $k ^ j$，这样的话前面会产生一个新的系数，我们将这个系数记为 $b_j$，那么 $b_j = \sum_{i = 1}^{m} a_i \times {i \brace j}$。那么我们将这个 $b_j$ 带入原式，那么我们的式子就变成了这样~~一坨~~：$\sum_{k = 0} ^ {n} (\sum_{j = 0} ^ {m} b_j k ^ {\underline{j}}) x ^ k \binom{n}{k}$

接下来，我们先交换 $k$ 与 $j$ 的枚举顺序：$\sum_{j = 0} ^ {m} b_j (\sum_{k = 0} ^ {n} k ^ {\underline{j}} x ^ k \binom{n}{k})$

接下来我我们利用**吸收公式**的 $k$ 次下降幂的形式：$k ^ {\underline{j} \binom{n}{k}} = n ^ {\underline{j} \binom{n - j}{k - j}}$

将其带入，得到：$\sum_{j = 0} ^ {m} b_j (\sum_{k = j}^{n} n ^ {\underline{j}} \binom{n - j}{k - j} x ^ k)$

我们提取一下系数：$\sum_{j = 0} ^ {m} b_j n ^ {\underline{j}} \cdot x ^ j \sum_{k = j} ^ {n} \binom{n - j}{k - j} x ^ {k - j}$

不难注意到右边是二项式定理的形式，故可以继续化简：$\sum_{j = 0} ^ {m} b_j n ^ {\underline{j}} \cdot x ^ j (x + 1) ^ {n - j}$

到这边，我们的任务就完成了，$b_j$ 可以提前 $\mathcal{O}(m ^ 2)$ 预处理出来，$n ^ {\underline{j}}$ 可以随着递推求，$x^j$ 也可以随着递推求，至于 $(x + 1)^{n - j}$ 就可以直接快速幂求了，总时间复杂度就是 $\mathcal{O}(m ^ 2)$。

代码

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

const int MAXM = 1005;
#define ll long long
int n, x, p, m;
ll a[MAXM], b[MAXM];
ll S[MAXM][MAXM];

ll qpow(ll a, ll b){
	ll res = 1;
	a %= p;
	while(b){
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

int main(){
	srand(time(NULL));
    cout << rand() % 40;
	cin.tie(0) -> ios::sync_with_stdio(0);

	cin >> n >> x >> p >> m;

	for(int i = 0;i <= m;i ++) cin >> a[i];
	S[0][0] = 1;
	for(int i = 1;i <= m;i ++){
		for(int j = 1;j <= i;j ++){
			S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % p;
		}
	}

	for(int j = 0;j <= m;j ++){
		for(int i = 0;i <= m;i ++){
			(b[j] += ((a[i] * S[i][j]) % p)) %= p;
		}
	}

	ll mi = 1, ans = 0, xi = 1;
	for(int i = 0;i <= m;i ++){
		ll del = b[i];
		(del *= mi) %= p;
		(del *= xi) %= p;
		(del *= qpow(x + 1, n - i)) %= p;
		(ans += del) %= p;
//		(ans += (b[i] * mi * qpow(x, i) * qpow(x + 1, n - i))) %= p;
		(mi *= (n - i)) %= p;
		(xi *= x) %= p;
	}
	cout << (ans + p) % p << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638717

大意

给定两个点 $a$ 和 $b$，首先对于 $a$ 到 $b$ 路径上的所有点 $x$（包含 $a$ 和 $b$），你要将与 $x$ 相连的所有边变为轻边。然后再将 $a$ 到 $b$ 路径上包含的所有边变为重边。

给定两个点 $a$ 和 $b$，你需要计算当前 $a$ 到 $b$ 的路径上一共包含多少条重边。

思路

我们考虑一个小巧思。

我们将问题可以转化为将 $a \to b$ 这条路径的点染上独一无二的颜色，最终求 $a \to b$ 路径上的重边即为两端颜色相同的边的数量。

因为每次我们选的颜色都不一样，这样操作一定能够让我们通过只记录端点的颜色去统计这个值，我们通过直接维护区间的左右的端点的颜色和相邻重色的个数，我们如果区间的端点颜色重合就可以将这个答案继续累加。这个就是处理本题线段树的方式。

但是对于这个题目是在树上的操作，那就没什么说的了，直接树剖维护即可。但是如果你像我一样闲着没事的话可以用 LCT 维护，原因是这个更改 $a \to b$ 路径的过程可以用 LCT 的 split 操作非常简便的完成。至于 LCT 里面维护的内容，和线段树几乎一样，剩下就没什么了。

代码

#include<iostream>
#include<algorithm>
using namespace std;

#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;

struct node{
    int ch[2], fa;
    int col, tag;
    int lc, rc;
    int cnt; 
    int sz;
    bool rev;
    node(){
        ch[1] = ch[0] = fa = 0;
        col = tag = lc = rc = cnt = sz = 0;
        rev = false;
    }
}t[MAXN];

bool isroot(int x){
    return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}

void pushup(int x) {
    t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
    t[x].cnt = t[lc(x)].cnt + t[rc(x)].cnt;
    
    t[x].lc = lc(x) ? t[lc(x)].lc : t[x].col;
    t[x].rc = rc(x) ? t[rc(x)].rc : t[x].col;
    
    if(lc(x) && t[lc(x)].rc == t[x].col) t[x].cnt ++;
    if(rc(x) && t[rc(x)].lc == t[x].col) t[x].cnt ++;
}

void update_rev(int x){
    if(!x) return;
    swap(lc(x), rc(x));
    swap(t[x].lc, t[x].rc);
    t[x].rev ^= 1;
}

void apply_col(int x, int c){
    if(!x) return;
    t[x].col = t[x].lc = t[x].rc = t[x].tag = c;
    t[x].cnt = t[x].sz - 1;
}

void pushdown(int x){
    if(t[x].rev){
        update_rev(lc(x));
        update_rev(rc(x));
        t[x].rev = 0;
    }
    if(t[x].tag){
        apply_col(lc(x), t[x].tag);
        apply_col(rc(x), t[x].tag);
        t[x].tag = 0;
    }
}

void rotate(int x){
    int y = fa(x), z = fa(y);
    int k = (rc(y) == x);
    if(!isroot(y)) t[z].ch[rc(z) == y] = x;
    fa(x) = z;
    t[y].ch[k] = t[x].ch[k ^ 1];
    if (t[x].ch[k ^ 1]) fa(t[x].ch[k ^ 1]) = y;
    t[x].ch[k ^ 1] = y;
    fa(y) = x;
    pushup(y);
    pushup(x);
}

void pushshell(int x){
    if(!isroot(x)) pushshell(fa(x));
    pushdown(x);
}

void splay(int x){
    pushshell(x);
    while(!isroot(x)){
        int y = fa(x), z = fa(y);
        if(!isroot(y)) (rc(z) == y) ^ (rc(y) == x) ? rotate(x) : rotate(y);
        rotate(x);
    }
}

void access(int x){
    for(int y = 0;x;y = x, x = fa(x)){
        splay(x);
        rc(x) = y;
        pushup(x);
    }
}

void makeroot(int x){
    access(x);
    splay(x);
    update_rev(x);
}

void split(int x, int y){
    makeroot(x);
    access(y);
    splay(y);
}

void modify(int u, int v, int c){
    split(u, v);
    apply_col(v, c);
}

void solve(){
    int n, m; cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        t[i] = node();
        t[i].col = t[i].lc = t[i].rc = -i;
        t[i].sz = 1;
    }
    for(int i = 1;i < n;i ++){
        int u, v; cin >> u >> v;
        makeroot(u); fa(u) = v;
    }
    int cur_col = 0;
    while(m --){
        int op, u, v;
        cin >> op >> u >> v;
        if(op == 1){
            modify(u, v, ++ cur_col);
            split(u, v);
            apply_col(v, ++ cur_col);
        }
		else{
            split(u, v);
            cout << t[v].cnt << "\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638674

大意

三种牌分别有 $n , m, k$ 张，要求排列后满足相同的类型的牌不相邻的方案数。

$\newcommand{\binom}[2]{{#1 \choose #2}}$

思路

这集很考察基本功，组合好题。

考虑插板法，我们首先先把这个东西转换成上面的大意之后，我们先考虑把前两个人的位置考虑好，再考虑第三个人放的位置。

先安排核桃和小 $B$ 的位置，我们先枚举 $i$ 块 H，方案数是 $\binom{n - 1}{i - 1}$，现在我们要把 $m$ 个 B 也分成若干块，插入到这 $i$ 块 H 的空隙里。

为了使得 H 块之间分开，B 块的个数 $j$ 只有三种情况：

- $j = i - 1$

- $j = i$

- $j = i + 1$

其分别对应的情况为：B 块全在 H 块中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 2}$，B 和 H 一头一尾（两种情况），方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 1} \times  2$，H 全在 B 中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i}$。然而此时的问题是，虽然 B 和 H 交错排列了，但是仍有一部分不合法的块内相邻的点，接下来我们需要做的就是将 R 插入到这个序列里面。

如果每一个 H 块内有 $x$ 个相邻的，那么就需要 $x - 1$ 个板来进行隔开，同样的对于 B 块内的也一样。所以说至少需要拿出来使得不合法变为合法的 R 需要 $(n - i) + (m - j)$ 个 R 来进行~~紧急避险~~，那么我们还能剩的 $k' = (k - n - m + i + j)$，那么我们剩下的这些 $k'$ 应该放到哪些地方呢？首先是 H 和 B 的中间是可以的，然后就是序列的开头和结尾是一定可以的，那么我们的剩余槽位是 $r = i + j$，若是 H 和 B 交错排列的话就是 $r = i + j + 1$，所以接下来的问题是把这剩下的 $k'$ 放到 $r$ 个剩余的槽位中（每个槽可以放 $0$ 个或多个），这个时候使用隔板法 $\binom{k' + r - 1}{r - 1}$，我们将其展开之后就是 $\binom{k - n - m + 2i + 2j}{i + j}$。

所以来说，对应的三种情况的总方案数就可以写出来了：

- $i = j - 1：\binom{k - n - m + 4i - 2}{2i - 1}$

- $i = j：\binom{k - n - m + 4i}{2i}$

- $i = j + 1：\binom{k - n - m + 4i + 2}{2i + 1}$

然后就没有了。

代码

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

const ll mod = 998244353;
const ll N = 2e6 + 100;

ll n, m, k;
ll fac[N + 100], inv[N + 100];
ll ans;

ll mpow(ll aa,ll bb){
	ll res = 1;
	while(bb){
		if (bb&1) res = res * aa % mod;
		aa = aa * aa % mod;
		bb >>= 1;
	}
	return res;
}

ll C(ll aa,ll bb){
	if(aa < 0 || bb < 0 || aa > bb) return 0;
	return fac[bb] * inv[aa] % mod * inv[bb - aa] % mod;
}

int main(){
	freopen("UNO.in","r",stdin);
	freopen("UNO.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	fac[0] = 1;
	for(int i = 1;i <= N;i ++) fac[i] = (fac[i - 1] * i) % mod;
	for(int i = 0;i <= N;i ++) inv[i] = mpow(fac[i], mod - 2);
	for(int i = 1;i <= n;i ++){
		ans += C(i - 1, n - 1) * C(i - 2, m - 1) % mod * C(k - n - m + 2 * i - 1, 2 * i) % mod;
		ans += C(i - 1, n - 1) * C(i - 1, m - 1) % mod * C(k - n - m + 2 * i, 2 * i + 1) % mod * 2 % mod;
		ans += C(i - 1, n - 1) * C(i, m-1) % mod * C(k - n - m + 2 * i + 1, 2 * i + 2) % mod;
	}
	cout << (ans + mod) % mod<<'\n';
	return 0;
}