题目大意
有一个棋盘只有两行,但有 1 0 1000 10^{1000} 1 0 1000 列,第一行上有 x x x 个炮,第二行上有 y y y 个炮。
众所周知,中国象棋中炮吃一个子时需要中间有一棋子作为炮架。记发生 k k k 次炮吃炮事件的方案数 ( m o d 1 0 9 + 9 ) \pmod{10^9+9} ( mod 1 0 9 + 9 ) 为 f k f_k f k ,输出 ⨁ k = 0 x + y − 4 f k \bigoplus\limits_{k=0}^{x+y-4}f_k k = 0 ⨁ x + y − 4 f k 。题目需要输出两个答案,分别对应两个限制条件:1.不考虑两行发生事件的顺序;2.事件必须先在第一行发生,之后再在第二行发生,不能再返回第一行发生。
思路
对于某一行上共 r r r 个炮,考虑哪一个炮作为炮架,产生一次炮吃炮事件的方案数为 2 ( r − 2 ) 2(r-2) 2 ( r − 2 ) ;因此,产生 t t t 次炮吃炮事件的方案数为 2 ( r − 2 ) × 2 ( r − 1 − 2 ) × ⋯ × 2 ( r − t + 1 − 2 ) = 2 t ( r − 2 ) ! ( r − 2 − t ) ! 2(r-2)\times 2(r-1-2)\times\cdots\times 2(r-t+1-2)=2^t\frac{(r-2)!}{(r-2-t)!} 2 ( r − 2 ) × 2 ( r − 1 − 2 ) × ⋯ × 2 ( r − t + 1 − 2 ) = 2 t ( r − 2 − t )! ( r − 2 )! 。
枚举 0 ≤ i ≤ k 0\le i\le k 0 ≤ i ≤ k ,表示第一行发生 i i i 次炮吃炮事件,第二行发生 k − i k-i k − i 次炮吃炮事件。对于答案1,我们要从 k k k 次炮吃炮中选出 i i i 次在第一行中发生的,f 1 , k = ∑ i = 0 k ( k i ) × 2 i ( x − 2 ) ! ( x − 2 − i ) ! × 2 k − i ( y − 2 ) ! [ y − 2 − ( k − i ) ] ! f_{1,k}=\sum\limits_{i=0}^k\binom{k}{i}\times 2^i\frac{(x-2)!}{(x-2-i)!}\times 2^{k-i}\frac{(y-2)!}{[y-2-(k-i)]!} f 1 , k = i = 0 ∑ k ( i k ) × 2 i ( x − 2 − i )! ( x − 2 )! × 2 k − i [ y − 2 − ( k − i )]! ( y − 2 )! ;对于答案2,先在第一行发生 i i i 次事件,再在第二行发生 k − i k-i k − i 次事件,f 2 , k = ∑ i = 0 k 2 i ( x − 2 ) ! ( x − 2 − i ) ! × 2 k − i ( y − 2 ) ! [ y − 2 − ( k − i ) ] ! f_{2,k}=\sum\limits_{i=0}^k2^i\frac{(x-2)!}{(x-2-i)!}\times 2^{k-i}\frac{(y-2)!}{[y-2-(k-i)]!} f 2 , k = i = 0 ∑ k 2 i ( x − 2 − i )! ( x − 2 )! × 2 k − i [ y − 2 − ( k − i )]! ( y − 2 )! 。
令 a = x − 2 a=x-2 a = x − 2 ,b = y − 2 b=y-2 b = y − 2 。
$$
\begin{aligned}
f_{1,k}&=2^k\sum\limits_{i=0}^k\frac{k!}{i!(k-i)!}\frac{a!}{(a-i)!}\frac{b!}{[b-(k-i)]!}\\
&=2^kk!\sum\limits_{i=0}^k\frac{a!}{i!(a-i)!}\frac{b!}{(k-i)![b-(k-i)]!}\\
&=2^kk!\sum\limits_{i=0}^k\binom{a}{i}\times \binom{b}{k-i}\\
&a+b\ 个物品中拿\ k\ 个,就等价于枚举\ i,从\ a\ 中拿\ i\ 个,从\ b\ 中拿\ k-i\ 个。\\
&=2^kk!\binom{a+b}{k}
\end{aligned}
\quad
\begin{aligned}
f_{2,k}&=2^k\sum\limits_{i=0}^k\frac{a!}{(a-i)!}\frac{b!}{[b-(k-i)]!}\\
&=2^k\frac{a!b!}{(a+b-k)!}\sum\limits_{i=0}^k\frac{(a+b-k)!}{(a-i)![b-(k-i)!]}\\
&=2^k\frac{a!b!}{(a+b-k)!}\sum\limits_{i=0}^k\binom{a+b-k}{a-i}\\
\end{aligned}
$$
枚举 0 ≤ k ≤ a + b 0\le k\le a+b 0 ≤ k ≤ a + b ,预处理阶乘、阶乘的逆元、2 2 2 的幂次,可在 O ( x + y ) O(x+y) O ( x + y ) 的时间内得到 f 1 f_1 f 1 。我们接下来要设法在同样的时间得到 f 2 f_2 f 2 ,令 S k = ∑ i = 0 k ( a + b − k a − i ) S_k=\sum\limits_{i=0}^k\binom{a+b-k}{a-i} S k = i = 0 ∑ k ( a − i a + b − k ) ,我们可以考虑 S k S_{k} S k 同 S k + 1 S_{k+1} S k + 1 的关系,使用移步法解决。
$$
\begin{aligned}
S_{k+1}&=\sum\limits_{i=0}^{k+1}\binom{a+b-k-1}{a-i}\\
S_k&=\sum\limits_{i=0}^k\binom{a+b-k}{a-i}\\
&=\sum\limits_{i=0}^k\binom{a+b-k-1}{a-i}+\sum\limits_{i=0}^k\binom{a+b-k-1}{a-i-1}\\
&=\left[S_{k+1}-\binom{a+b-k-1}{a-k-1}\right]+\left[S_{k+1}-\binom{a+b-k-1}{a}\right]\\
&=2S_{k+1}-\binom{a+b-k-1}{a}-\binom{a+b-k-1}{b}
\end{aligned}
$$
倒序枚举 0 ≤ k ≤ a + b 0\le k\le a+b 0 ≤ k ≤ a + b ,S a + b = 1 S_{a+b}=1 S a + b = 1 ,得到 f 2 , a + b = 2 a + b a ! b ! f_{2,a+b}=2^{a+b}a!b! f 2 , a + b = 2 a + b a ! b ! ,即可在 O ( x + y ) O(x+y) O ( x + y ) 时间内得到答案。
代码
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 #include <iostream> using namespace std;typedef long long ll;const int MOD = 1e9 + 9 ;const int MAX_SIZE = 1e7 + 4 ;int fac[MAX_SIZE], inv[MAX_SIZE];int power2[MAX_SIZE];ll QuickPower (ll a, ll b) { ll res = 1 ; while (b) { if (b & 1 ) { res = res * a % MOD; } a = a * a % MOD; b >>= 1 ; } return res; } void Init () { fac[0 ] = power2[0 ] = 1 ; for (int i = 1 ;i < MAX_SIZE;i++) { fac[i] = 1ll * fac[i - 1 ] * i % MOD; power2[i] = 1ll * power2[i - 1 ] * 2 % MOD; } inv[MAX_SIZE - 1 ] = QuickPower (fac[MAX_SIZE - 1 ], MOD - 2 ); for (int i = MAX_SIZE - 2 ;i >= 0 ;i--) { inv[i] = 1ll * inv[i + 1 ] * (i + 1 ) % MOD; } } inline ll C (int n, int m) { return m > n ? 0 : 1ll * fac[n] * inv[n - m] % MOD * inv[m] % MOD; } int main () { Init (); int x, y; cin >> x >> y; int a = x - 2 , b = y - 2 ; int ans1 = 0 ; for (int k = 0 ;k <= a + b;k++) { ans1 ^= 1ll * power2[k] * fac[k] % MOD * C (a + b, k) % MOD; } cout << ans1 << ' ' ; int ans2 = 1ll * power2[a + b] * fac[a] % MOD * fac[b] % MOD; int lastS = 1 ; for (int k = a + b - 1 ;k >= 0 ;k--) { int curS = 2 * lastS - C (a + b - k - 1 , a) - C (a + b - k - 1 , b); curS = (curS % MOD + MOD) % MOD; ans2 ^= 1ll * power2[k] * fac[a] % MOD * fac[b] % MOD * inv[a + b - k] % MOD * curS % MOD; lastS = curS; } cout << ans2 << endl; return 0 ; }