题解：[BJOI2018]治疗之雨

题面

前置芝士：随机游走模型

给定一个 (n) 个点 (m) 条边的无向连通图，某位同志想从 (s) 号节点走到 (t) 号节点，每一个节点走向另一个相连的节点有一定概率，求期望步数

设 (f_i) 表示为从 (i) 节点到 (t) 节点的期望步数，(p_{i,j}) 表示从节点 (i) 到节点 (j) 的概率

列出方程组：

[egin{cases} f_i = displaystyle{sum_{(i,j)in E}^n p_{i,j} imes f_j + 1} & i eq t\ f_t = displaystyle{0}\ \ end{cases} ]

高斯消元 (mathcal{O}(n^3)) 求解即可

例题 [HNOI2013]游走

Solution

拿到题目，发现每一状态前后都能转移到，无法进行 DP

可以建立随机游走模型，有 (n+1) 个点，表示当前血量为 0-n ，每个点有一个状态 (E_i)

对于每一个状态 (E_i) 表示第一个数的数值大小为 (i) 时到达最小值 (0) 的期望步数

对于每一轮，要么受到减去 (ain [0,k]) ，要么加一，所以只存在向左和向右一个数值的边

设 (f_i) 表示 (k) 次伤害，受到 (i) 点伤害的概率

根据二项式分布有

(f_i = {k choose i} imes (frac{1}{m+1})^i imes (frac{m}{m+1})^{k-i})

拆开组合数得

(f_i = frac{k!}{k!(k-i)!} imes (frac{1}{m+1})^i imes (frac{m}{m+1})^{k-i})

这个式子是 (mathcal{O}(n)) 的，达标

先分类讨论

从 (i) 点血量到 (j(j < i)) 点血量的概率为 (frac{1}{m+1} f_{i-j}+frac{m}{m+1}f_{i-j+1})
从 (i) 点血量到 (i+1) 点血量的概率为 (frac{1}{m+1}f_0)
从 (n) 点血量不可有到 (n+1) 的可能性，任意点转来概率都为 (f_{i-j})

参照模型中的板子，列出方程组

[egin{cases} E_i = displaystyle{ 1 + frac{1}{m+1} f_0 imes E_{i+1} + sum_{j=1}^i (frac{1}{m+1} f_{i-j}+frac{m}{m+1}f_{i-j+1}) imes E_j} & i eq n\ E_n = displaystyle{ 1 + sum_{j=1}^n f_{n-j} imes E_j}\ \ end{cases} ]

(nleq 1500) , (mathcal{O}(n^3)) 的高斯消元过不去

但这里的方程矩阵有一个性质: (1表示有值，0表示无值)

[quad egin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 1 & 0 & 0 & 0 \ 1 & 1 & 1 & 1 & 1 & 0 & 0 \ 1 & 1 & 1 & 1 & 1 & 1 & 0 \ 1 & 1 & 1 & 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 & 1 & 1 & 1 \ end{bmatrix} quad egin{bmatrix} 1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 1 \ end{bmatrix} ]

发现消到第 (i) 行时，将第 (i) 列消为 (1) (数值上真正的1) 将这第 (i) 列的以下所有行上的元素消成 (0)

最终会得到一个形如下图的矩阵

[quad egin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 \ end{bmatrix} quad egin{bmatrix} 1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 1 \ end{bmatrix} ]

此时 (E_n) 已经求出来了，只要从下往上进行回代即可，时间复杂度 (mathcal{O}(n^2))，达标

最终答案即为 (E_p)

Code(C++):

#include<bits/stdc++.h>
#define forn(i,s,t) for(int i=(s);i<=(t);++i)
#define form(i,s,t) for(int i=(s);i>=(t);--i)
using namespace std;
typedef long long LL;
const int N = 1503,Mod = 1e9+7;
inline LL q_pow(LL p,int k) {            // 快速幂
	LL Ans = 1;
	while(k) (k&1 ? Ans=Ans*p%Mod:0),p=p*p%Mod,k>>=1;
	return Ans;
}
int T,n,p;LL m,k,Ans,G[N][N],f[N],fac[N];
inline void init() {Ans = 0;forn(i,1,min((LL)n+1,k))f[i]=0;forn(i,1,n)forn(j,1,n+1)G[i][j]=0;} // 初始化
inline int work() {
	scanf("%d%d%lld%lld",&n,&p,&m,&k);
	if(!k) return puts("-1"),0;
	if(!m) if(k == 1) return puts("-1"),0;
		   else {while(p>0) (p<n?p++:0),p-=k,++Ans;return printf("%lld
",Ans),0;} //以上为特殊情况
	LL inv=q_pow(m+1,Mod-2),invm=q_pow(m,Mod-2);
	f[0] = q_pow(m*inv%Mod,k);
	forn(i,1,min((LL)n+1,k)) f[i] = f[i-1]*invm%Mod*q_pow(i,Mod-2)%Mod*(k-i+1)%Mod;  // 线性求f数组
	forn(i,1,n-1) forn(j,1,i) G[i][j]=(f[i-j]*m+f[i-j+1])%Mod*inv%Mod;
	forn(i,1,n-1) G[i][i] = (G[i][i]+Mod-1)%Mod,G[i][i+1]=f[0]*inv%Mod;
	forn(i,1,n) G[i][n+1] = Mod-1;
	forn(i,1,n) G[n][i] = f[n-i]; G[n][n] = (G[n][n]+Mod-1)%Mod;                     // 以上为列方程
	forn(i,1,n) {
		inv = q_pow(G[i][i],Mod-2),G[i][i]=1,G[i][n+1]=G[i][n+1]*inv%Mod;
		if(i!=n) G[i][i+1] = G[i][i+1]*inv%Mod;
		forn(j,i+1,n) {
			G[j][i+1] = (G[j][i+1]-G[j][i]*G[i][i+1]%Mod+Mod)%Mod;
			G[j][n+1] = (G[j][n+1]-G[j][i]*G[i][n+1]%Mod+Mod)%Mod;
			G[j][i] = 0;
		}
	}                                                                               // 消元具体过程
	form(i,n,2) G[i-1][n+1]=(G[i-1][n+1]-G[i-1][i]*G[i][n+1]%Mod+Mod)%Mod,
				G[i-1][i] = 0;                                          // 回代过程
	printf("%lld
",G[p][n+1]);
	return 0;
} 
int main() {
	scanf("%d",&T);
	while(T--) init(),work();
	return 0;
}