「FCS NOI 2018 day1」残缺的算式 - 表达式运算+递推+第一类Stirling数 | Bill Yang's Blog

「FCS NOI 2018 day1」残缺的算式 - 表达式运算+递推+第一类Stirling数

题目大意

    小明有一套玩具卡片。这套卡片中,有$n$张是数字卡片,这$n$张数字卡片上分别写有一个正整数$1,2,\ldots,n$;还有若干张符号卡片,每张符号卡片上写有符号$\underline +,\underline -,\underline{*},\underline(,\underline)$之一。
    小明最喜欢用这套卡片来摆算式,然后计算它的结果。当然,摆算式时不必用完所有的卡片。
    一天,小明摆好了一个算式。然而,准备计算前,一个熊孩子把算式中的数字卡片全部取走了,只剩下符号卡片和原来数字卡片所在的空位。也就是说,现在的算式可能是这样的:(_+_*_)*(_*_-_)+_(这里_代表原来放有数字卡片的空位)。
    无奈小明已不记得原来每个位置填的数字卡片上的数分别是多少,他只能假设每
种可能的算式作为原算式的概率相等。现在,小明想知道,原算式的结果的期望值是多少?
    形式化地,设有$m$种可能的算式,它们的运算结果分别为$s_1,s_2,\ldots,s_m$,那么原算式的结果的期望值$E$为


题目分析

尝试把表达式展开:

由期望的线性性质:

即可以计算每一项的期望
实际上次数一样的$x_1x_2\cdots x_k$项期望也是一样的,所以只要处理出$c_k$表示所有$k$次项的系数和。
$c$系数可以使用表达式处理进行求解。
例如使用表达式树,表达式栈。
标解给出了一种简洁的表达式栈的写法,只要系统栈不爆,这样就很好写。

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
void add(int &x,int v) {x+=v;if(x>=mod)x-=mod;}

struct poly {
int m,*c;
poly(int m=0):m(m) {c=new int[m+1];}
};

poly operate(const poly &a,char opt,const poly &b) {
poly x=poly(opt=='*'?a.m+b.m:max(a.m,b.m));
if(opt=='*') {
for(int i=0; i<=x.m; i++)x.c[i]=0;
for(int i=0; i<=a.m; i++)
for(int j=0; j<=b.m; j++)
add(x.c[i+j],1ll*a.c[i]*b.c[j]%mod);
} else for(int i=0; i<=x.m; i++)x.c[i]=((i<=a.m?a.c[i]:0)+(i<=b.m?((b.c[i]*(opt=='+'?1:-1))+mod)%mod:0))%mod;
return x;
}
poly split(char *&s);
poly block(char *&s) {
poly x;
if(*s=='_')x=poly(1),x.c[0]=0,x.c[1]=1;
else x=split(++s);
s++;
return x;
}
poly mul(char *&s) {
poly x=block(s);
while(*s=='*')x=operate(x,'*',block(++s));
return x;
}
poly split(char *&s) {
poly x=mul(s);
while(*s=='+'||*s=='-') {char o=*s;x=operate(x,o,mul(++s));}
return x;
}

简单解释一下代码。
operate函数对$a,b$两个表达式进行运算,计算新的$c$。
split函数用同层的$+,-$号分割表达式,并计算$c$。
mul函数用乘号分割split后的表达式,并计算$c$。
block函数的意思是找出一个同层的表达式块,如第一个位置是_,就返回_,如第一个位置是$($,返回括号内的表达式块。

算法一

现在我们得到了系数$c$,只需要计算$i$个数选$j$的积的期望即可。
设$f(i,j)$表示从$1,2\ldots,i$中选$j$个数的乘积之和。

然后再除掉分母即可得到期望。
时间复杂度$O(\left|S\right|n)$,可以拿到$80$分,代码见下。

算法二

怎么优化算法一呢?
算法一的瓶颈在于$n$。
现在引入三个定理:

定理一

证明:
由于$\binom nx=\frac{x+1}{n+1}\binom{n+1}{x+1}$,
又由于$\binom nx=\binom{n-1}x+\binom{n-1}{x-1}$(Pascal公式),
因此:

故$n\binom nx=(x+1)\binom n{x+1}+x\binom nx$,Q.E.D。

定理二

证明:

易知。

定理三

这里证过了。

有了这三个定理,现在我们来找规律。

感受一下这个规律。
通过三个定理的迭代,可以在组合数的上标不变的情况下对组合数下标进行递推。
$f(i,j)$具有$\sum\limits_{k=0}^{2j}\alpha_{j,k}\binom{i+1}k$的形式,其中$\alpha_j,k$为常系数。
为什么是$2j$呢?观察上述规律,每次下标加了$2$,还要注意低位没了,系数要清零。
同时注意,$\alpha_{j,\underline k}$与$\binom {i+1}{\underline k}$对应。
此时我们可以将$f(i,j)$视作一个多项式。

代入$f(i,j)$的递推式(定理二):

由上面的对应关系可知:
$\binom{i+1}{\underline{k+2}}$与$\alpha_{j,\underline{k+2}}$对应,$\binom{i+1}{\underline{k+1}}$与$\alpha_{j,\underline{k+1}}$对应。
即:
上个多项式第$k$项乘上$k+1$得到当前第$k+2$项,乘上$k$得到当前第$k+1$项。

因此得到$\alpha_{j-1,\ldots}$到$\alpha_{j,\ldots}$的转移:

即$f(i,j-1)$到$f(i,j)$的变化,与第一维$i$无关。

令$i=n$,即可得到$f(n,j)$的多项式。
可以在$O(\left|S\right|)$的时间内计算$f(n,j)$的值。
可以在$O(\left|S\right|)$的时间内递推得到所有$f(n,j)$。
套入表达式的系数即可快速计算答案,时间复杂度$O(\left|S\right|^2)$。
下面的满分代码用的就是这种算法。

算法三

$f(i,k)$是一个$2k$次多项式,可以用拉格朗日插值法$O(k^2)$求出。

算法四

$f(i,j)$实际上是第一类斯特林数$i$行倒数$j$个数,可以用FFT计算,时间复杂度$O(k\log k)$。


代码

$80$分:

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
#include<bits/stdc++.h>

using namespace std;

const int maxn=5005,mod=1e9+7;

void add(int &x,int v) {x+=v;if(x>=mod)x-=mod;}

struct poly {
int m,*c;
poly(int m=0):m(m) {c=new int[m+1];}
};

poly operate(const poly &a,char opt,const poly &b) {
poly x=poly(opt=='*'?a.m+b.m:max(a.m,b.m));
if(opt=='*') {
for(int i=0; i<=x.m; i++)x.c[i]=0;
for(int i=0; i<=a.m; i++)
for(int j=0; j<=b.m; j++)
add(x.c[i+j],1ll*a.c[i]*b.c[j]%mod);
} else for(int i=0; i<=x.m; i++)x.c[i]=((i<=a.m?a.c[i]:0)+(i<=b.m?((b.c[i]*(opt=='+'?1:-1))+mod)%mod:0))%mod;
return x;
}
poly split(char *&s);
poly block(char *&s) {
poly x;
if(*s=='_')x=poly(1),x.c[0]=0,x.c[1]=1;
else x=split(++s);
s++;
return x;
}
poly mul(char *&s) {
poly x=block(s);
while(*s=='*')x=operate(x,'*',block(++s));
return x;
}
poly split(char *&s) {
poly x=mul(s);
while(*s=='+'||*s=='-') {char o=*s;x=operate(x,o,mul(++s));}
return x;
}

int n,C[maxn][maxn],f[maxn][maxn],ans=0;
char s[10005];

int Quick_Pow(int a,int b) {
int ans=1;
for(; b; b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
return ans;
}

int main() {
scanf("%d%s",&n,s);
char *p=s;
poly a=split(p);
for(int i=1; i<=n; i++) {
C[i][0]=C[i][i]=1;
for(int j=1; j<i; j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
f[1][1]=1;
for(int i=1; i<=n; i++)f[i][0]=1;
for(int i=2; i<=n; i++)
for(int j=1; j<=i; j++)
f[i][j]=(1ll*f[i-1][j-1]*i%mod+f[i-1][j])%mod;
for(int i=0; i<=a.m; i++)if(a.c[i])add(ans,1ll*a.c[i]*f[n][i]%mod*Quick_Pow(C[n][i],mod-2)%mod);
printf("%d\n",(ans+mod)%mod);
return 0;
}

$100$分(算法二):

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
#include<bits/stdc++.h>

using namespace std;

const int maxn=20005,mod=1e9+7;

void add(int &x,int v) {x+=v;if(x>=mod)x-=mod;}

struct poly {
int m,*c;
poly(int m=0):m(m) {c=new int[m+1];}
};

poly operate(const poly &a,char opt,const poly &b) {
poly x=poly(opt=='*'?a.m+b.m:max(a.m,b.m));
if(opt=='*') {
for(int i=0; i<=x.m; i++)x.c[i]=0;
for(int i=0; i<=a.m; i++)
for(int j=0; j<=b.m; j++)
add(x.c[i+j],1ll*a.c[i]*b.c[j]%mod);
} else for(int i=0; i<=x.m; i++)x.c[i]=((i<=a.m?a.c[i]:0)+(i<=b.m?((b.c[i]*(opt=='+'?1:-1))+mod)%mod:0))%mod;
return x;
}
poly split(char *&s);
poly block(char *&s) {
poly x;
if(*s=='_')x=poly(1),x.c[0]=0,x.c[1]=1;
else x=split(++s);
s++;
return x;
}
poly mul(char *&s) {
poly x=block(s);
while(*s=='*')x=operate(x,'*',block(++s));
return x;
}
poly split(char *&s) {
poly x=mul(s);
while(*s=='+'||*s=='-') {char o=*s;x=operate(x,o,mul(++s));}
return x;
}

int n,len=0,a[maxn],inv[maxn];
char s[maxn];

int Quick_Pow(int a,int b) {
int ans=1;
for(; b; b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
return ans;
}

int Cal() {
int C=1,ans=0;
for(int i=0; i<=len; i++) {
add(ans,1ll*C*a[i]%mod);
C=1ll*C*(n+1-i)%mod*inv[i+1]%mod;
}
return ans;
}

int main() {
scanf("%d%s",&n,s);
char *p=s;
poly po=split(p);
inv[1]=1;
for(int i=2; i<=2*po.m+4; i++)inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;
int C=1,ans=0;
a[0]=1;
for(int i=0; i<=po.m; i++) {
add(ans,1ll*po.c[i]*Cal()%mod*Quick_Pow(C,mod-2)%mod);
C=1ll*C*(n-i)%mod*inv[i+1]%mod;
for(int i=(len+=2); i>=2; i--)a[i]=1ll*(a[i-1]+a[i-2])*(i-1)%mod;a[0]=a[1]=0;
}
printf("%d\n",(ans+mod)%mod);
return 0;
}

姥爷们赏瓶冰阔落吧~
0%