BZOJ5292 洛谷4457 LOJ2513：[BJOI2018]治療之雨——題解

https://www.lydsy.com/JudgeOnline/problem.php?id=5292

https://www.luogu.org/problemnew/show/P4457

https://loj.ac/problem/2513

你現在有m+1個數：第一個為p，最小值為0，最大值為n；剩下m個都是無窮，沒有最小值或最大值。

你可以進行任意多輪操作，每輪操作如下：

在不為最大值的數中等概率隨機選擇一個（如果沒有則不操作），把它加一；

進行k次這個步驟：在不為最小值的數中等概率隨機選擇一個（如果沒有則不操作），把它減一。

現在問期望進行多少輪操作以后第一個數會變為最小值0。

期望dp的一個慣用套路。

設f[i]為正好打中英雄i下的概率，則f[i]=C(k,i)*(1/(m+1))^k*(m/(m+1))^(k-i)

于是不難得到f[i]與f[i-1]之間的關系，則線性推之。

再設a[i][j]為英雄i血經過一輪變j血的概率。

則a[i][j]=(f[i-j]*m+f[i+1-j])/(m+1)，但是當i=n時不適用，當i<j時也不適用，二者特判之。

最后令x[i]為英雄到i血的期望。

則有：

x[0]=0;

x[1]=a[1][2]*x[2]+a[1][1]*x[1]+1

x[2]=a[2][3]*x[3]+a[2][2]*x[2]+a[2][1]*x[1]+1

……

x[n]=a[n][n]*x[n]+a[n][n-1]*x[n-1]+……

（注意最后一項有細微差別。）

此時我們可以高斯消元求出答案……？

n=1500仿佛在開玩笑。

那么這樣的式子一定有什么特殊的方法可以消元。

我們每次用1式消掉x[1]，用2式x[2]……，則復雜度其實只需要O(n^2)（因為1式只有2個數，2式消完后也只有2個數……以此類推）

這樣我們每一個式子就是一個二元一次方程，最后一個式子是一個一元一次方程，于是就可以求解了。

（PS：還有其他比如k=0/1，m=0之類的特判不要忘了加。）

#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1505;
const int p=1e9+7;
inline ll read(){ll X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X;
}
ll qpow(ll k,int n){ll res=1;while(n){if(n&1)res=res*k%p;k=k*k%p;n>>=1;}return res;
}
ll n,q,m,k,f[N],a[N][N],x[N];
inline void init(){ll inv1=qpow(m+1,p-2),inv2=qpow(m,p-2);f[0]=qpow(inv1*m%p,k);for(int i=1;i<=min(n,k);i++)f[i]=f[i-1]*inv2%p*qpow(i,p-2)%p*(k-i+1)%p;for(int i=1;i<n;i++){for(int j=1;j<=i;j++)a[i][j]=(f[i-j]*m%p+f[i+1-j])%p*inv1%p;a[i][i+1]=f[0]*inv1%p;}for(int j=1;j<=n;j++)a[n][j]=f[n-j];for(int i=1;i<=n;i++)a[i][n+1]=p-1;for(int i=1;i<=n;i++)(a[i][i]+=p-1)%=p;
}
ll solve(){if(!k)return -1;if(!m){if(k==1)return -1;int res=0;while(q>0){if(q<n)q++;q-=k;res++;}return res;}init();for(int i=1;i<=n;i++){ll inv=qpow(a[i][i],p-2);a[i][i]=1;(a[i][n+1]*=inv)%=p;if(i!=n)(a[i][i+1]*=inv)%=p;for(int j=i+1;j<=n;j++){ll tmp=a[j][i];a[j][i]=0;(a[j][i+1]+=p-tmp*a[i][i+1]%p)%=p;(a[j][n+1]+=p-tmp*a[i][n+1]%p)%=p;}}x[n]=a[n][n+1];for(int i=n;i>q;i--)x[i-1]=(a[i-1][n+1]-a[i-1][i]*x[i]%p+p)%p;memset(f,0,sizeof(f));return x[q];
}
int main(){int t=read();while(t--){n=read(),q=read(),m=read(),k=read();printf("%lld\n",solve());}return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

?+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

?+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++