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

路终会有尽头，但视野总能看到更远的地方。

0%

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

发表于 更新于 分类于 Valine：

题目大意

    小明有一套玩具卡片。这套卡片中，有$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;
}

相关文章
姥爷们赏瓶冰阔落吧~