UOJ514 「UR#19」通用测评号

link

contest link

考场上推出来了式子,手算样例算错,然后扔了,赛后发现算错,重算了一遍发现是对的。

「你每次会等概率随机选一个没有满的燃料舱」

考虑也可以选择满了的燃料舱,这不会影响答案

这样每次选每个燃料舱的概率都是一样的。

考虑枚举最后一个到b的燃料舱,再枚举一个满了的燃料舱计算方案数

记$S(i)=\frac{\frac{x}{n}^i}{i!}$

满了的方案数的指数生成函数为$e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i)$

其它的不一定满,方案数为$e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i)$

最后这个燃料舱的第b次操作一定在最后,所以$\cdot \frac{1}{n}$然后只考虑前面的操作$S(b-1)$

那么满足条件的概率的指数生成函数为$(n-1)(e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i))(e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i))^{n-2}S(b-1)$

设生成函数为$F(x)=\sum \frac{a_ix^i}{i!}$,则设$G(x)=\sum a_ix^i$,答案为$G(1)$,也就是$\sum a_i$。

考虑计算这个函数。

由于exp很难处理,考虑把式子展开成$\sum e^{\frac{ix}{n}}F_i(x)$的形式。

先考虑$(e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i))^{n-2}$,则答案是$\sum_{i=0}^{n-2}\binom{n-2}{i}e^{\frac{ix}{n}}(-\sum_{i=0}^{b-1}S(i))^{n-2-i}$,

乘上$e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i)$也类似。

由于得到的多项式次数$\lt na$,所以可以先DFT,乘完再IDFT

这一部分的复杂度是$O(n^2a\log(na))$,也就是$n$次IDFT的复杂度。

考虑计算答案。生成函数可以拆成$c\cdot e^{ax}\frac{x^b}{b!}$的形式,对于每个这种式子计算答案。

$e^{ax}\frac{x^b}{b!}=\sum_{i=0}^{\infty}\frac{a^ix^{i+b}}{i!b!}=\sum_{i=0}^{\infty}a^{i}\binom{i+b}{i}\frac{x^{i+b}}{(i+b)!}$

那么得到的普通型生成函数为$\sum_{i=0}^{\infty}\binom{i+b}{i}a^ix^{i+b}=\frac{x^b}{(1+ax)^{b+1}}$。

于是做完了。

代码(已define int long long):

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
const int p=998244353,G=114514;
int inv[62505],fac[62505],invf[62505],pw[62505];
int cnt[255],n,a,b,s,k,ans,w=1;
int f[255][65537],iN,N;
int fpm(int a,int b){
int c=1;for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
return c;
}
int f1[65537],f2[65537];
int _w[1<<17|5],rev[1<<16|5];
int Sum(int a,int b){return (a+=b)>=p?a-p:a;}
void dft(int *a){
for(int i=0;iif(i>rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i1){
for(int j=0;j
for(int k=0;k
int u=a[j+k],v=a[j+k+i]*_w[k+i]%p;
a[j+k]=Sum(u,v);
a[j+k+i]=Sum(u,p-v);
}
}
}
}
void idft(int *a){
reverse(a+1,a+N);
dft(a);
for(int i=0;i
}
signed main(){
#ifdef QAQAutoMaton
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
read(n,a,b);
int w=(a-1)+(n-1)*b;
fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
for(int i=2;i<=w;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=inv[i]*invf[i-1]%p;
}
int in=inv[n];
pw[0]=1;
for(int i=1;i<=w;++i){
pw[i]=pw[i-1]*in%p;
}
N=1;
while(N<=w)N<<=1;
for(int i=1;i1){

int ww=fpm(G,(p+1)/(i<<1)),w=1;
for(int j=0;j
_w[i+j]=w;
w=w*ww%p;
}
}
for(int i=1;i
rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
}
iN=fpm(N,p-2);
for(int i=0;i
for(int i=0;i

dft(f1);dft(f2);
for(int i=0;i0][i]=1;

for(int i=1;i<=n-2;++i){
for(int j=0;j-1][j]*f1[j]%p;

}
for(int i=0;i<=n-2;++i){
int C=fac[n-2]*invf[i]%p*invf[n-2-i]%p;
for(int j=0;j
}
for(int i=n-2;~i;--i){
for(int j=0;j1][j]=(f[i+1][j]+f[i][j]*f2[j])%p;

}
for(int i=0;i<=n-1;++i){
idft(f[i]);
}
for(int i=0;i<=n-1;++i){
int wx=n*inv[i+1]%p,cur=invf[b-1]*pw[b-1]%p;
for(int j=0;j-1;++j)cur=cur*wx%p;

for(int j=0;j<=w;++j){
cur=cur*wx%p;
ans=(ans+f[i][j]*fac[j+b-1]%p*cur)%p;
}
}
write(ans*(n-1)%p,'\n');
return 0;
}
#

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×