题解 P3266 【[JLOI2015]骗我呢】

· · 题解

[JLOI2015]骗我呢

更好的阅读体验：https://www.cnblogs.com/peanuttang/p/14389554.html

简要题意

给定 n,m，求有多少个 n\times m 的矩阵，满足：
对于任意的 i,j，都满足矩阵中的第 i 行第 j 列的元素 x_{i,j} 有：

结果对 10^9+7 取模，1\le n,m\le 10^6。

题解

第 1 条性质表示这个矩阵中每行都是单调递增的，而第 3 条性质则限制了每个只有 m+1 种取值。

我们发现，一行只有 m 个元素，而每个元素只可能有 m+1 中取值，且行内单调递增。于是这行有且只有一个在 [0,m] 中的元素没有被取到，而剩下的元素从小到大排序来填充这一行。

于是我们设计 DP 状态 f_{i,j} 表示进行到第 i 行，满足第 i 行缺少的元素时 j 的方案数。

考虑转移，发现如果 k>j+1 则对于 f_{i,p}=j+1，就会有 f_{i,p}=j+1=f_{i-1,p+1}，不满足第 2 条性质。于是要有 k\le j+1，所以有转移：f_{i,j}=\sum_{k=1}^{j+1}{f_{i-1,k}}。

再优化一下：f_{i,j}=\sum_{k=0}^{j+1}{f_{i-1,k}}=\sum_{k=0}^{j}{f_{i-1,k}}+f_{i-1,j+1}=f_{i,j-1}+f_{i-1,j+1}。

答案就是 f_{n+1,m}，这样子做是 O(nm) 的，要考虑优化。

我们考虑这个式子的组合意义，我们先将它映射到坐标轴上。下图中箭头表示转移，而答案就是从 (1,1) 走到 (n,m) 的路径数量。

这里面有些转移时“斜”的，这不太直观。我们将这个网格图变换一下，将第 i 行的点向右平移 i-1 格。同时将第 1 列之间的转移变成先往上再往右走。得到下图：

我们在 x 轴上再加上额外的一行，把起点弄到原点上，再画出两条直线：

我们发现答案就是从 (0,0) 到 T 即坐标轴上的 (n+m+1,n) 的路径数量，即只能向右或者向上走，不能触碰到 a:y=x+1 与 b:y=x-m-2 两条直线的从 (0,0) 到 (n+m+1,n) 的路径数量。

如果没有两条直线的限制，那么答案显然就是 \dbinom {x_T+y_T}{x_T}。对于碰到了直线的，例如我们先后触碰到了 aabbabb，发现其实连续触碰到相同的直线之没有上面影响的，可以整个缩起来，于是上面的例子可以被缩为 abab。

我们回想一下初中奥数“将军饮马”问题，我们发现将 (n+m+1,n) 关于 a 对称，得到 A'，则从 (0,0) 到 A' 的每一条路径都和对应的先触碰到 a 再折回到 (n+m+1,n) 的路径都是一一对应的，数量自然而然也是相等的。这个方法是可以叠加的，例如我们先将 (n+m+1,n) 关于 a 对称，再关于 b 对称，则到对应点的路径数则是结尾为 ba 的路径数。可以见下图：

这样我们就可以计算了。容斥一下，答案就是 \dbinom {x_T+y_T}{x_T}-\texttt{先到a的路径数}-\texttt{先到b的路径数}。减去先到 a 的路径数，我们只需要减去以 a,ab 结尾的方案，加上以 ba,bab 结尾的方案，减去\ldots

预处理阶乘的复杂度是线性的；而对称过程，每次的对称距至少增加 1，所以复杂度也是不超过线性的。所以总时间复杂度是线性的，而空间复杂度是 O(n) 的。

Code

#include <bits/stdc++.h>

#define il inline
#define ll long long
const int N=3e6+5,P=1e9+7;

int n,m,fac[N],ans;

il int ksm(int a,int b){int res=1; for ( ; b; b>>=1,a=(ll)a*a%P) if (b&1) res=(ll)res*a%P; return res;}

il int C(int x,int y){return x<0||y<0?0:(ll)fac[x+y]*ksm(fac[x],P-2)%P*ksm(fac[y],P-2)%P;}

il void trans(int &x,int &y,int a){std::swap(x,y),x-=a,y+=a;}

int main()
{
    scanf("%d%d",&n,&m); int i,x,y;
    for (i=fac[0]=1; i<N; i++) fac[i]=(ll)fac[i-1]*i%P;

    for (x=n+m+1,y=n,ans=C(x,y); x>=0&&y>=0;) trans(x,y,1),ans=(ans-C(x,y)+P)%P,trans(x,y,-m-2),ans=(ans+C(x,y))%P;
    for (x=n+m+1,y=n; x>=0&&y>=0; ) trans(x,y,-m-2),ans=(ans-C(x,y)+P)%P,trans(x,y,1),ans=(ans+C(x,y))%P; printf("%d\n",ans);

    return 0;
}