【BJOI2018】治疗之雨

Source and Judge

BJOI2018
loj2513

Record

2h

Analysis

请先思考后再展开

常规地倒推dp求期望,因为会奶,未知数间有依赖性
那么搞定dp方程,然后高斯消元
$f[0]=0$ ,所以共n个未知元
显然不能暴力消元,但注意到矩阵基本上是规则的三角,不过可能左边无法到达而已

那么每次往下消元的只有一个元而已

现在唯一的问题就是在时限内计算出正确的转移系数了
$S->S2,z=S2-S$
当z=-1,就是一开始奶脸,然后全打随从:
$$
\frac{1}{m+1} (\frac{m}{m+1})^{k}
$$

除此之外:

①如果到0,因为已知未知数为0,系数无关紧要(虽然也能算)
②尚未死亡,那么要恰好受到z点伤害
如果能奶脸,考虑一开始奶了什么(方括号表示布尔):
$$
[z+1 \leq k] \frac{1}{m+1} C_k^{z+1} (\frac{1}{m+1})^{z+1} (\frac{m}{m+1})^{k-z-1}+
\frac{m}{m+1} C_k^z (\frac{1}{m+1})^z (\frac{m}{m+1})^{k-z}
$$
否则: $C_k^z (\frac{1}{m+1})^z (\frac{m}{m+1})^{k-z}$

预处理一下 $f(a)=C_k^a \frac{m^{k-a}}{(m+1)^k}$ 即可
时间为 $O(Tn^2)$

但不知道为什么是别人10倍的时间,精a了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-') f=-1;;c=getchar();}
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
const int MOD=1e9+7;
int qpower(int x,int e)
{
int ans=1;
while(e>0)
{
if(e&1) ans=(ll)ans*x%MOD;
x=(ll)x*x%MOD;e>>=1;
}
return ans;
}
int inv(int x) {return qpower(x,MOD-2);}
int add(int x,int y)
{
ll t=x+y;
if(t>=MOD) t-=MOD;
if(t<0) t+=MOD;
return t;
}
const int MAX_N=2100;
int f[MAX_N];
int gs[MAX_N][MAX_N],s[MAX_N];
void main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(gs,0,sizeof gs);
memset(s,0,sizeof s);
int n,p,m,k;scanf("%d%d%d%d",&n,&p,&m,&k);
if(k==0) {puts("-1");continue;}
f[0]=(ll)qpower(m,k)*inv(qpower(m+1,k))%MOD;
for(int a=1;a<MAX_N;a++) f[a]=(ll)f[a-1]*inv(a)%MOD*(k-a+1)%MOD*inv(m)%MOD;
if(k<MAX_N) f[k]=inv(qpower(m+1,k));//debug m=0
int invm1=inv(m+1);
for(int x=1;x<=n;x++)
{
for(int y=max(1,x-k);y<=x+1 and y<=n;y++)
{
int z=x-y;
if(y==x+1) gs[x][y]=(ll)f[0]*invm1%MOD;
else if(x==n) gs[x][y]=f[z];
else
{
gs[x][y]=(ll)m*invm1%MOD*f[z]%MOD;
if(z+1<=k) gs[x][y]=add(gs[x][y], (ll)invm1*f[z+1]%MOD );
}
}
gs[x][x]=add(gs[x][x],-1);
s[x]=add(s[x],-1);
}
for(int i=1;i<=n-1;i++) if(gs[i][i]!=0)
{
ll tmp=inv(gs[i][i]);
for(int j=i+1;j<=n;j++) if(gs[j][i]!=0)
{
ll t=(ll)gs[j][i]*tmp%MOD;
gs[j][i]=0;
gs[j][i+1]=add(gs[j][i+1],-(ll)gs[i][i+1]*t%MOD);
s[j]=add(s[j],-(ll)s[i]*t%MOD);
}
}
for(int i=n;i>=2;i--) if(gs[i][i]!=0)
{
ll tmp=inv(gs[i][i]);
for(int j=i-1;j>=1;j--) if(gs[j][i]!=0)
{
ll t=(ll)gs[j][i]*tmp%MOD;
gs[j][i]=0;
s[j]=add(s[j],-(ll)s[i]*t%MOD);
}
}
bool error=0;
for(int i=1;i<=n;i++)
{
if(s[i]!=0)
{
bool bk=1;
for(int j=1;j<=n;j++) if(gs[i][j]!=0) bk=0;
if(bk) {puts("-1");error=1;break;}//0=非0
}
if(gs[i][i]==0) {puts("-1");error=1;break;}
}
if(!error) printf("%lld\n",(ll)s[p]*inv(gs[p][p])%MOD);
}
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c2cf.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%