NO IMAGE

一、題意概述

問你有多少個滿足條件的 n·m (1≤n,m≤103)” role=”presentation” style=”position: relative;”>n⋅m (1≤n,m≤103)n·m (1≤n,m≤103)n·m\ (1\leq n,m\leq 10^3) 的矩陣 A” role=”presentation” style=”position: relative;”>AAA,滿足矩陣每個元素 Ai,j∈{0,1,2}” role=”presentation” style=”position: relative;”>Ai,j∈{0,1,2}Ai,j∈{0,1,2}A_{i,j}\in\{0,1,2\} 並且 Ai,j≤Ai 1,j” role=”presentation” style=”position: relative;”>Ai,j≤Ai 1,jAi,j≤Ai 1,jA_{i,j}\leq A_{i 1,j} 而且 Ai,j≤Ai,j 1″ role=”presentation” style=”position: relative;”>Ai,j≤Ai,j 1Ai,j≤Ai,j 1A_{i,j}\leq A_{i,j 1},答案取模 109 7″ role=”presentation” style=”position: relative;”>109 7109 710^9 7。

二、解題思路

考慮 01″ role=”presentation” style=”position: relative;”>010101 和 12″ role=”presentation” style=”position: relative;”>121212 的分界線,用 (n,0)” role=”presentation” style=”position: relative;”>(n,0)(n,0)(n,0) 到 (0,m)” role=”presentation” style=”position: relative;”>(0,m)(0,m)(0,m) 的兩條不相交(可重合)路徑,平移其中一條變成 (n−1,−1)” role=”presentation” style=”position: relative;”>(n−1,−1)(n−1,−1)(n-1,-1) 到 (−1,m−1)” role=”presentation” style=”position: relative;”>(−1,m−1)(−1,m−1)(-1,m-1) 變成起點 (n,0)” role=”presentation” style=”position: relative;”>(n,0)(n,0)(n,0) 和 (n−1,−1)” role=”presentation” style=”position: relative;”>(n−1,−1)(n−1,−1)(n-1,-1),終點 (0,m)” role=”presentation” style=”position: relative;”>(0,m)(0,m)(0,m) 和 (−1,m−1)” role=”presentation” style=”position: relative;”>(−1,m−1)(−1,m−1)(-1,m-1) 的嚴格不相交路徑,套 Lindstrom-Gessel-Viennot lemma 定理。

答案就是 (Cn mn)2−Cn mm−1·Cn mn−1″ role=”presentation” style=”position: relative;”>(Cnn m)2−Cm−1n m⋅Cn−1n m(Cn mn)2−Cn mm−1·Cn mn−1(C_{n m}^n)^2-C_{n m}^{m-1}·C_{n m}^{n-1} !

三、解題程式碼

#include <bits/stdc  .h>
const int MOD = 1e9   7;
#include <bits/stdc  .h>
using namespace std;
const int N = 1005;
int dp[N][N];
void update(int &x, int a) {
x  = a;
if (x >= MOD) x -= MOD;
}
int sqr(int x) {
return 1LL * x * x % MOD;
}
int main() {
dp[0][0] = 1;
for (int i = 0; i < N;    i) {
for (int j = 0; j < N;    j) {
if (i) update(dp[i][j], dp[i - 1][j]);
if (j) update(dp[i][j], dp[i][j - 1]);
}
}
int n, m;
while (scanf("%d%d", &n, &m) == 2) {
printf("%d\n", static_cast<int>((sqr(dp[n][m])   MOD - 1LL * dp[n - 1][m   1] * dp[n   1][m - 1] % MOD) % MOD));
}
}