小狗狗也AK了！

主動放棄遊戲區知名部落客的機會。

題目

題目背景

F i r e W i n g B i r d \sf FireWingBird FireWingBird：“哈哈，我是人類！”

題目描述

人類 F i r e W i n g B i r d \sf FireWingBird FireWingBird 認為 O n e I n D a r k \sf OneInDark OneInDark 這條狗就不要叫了，是以 T a Ta Ta 要出一道題來當人上狗！

現在 F i r e W i n g B i r d \sf FireWingBird FireWingBird 正在看 3 D 3D 3D 模诶拟雨，沒騰出手來，隻好用後腿随便寫了一個題。題面被謄抄于下方，由 S i s t e r \color{black}{S}\color{red}ister Sister 提供翻譯。

對于所有正整數序列 a 1 , a 2 , a 3 , … , a k a_1,a_2,a_3,\dots,a_k a1​,a2​,a3​,…,ak​ 和 b 1 , b 2 , b 3 , … , b k b_1,b_2,b_3,\dots,b_k b1​,b2​,b3​,…,bk​ 滿足下列條件

• ∑ i = 1 k a i = n \sum_{i=1}^{k}a_i=n ∑i=1k​ai​=n
• ∑ i = 1 k b i = m \sum_{i=1}^{k}b_i=m ∑i=1k​bi​=m

定義其權值為 ∏ i = 1 k min ⁡ ( a i , b i ) \prod_{i=1}^{k}\min(a_i,b_i) ∏i=1k​min(ai​,bi​)，求所有權值的和。

資料範圍與提示

max ⁡ ( n , m , k ) ⩽ 5 × 1 0 5 \max(n,m,k)\leqslant 5\times 10^5 max(n,m,k)⩽5×105 。

思路

很明顯是二進制生成函數。枚舉 min ⁡ \min min 是誰，容易發現答案即

[ x n y m ] ( ∑ 1 ⩽ a ⩽ b a x a y b + ∑ 1 ⩽ b < a b x a y b ) k [x^ny^m]\left(\sum_{1\leqslant a\leqslant b}ax^ay^b+\sum_{1\leqslant b<a}bx^ay^b\right)^k [xnym](1⩽a⩽b∑​axayb+1⩽b<a∑​bxayb)k

很容易進行無窮級數求和，這裡就略去一點步驟。

[ x n y m ] [ x y ( 1 − x y ) 2 ( 1 − y ) + x 2 y ( 1 − x y ) 2 ( 1 − x ) ] k    = [ x n − k y m − k ] ( 1 1 − y + x 1 − x ) k 1 ( 1 − x y ) 2 k [x^ny^m]\left[\frac{xy}{(1{\it-}xy)^2(1-y)}+\frac{x^2y}{(1{\it -}xy)^2(1-x)}\right]^k\\\;\\ =[x^{n-k}y^{m-k}]\left(\frac{1}{1-y}+\frac{x}{1-x}\right)^k\frac{1}{(1-xy)^{2k}} [xnym][(1−xy)2(1−y)xy​+(1−xy)2(1−x)x2y​]k=[xn−kym−k](1−y1​+1−xx​)k(1−xy)2k1​

如果我們枚舉 1 ( 1 − x y ) 2 k = ∑ i = 0 + ∞ ( i + 2 k − 1 2 k − 1 ) ( x y ) i {1\over(1-xy)^{2k}}=\sum_{i=0}^{+\infty}{i+2k-1\choose 2k-1}(xy)^i (1−xy)2k1​=∑i=0+∞​(2k−1i+2k−1​)(xy)i 的次數，前面就是可以 O ( k ) \mathcal O(k) O(k) 計算的二項式了。

然而！我沒有發現！這裡可以直接 乘進去！我的數學直覺太差了！

因為 1 1 − y + x 1 − x = 1 + ∑ i = 1 + ∞ ( x i + y i ) \frac{1}{1-y}+\frac{x}{1-x}=1+\sum_{i=1}^{+\infty}(x^i+y^i) 1−y1​+1−xx​=1+∑i=1+∞​(xi+yi)，與 1 1 − x y = ∑ i = 0 + ∞ ( x y ) i {1\over 1-xy}=\sum_{i=0}^{+\infty}(xy)^i 1−xy1​=∑i=0+∞​(xy)i，可謂是幾乎互補……

( 1 + ∑ i = 1 + ∞ x i + ∑ i = 1 + ∞ y i ) ( ∑ i = 0 + ∞ x i y i ) = ∑ i = 0 + ∞ x i y i + ( ∑ i = 0 + ∞ x i y i ) ( ∑ i = 1 + ∞ x i ) + ( ∑ i = 0 + ∞ x i y i ) ( ∑ i = 1 + ∞ y i ) = ∑ i = 0 + ∞ x i y i + ∑ 0 ⩽ b < a x a y b + ∑ 0 ⩽ a < b x a y b = ∑ a , b ⩾ 0 x a y b = 1 1 − x ⋅ 1 1 − y \begin{aligned}&\left(1+\sum_{i=1}^{+\infty}x^i+\sum_{i=1}^{+\infty}y^i\right)\left(\sum_{i=0}^{+\infty} x^iy^i\right)\\&=\sum_{i=0}^{+\infty}x^iy^i+\left(\sum_{i=0}^{+\infty}x^iy^i\right)\left(\sum_{i=1}^{+\infty}x^i\right)+\left(\sum_{i=0}^{+\infty}x^iy^i\right)\left(\sum_{i=1}^{+\infty}y^i\right)\\&=\sum_{i=0}^{+\infty}x^iy^i+\sum_{0\leqslant b<a}x^ay^b+\sum_{0\leqslant a<b}x^ay^b\\&=\sum_{a,b\geqslant 0}x^ay^b\\&=\frac{1}{1-x}\cdot\frac{1}{1-y}\end{aligned} ​(1+i=1∑+∞​xi+i=1∑+∞​yi)(i=0∑+∞​xiyi)=i=0∑+∞​xiyi+(i=0∑+∞​xiyi)(i=1∑+∞​xi)+(i=0∑+∞​xiyi)(i=1∑+∞​yi)=i=0∑+∞​xiyi+0⩽b<a∑​xayb+0⩽a<b∑​xayb=a,b⩾0∑​xayb=1−x1​⋅1−y1​​

I n c r e d i b l e !    M a r v e l o u s !    U n p r e c e d e n t e d !    N o    w o r d    c a n    d e s c r i b e    m y    f e e l i n g ! Incredible!\;Marvelous!\;Unprecedented!\;No\;word\;can\;describe\;my\;feeling! Incredible!Marvelous!Unprecedented!Nowordcandescribemyfeeling!

回到正題上。我們把 1 1 − x y {1\over 1-xy} 1−xy1​ 給踢進去，就會得到

[ x n − k y m − k ] 1 ( 1 − x ) k ( 1 − y ) k ⋅ 1 ( 1 − x y ) k [x^{n-k}y^{m-k}]\frac{1}{(1{\it-}x)^k(1{\it -}y)^k}\cdot\frac{1}{(1{\it-}xy)^k} [xn−kym−k](1−x)k(1−y)k1​⋅(1−xy)k1​

現在再用枚舉 x y xy xy 的次數的方法，前面就可以硬算了。時間複雜度 O ( n ) \mathcal O(n) O(n)，碼量超小。

代碼

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int MaxM = 2000005;
const int Mod = 998244353;
namespace Math{
	int jc[MaxM], inv[MaxM];
	void import(int n = MaxM-1){
		jc[0] = inv[0] = jc[1] = inv[1] = 1;
		rep(i,2,n){
			jc[i] = 1ll*jc[i-1]*i%Mod;
			inv[i] = (0ll+Mod-Mod/i)*inv[Mod%i]%Mod;
		}
		rep(i,2,n) inv[i] = 1ll*inv[i-1]*inv[i]%Mod;
	}
	int getC(int n,int m){
		return 1ll*jc[n]*inv[m]%Mod*inv[n-m]%Mod;
	}
}
using Math::getC;

int main(){
	Math::import();
	for(int T=readint(); T; --T){
		int n = readint(), m = readint();
		int k = readint(), ans = 0;
		if(n > m) swap(n,m); // n <= m
		rep(i,0,n-k){
			int_ t = getC(i+k-1,k-1);
			t = t*getC(n-i-1,k-1)%Mod;
			t *= getC(m-i-1,k-1);
			ans = (ans+t)%Mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}
           

後記

當化簡到 1 ( 1 − x y ) 2 k \frac{1}{(1-xy)^{2k}} (1−xy)2k1​ 那一步時，我還比較自信，于是直接枚舉了 x y xy xy 的次數，剩下的時間就都浪費在試圖直接求左邊那個式子的某一項系數了。

想過遞推組合數，啥都想過了，發現真的行不通，不如 往回退一步，是不是某一步的 “代碼實作” 錯了？簡直讓人想起這道令人崩潰的題目啊……