闲扯

很巧妙的一道题，思路值得借鉴。

题面

Solution

我们先考虑问题的弱化版： $n\leq 10^3,m\leq 10^3$ 。

考虑 $dp$ 。设 $dp_{i,j}$ 表示走到 $(i,j)$ 这个点，所有的 $G(P_{i,j},k)$ 的总和。

考虑转移。

我们如果只考虑每条线段下方的方格数，那么有如下方程： $dp_{i,j}=dp_{i-1,j}\cdot k^j+dp_{i,j-1}$ 。

表示我们从 $(i-1,j)$ 走到 $(i,j)$ ，多出了 $j$ 个格子，得到的贡献为所有走到 $(i-1,j)$ 的贡献乘上一定有的 $k^j$ ；而从 $(i,j-1)$ 走到 $(i,j)$ ，没有新的格子加入，贡献就为 $dp_{i,j-1}$ 。

但是这个方程是 $O(n^2)$ 的，考虑怎么优化。

因为上面我们考虑的是线段下方的方格数，我们再考虑一下计算方格右边的方格数。

这时我们可以得到以下方程： $dp_{i,j}=dp_{i,j-1}\cdot k^{n-i}+dp_{i-1,j}$ 。

但是我们的初始条件和前一种不同，没办法合并。

但是我们注意到这样一个事实：我们计算右边的格子数的总贡献，是等价于计算左边格子的总贡献的。

这是因为对于计算右边格子的每一种方案，我们都能相应的找到计算左边的一种方案。而我们经过 $180$ 度的旋转操作之后，得到的方案，刚好把左边和右边反过来了。所以每一种方案都有一个相对应的状态。

所以我们可以将方程改写成如下形式 $dp_{i,j}=dp_{i,j-1}\cdot k^i+dp_{i-1,j}$ 。

这时，我们发现两种转移方程的初始条件都是 $dp_{0.i}=dp_{j,0}=1$ 。

所以我们可以进行这样的操作：

$dp_{i,j}=dp_{i,j-1}+dp_{i-1,j}\cdot k^j=dp_{i,j-1}\cdot k^i+dp_{i-1,j}\\ dp_{i,j-1}\cdot(k^i-1)=dp_{i-1,j}\cdot(k^j-1)\\ dp_{i,j}\cdot(k^i-1)=dp_{i-1,j+1}\cdot(k^{j+1}-1)\\ dp_{i,j,(i=j)}=dp_{i-1.j+1}\cdot\frac{k^{j+1}-1}{k^i-1}\\ =dp_{i-2,j+2}\cdot\frac{(k^{j+1}-1)(k^{j+2}-1)}{(k^i-1)(k^{i-1}-1)}\\ =\cdots\\ =dp_{0,2\cdot i}\frac{\prod_{s=1}^i(k^{j+s}-1)}{\prod_{s=1}^i(k^s-1)}\\ =\frac{\prod_{s=1}^i(k^{j+s}-1)}{\prod_{s=1}^i(k^s-1)}$

所以我们只需要算出 $k^s,s\in(1,2\cdot i)$ ，即可得到最终的答案。

但是需要特别注意的是：当 $k=1$ 时，上式是恒成立的，不能用来求解。但是此时答案等于到 $(n,m)$ 的路径的方案数，直接用组合数 $C_{n+m}^{n}$ 计算即可。

Code

#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 1e7+10,mod = 1e9+7;
int pw[MAXN<<1],ans=705432;
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	pw[0]=1;
	for(ri i=2,n=11;i<=7;++i){
		n=(n-i+1)*10+i;
		for(ri j=1;j<=(n<<1);++j) pw[j]=mul(pw[j-1],i);
		ri up=1,down=1;
		for(ri j=1;j<=n;++j) up=mul(up,add(pw[n+j],mod-1)),down=mul(down,add(pw[j],mod-1));
		ans=add(ans,mul(up,qpow(down,mod-2,mod)));
	}
	print(ans);
	return 0;
}