题解
高斯消元+期望
首先好像有那么一句话叫概率正着推期望倒着推==
让你计算期望
那么考虑倒着推
设(f_S)表示剩余血量为(S)时距离结束的期望步数
然后显然(f_0=0)
考虑每一轮,先有(1)次回血,再有(k)段攻击
那么可以计算出每次扣(t)滴血的期望是(atk[t]=C(_{t}^{k})(frac{1}{m+1})^t(frac{m}{m+1})^{k-t})
然后先预处理出来(atk[])
转移是成环的,只能高斯消元
因为是倒着推得
所以显然枚举所有的后继即可:(f_i=1+sum_{j=1}^{i}{f[j]*atk[i-j]*frac{m}{m+1} + f[j]*atk[i-j+1]*frac{1}{m+1}})
当然(f_n)的情况比较特殊,因为已经有(n)滴血的时候不会加血
这时候你可能会发现一个问题
(f_0)这一项去哪里了?
这一项的系数其实并不好计算,因为可能这一轮还没有结束血就已经扣没了
但是(f_0=0)，所以如果要从(f_0)转移过来的话(f_0)前面的系数就恰好跟着(f_0)一起被消掉了
而且(f_0)不能从其他后继状态转移,因为(f_0)就是一个结束状态
这也就是期望倒着推的优点所在
还没完==
然后发现(n=1500)
那么不能暴力消元了
但是观察矩阵可以发现第(i)行一定有且只有(i+1)项
所以可以从第i行一行一行的消下来的时候只消第i,i+1,n+1三项
复杂度(O(Tn^2))
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 1505 ;
const int mod = 1e9 + 7 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9' || c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0' && c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , stp , m , k ;
int fac[M] , hit[M] , miss[M] , atk[M] ;
int B[M][M] , wei[M] ;
inline int Fpw(int Base , int k) {
int temp = 1 ;
while(k) {
if(k & 1) temp = (1LL * temp * Base) % mod ;
Base = (1LL * Base * Base) % mod ; k >>= 1 ;
}
return temp ;
}
inline int Inv(int x) { return Fpw(x , mod - 2) ; }
inline int Gfac(int l , int r) {
int temp = 1 ;
for(int i = l ; i <= r ; i ++) temp = 1LL * temp * i % mod ;
return temp ;
}
inline void Pre_Solve() {
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n + 1 ; j ++)
B[i][j] = 0 ;
fac[0] = 1 ;
for(int i = 1 ; i <= n ; i ++)
fac[i] = 1LL * fac[i - 1] * i % mod ;
hit[0] = miss[0] = 1 ;
hit[1] = Inv(m + 1) ; miss[1] = 1LL * m * Inv(m + 1) % mod ;
for(int i = 0 ; i <= min(n , k) ; i ++)
atk[i] = 1LL * Gfac(k - i + 1 , k) * Inv(fac[i]) % mod * Fpw(hit[1] , i) % mod * Fpw(miss[1] , k - i) % mod ;
}
inline bool gauss() {
for(int i = 1 ; i <= n ; i ++) {
wei[i] = min(i + 1 , n) ;
for(int j = 1 ; j <= n + 1 ; j ++)
B[i][j] = (B[i][j] % mod + mod) % mod ;
}
for(int i = 1 ; i <= n ; i ++) {
if(B[i][i] == 0) return false ;
int tinv = Inv(B[i][i]) ;
for(int j = i + 1 ; j <= n ; j ++) {
if(B[j][i] == 0) continue ;
int tp = 1LL * B[j][i] * tinv % mod ;
B[j][i] = ((B[j][i] - 1LL * tp * B[i][i] % mod) % mod + mod) % mod ;
if(i + 1 <= n) B[j][i + 1] = ((B[j][i + 1] - 1LL * tp * B[i][i + 1] % mod) % mod + mod) % mod ;
B[j][n + 1] = ((B[j][n + 1] - 1LL * tp * B[i][n + 1] % mod) % mod + mod) % mod ;
}
}
for(int i = n ; i >= 1 ; i --) {
for(int j = i + 1 ; j <= n ; j ++)
B[i][n + 1] = ((B[i][n + 1] - 1LL * B[i][j] * B[j][n + 1] % mod) % mod + mod) % mod ;
B[i][n + 1] = (1LL * B[i][n + 1] * Inv(B[i][i]) % mod + mod) % mod ;
if(i == stp) break ;
}
return true ;
}
int main() {
int T = read() ;
while(T --) {
n = read() ; stp = read() ; m = read() ; k = read() ;
if(k == 0) { printf("-1
") ; continue ; }
else if(k == 1 && m == 0) { printf("-1
") ; continue ; }
Pre_Solve() ;
for(int i = 1 ; i <= n ; i ++) {
B[i][i] = (B[i][i] + 1) % mod ; B[i][n + 1] = (B[i][n + 1] + 1) % mod ;
if(i < n) for(int j = 0 ; j <= i + 1 ; j ++) {
if(i - j <= k) B[i][j] = ((B[i][j] - 1LL * atk[i - j] * miss[1] % mod) % mod + mod) % mod ;
if(i - j + 1 <= k) B[i][j] = ((B[i][j] - 1LL * atk[i - j + 1] * hit[1] % mod) % mod + mod) % mod ;
}
else for(int j = 0 ; j <= i ; j ++) {
if(i - j <= k) B[i][j] = ((B[i][j] - 1LL * atk[i - j] % mod) % mod + mod) % mod ;
}
}
if(!gauss()) printf("-1
") ;
else printf("%d
",(B[stp][n + 1] % mod + mod) % mod) ;
}
return 0 ;
}