P3266 [JLOI2015]骗我呢 [* hard]
给定 \(n\times m\) 的棋盘，规定左下角为 \((1,1)\)，右上角为 \((n,m)\)，对于棋盘内的每个元素：
- \(a_{i,j}\in [0,m]\)
- \(a_{i,j}<a_{i,j+1}\)
- \(a_{i,j}<a_{i-1,j+1}\)
即，每行满足从左往右依次递增，每个对角线满足从左上到右下依次递增的棋盘数量。
\(n,m\le 10^6\)
Solution
观察发现 \(a_{i,j}\in [j-1,j]\)，同时如果 \(j\) 使得 \(a_j=j\)，那么其后均需满足此条件。
观察发现对于对角线，如果 \(a_j=j\)，那么其往后必然也如此。
于是假设一个位置是最后一个 \(a_j=j-1\)，那么其往前均如此，往后均非如此。
同时对于每个对角线，也有其往上如此，往下非如此。
设 \(f_i\) 表示对于第 \(i\) 行最后一个 \(j\) 使得 \(a_{i,j}=j-1\)，此时 \(f_i\in [0,m]\) 这样我们只需要考虑对角线的限制：
不难发现若 \(f_{i-1}-1>f_i\)，那么就有：对于 \((i-1,f_{i-1})\) 和 \((i,f_{i-1}-1)\) 这两个值相同，均为 \(f_{i-1}-1\)
我们等价于对 \(f\) 序列计数，一个 \(f\) 序列合法当且仅当对于 \(i\)，有 \(f_i\ge f_{i-1}-1\)
这样我们可以得到一个容易的 dp 来计算答案，复杂度 \(\mathcal O(nm)\)
接下来，我们实际上需要计数的序列 \(a\) 的数量，满足：
- \(a_i\in [0,m]\)
- \(a_i+1\ge a_{i-1}\)
这个第二个限制比较难受，我们考虑令 \(b_i=a_i+i\)，那么不难发现限制等价于 \(b_i\ge b_{i-1}\)
我们考虑对 \(b_i\) 序列进行计数，这样 \(b_i\in [i,i+m]\)
现在考虑网格上的路径计数问题，条件可以等价于：
从 \((0,0)\) 出发，在不经过 \(y=x-1\) 和 \(y=x+m+2\) 的情况下到达 \((n,n+m)\) 的方案数。
这样将第一次到达 \(x=k\) 时的 \(y\) 坐标写下来就得到了 \(b_k\)
考虑容斥，我们计算：
路径总数，减去经过了 \(y=x-1\) 的路径数，减去经过 \(y=x+m+2\) 的路径数，加上经过了 \(y=x-1\) 和 \(y=x+m+2\) 的路径数。
前三种都是平凡的，考虑最后一种如何处理，类似的，我们考虑对称，将 \((0,0)\) 关于 \(y=x-1\) 进行对称，将 \((n,n+m)\) 关于 \(y=x+m+2\) 进行对称，这样从两个对称点走到另一个对称点的方案即为答案。（这是我一开始 naive 的想法）
然而有 Hack，\(n=3,m=0\)（\(n\ge m+3\) 的时候都是 Hack 数据）
这是由于进行对称之后，我们不难发现我们计算的路径一定都是先经过了下面的限制线，然后到达终点时要经过上面的限制线的情况。
然而如果 \(n\le m+2\) 的话，那么即 \((0,0)\to (n,n+m)\)
假设先到达了第一条限制线，那么此时下标至少为 \((0,m+2)\)，这个时候要到达第二条限制线，相当于要到达 \((m+3,m+2)\)，由于 \(m+3>n\)，所以肯定不会产生此类情况。
假设到达 \((n,n+m)\) 时是最后从 \(y=x-1\) 处出来的，那么由于之前要经过 \(y=x+m+2\)，然而由于经过了 \(y=x+m+2\) 是绝对无法再经过 \(y=x-1\) 的，所以最后经过的线也必须是 \(y=x+m+2\) 。
设两条限制线分别为 A 和 B，假设我们依次经过了 A 和 B 或者说达成了 AAABBAA... 这种循环的模式
我们希望于让这样的走法只被加上恰好一次。
考虑开头是 A 的串，我们现在希望计算所有开头是 A 的串。
然而如果执行对称，我们没有办法保证其之前没有经过 B
那么，容斥，我们减去之前经过了 B 的方案。
换而言之我们减去 BA 类型的串。
但是 B 也无法真的就是开头，所以我们加上 ABA 类型的串...
于是我们得到了一个容斥的做法，对以 B 开头重复一次流程即可。
不难发现长度为奇数的对答案的贡献都是 -1，偶数都是 1，所以直接减去 A 和 B，加上 AB 和 BA，减去 ABA 和 BAB 就可以了。
这样可以直接多次对称，是十分方便的（非常正确）。
现在考虑对称，根据观察，我们发现 \((x_0,y_0)\) 关于 \(y=x+b\) 对称的结果为 \((y_0-b,x_0+b)\)
那么不难注意到，每次关于 \(y=x-1\) 对称，几乎只是将 \(x,y\) 进行了交换。
每次将其关于 \(y=x+m+2\) 对称，会使得其中 \(x\) 增大 \(m\)，然后交换又会回来，换而言之每操作两次会使得 \(x,y\) 中的一个增大 \(m\)
于是交换次数上界为 \(\frac{n}{m}\)，所以我们的复杂度也是 \(\mathcal O(\frac{n}{m})\)
\(Code:\)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int P = 1e9 + 7 ;
const int N = 5e6 ;
struct node {
int x, y ;
node(int _x = 0, int _y = 0) { x = _x, y = _y ; }
} Ed ;
int fpow(int x, int k) {
int ans = 1, base = x ;
while(k) {
if(k & 1) ans = 1ll * ans * base % P ;
base = 1ll * base * base % P, k >>= 1 ;
} return ans ;
}
int n, m, maxn, fac[N + 5], inv[N + 5] ;
int C(int x, int y) {
if( x < 0 || y < 0 || x < y ) return 0 ;
return fac[x] * inv[y] % P * inv[x - y] % P ;
}
int operator - (node a, node b) {
int dx = a.x - b.x, dy = a.y - b.y ;
return C(dx + dy, dx) ;
}
node F(node x, int b) {return node(x.y - b, x.x + b) ;}
int Get(node x, int type) {
if( (Ed - x) == 0 ) return 0 ;
int ans = ((Ed - x) - Get(F(x, (type == 1) ? m + 2 : -1), type ^ 1) + P) % P ;
return ans ;
}
signed main()
{
n = gi(), m = gi() ; Ed = node(n, n + m) ;
maxn = 2 * n + m ;
fac[0] = inv[0] = 1 ;
rep( i, 1, N ) fac[i] = fac[i - 1] * i % P ;
inv[N] = fpow( fac[N], P - 2 ) ;
drep( i, 1, N ) inv[i - 1] = inv[i] * i % P ;
int ans = C(maxn, n) ;
ans -= Get(F(node(0, 0), -1), 1) ;
ans -= Get(F(node(0, 0), m + 2), 0) ;
ans = (ans % P + P) % P ;
cout << ans << endl ;
return 0 ;
}