题目链接

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

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

LOJ:https://loj.ac/problem/2513

Solution

神仙期望题(可能是我期望太差了QAQ)

这题看懂题可能占了\(50\%\)的难度....

题目中的最大值最小值指的是上限和下限,我就是因为这个懵了好久...那么容易发现其他的怪你\(A\)多少下或者奶多少下都没有问题,我们只需要考虑自己就好了。

设\(p_i\)表示一个回合对自己造成\(i\)点伤害的概率,这里不考虑自己的上下界,那么显然可以得到:

\[p_i=\dfrac{\binom{k}{i}m^{k-i}}{(m+1)^k}
\]

分母是总情况,分子组合数表示哪些攻击到自己,剩下的随便选。

设\(f_i\)表示答案,即自己有\(i\)滴血可以存活回合数的期望,那么仔细想想可以得到一个这样的式子:

\[f_i=\frac{m}{m+1}\left(\sum_{j=i}^{n}p_j+\sum_{j=0}^{i-1}p_j(f_{i-j}+1) \right)+\frac{1}{m+1}\left(\sum_{j=i+1}^{n}p_j+\sum_{j=0}^ip_j(f_{i+1-j}-1)\right)
\]

前半部分算的是自己没被奶,括号内的\(\sum_{j=i}^np_j\)表示的是自己这回合被\(A\)死了,那么一定要\(A\) \(i\)次或以上,然后回合数为\(1\),乘起来就是这个,后面部分表示自己没被\(A\)死,那么回合数就是\(f_{i-j}+1\),\(+1\)是因为要算上本回合。

后半部分算的是自己被奶了,和前面差不多。

把式子画一下,\((f_{i-j}+1)\)这个括号展开,由于:

\[\sum_{i=0}^{n}p_i=1
\]

这个可以根据定义得到。

然后把式子展开:

\[f_i=\frac{m}{m+1}\left(1+\sum_{j=0}^{i-1}p_jf_{i-j} \right)+\frac{1}{m+1}\left(1+\sum_{j=0}^ip_jf_{i+1-j}\right)
\]

\[f_i=1+\frac{m}{m+1}\sum_{j=0}^{i-1}p_jf_{i-j}+\frac{1}{m+1}\sum_{j=0}^ip_jf_{i+1-j}
\]

注意下边界条件,因为满血不能被奶,所以:

\[f_n=1+\sum_{i=0}^{n-1}p_if_{n-i}
\]

那么我们得到了一堆的方程,至此我们可以\(O(Tn^3)\)的高斯消元解决。

但是这并不足以通过本题,我们观察一下高斯消元列出来的矩阵,大概长这样:

\[\begin{bmatrix}
a_{1,1}&a_{1,2}&0&0&\cdots&0\\
a_{2,1}&a_{2,2}&a_{2,3}&0&\cdots&0\\
a_{3,1}&a_{3,2}&a_{3,3}&a_{3,4}&\cdots&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
a_{n-2,1}&a_{n-2,2}&a_{n-2,3}&a_{n-2,4}&\cdots&a_{n-2,n}\\
a_{n-1,1}&a_{n-1,2}&a_{n-1,3}&a_{n-1,4}&\cdots&a_{n-1,n}\\
a_{n,1}&a_{n,2}&a_{n,3}&a_{n,4}&\cdots&a_{n,n}\\
\end{bmatrix}
\]

总之就是主对角线左边是满的,右边有一格有值。

那么我们高斯消元的时候每次只会对三个值造成影响,那么复杂度就降为\(O(Tn^2)\),足以通过此题。

#include<bits/stdc++.h>
using namespace std; void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
} void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double
#define ll long long const int maxn = 1.5e3+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7; int n,P,k,m,p[maxn],inv[maxn],fac[maxn],ifac[maxn],a[maxn][maxn],im; int add(int x,int y) {return x+y>mod?x+y-mod:x+y;}
int del(int x,int y) {return x-y<0?x-y+mod:x-y;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;} int qpow(int aa,int x) {
int res=1;
for(;x;x>>=1,aa=mul(aa,aa)) if(x&1) res=mul(res,aa);
return res;
} void solve() {
read(n),read(P),read(m),read(k);im=qpow(m+1,mod-2);
if(k==0) return puts("-1"),void();
if(m==0) {
if(k==1) puts("-1");
else {int res=0;for(;P>0;) {if(P<n) P++;P-=k;res++;}write(res);}return ;
}
inv[0]=inv[1]=1;for(int i=2;i<=n;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
fac[0]=1;for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
ifac[0]=1;for(int i=1;i<=n;i++) ifac[i]=mul(ifac[i-1],inv[i]);
p[0]=mul(qpow(m,k),qpow(qpow(m+1,k),mod-2));
for(int i=1;i<=n;i++) p[i]=mul(mul(p[i-1],mul(i>k?0:k-i+1,inv[i])),qpow(m,mod-2)); for(int i=1;i<n;i++) {
a[i][n+1]=a[i][i]=mod-1;
for(int j=0;j<i;j++) a[i][i-j]=add(a[i][i-j],mul(mul(im,m),p[j]));
for(int j=0;j<=i;j++) a[i][i+1-j]=add(a[i][i+1-j],mul(im,p[j]));
}a[n][n+1]=a[n][n]=mod-1;
for(int i=0;i<n;i++) a[n][n-i]=add(a[n][n-i],p[i]); a[1][2]=mul(a[1][2],qpow(a[1][1],mod-2));
if(n!=1) a[1][n+1]=mul(a[1][n+1],qpow(a[1][1],mod-2));
a[1][1]=1; for(int i=2;i<=n;i++) {
for(int j=1;j<i;j++) {
if(!a[i][j]) continue;
a[i][j+1]=del(a[i][j+1],mul(a[j][j+1],a[i][j]));
a[i][n+1]=del(a[i][n+1],mul(a[j][n+1],a[i][j]));
a[i][j]=0;
}
a[i][i+1]=mul(a[i][i+1],qpow(a[i][i],mod-2));
if(i!=n) a[i][n+1]=mul(a[i][n+1],qpow(a[i][i],mod-2));
a[i][i]=1;
} for(int i=n-1;i;i--) a[i][n+1]=del(a[i][n+1],mul(a[i+1][n+1],a[i][i+1]));
write(a[P][n+1]); for(int i=1;i<=n;i++) a[i][i]=a[i][i+1]=a[i][n+1]=0;
} int main() {
int t;read(t);while(t--) solve();
return 0;
}

最新文章

  1. iOS 地图定位及大头针的基本使用
  2. 20145215&amp;20145307《信息安全系统设计基础》实验二 固件设计
  3. Solution for Error FRM-92095: Oracle Jnitiator version too low
  4. MapWinGIS.ocx 注册
  5. 如何让网页在浏览器标题栏显示自己制作的图标ico
  6. OpenCV(5) 对比度和亮度
  7. 示例在同一台机器上使用RMAN克隆数据库
  8. Java读取、创建xml(通过dom方式)
  9. 【Python学习笔记】集合
  10. C++ STL之list容器的基本操作
  11. 问题.NETwebservice其他电脑无法使用-测试窗体只能用于来自本地计算机的请求
  12. kettle不能正常自动获取字段
  13. Eclipse配色插件
  14. EL表达式(1)
  15. thinkphp5.0学习笔记(三)获取信息,变量,绑定参数
  16. 【复习】VueJS之内部指令
  17. 【程序员札记#学习&amp;&amp;塑形# 】2018年5月04号
  18. Hello World 程序的起源与历史
  19. 如何快速实现 markdown 转 HTML 文档?
  20. 丑数(python)

热门文章

  1. leetcode-最大子序和(动态规划讲解)
  2. 41. Maximum Subarray
  3. 一个五位数ABCDE乘以9,得到EDCBA,求此五位数
  4. Educational Codeforces Round 32 Problem 888C - K-Dominant Character
  5. 关闭Tomcat进程 一条语句(必看)
  6. css贝塞尔曲线模仿饿了么购物车小球动画
  7. 常用web资源
  8. NYOJ 35 表达式求值(逆波兰式求值)
  9. 1001 Duplicate Pair
  10. 【linux】- nohup 和 &amp;