T1
来源： WinnieChen的考试
题意：
两组人，第一组人的能力值分别为 $a_1,a_2,…,a_n$ 第二组人的能力值为 $b_1,b_2,…,b_n$ ，$a,b\in[1,2]$ 第一组和第二组的人两两比赛，能力值为 $x , y$ 进行比赛时能力值为 $x$ 的人获胜概率为 $\displaystyle\frac {x}{x+y}$ 。
求第一组中每个玩家获胜场次的期望（要求误差 $10^{-3}$）。
题解：
发现对于每个 $a$ 求的其实是： $\displaystyle \sum\limits_{i=1}^{m} \dfrac{a}{a + b_i}$ 。发现并不好求，考虑转化一下，
对其中的$\displaystyle \frac{b_i}{a+b_i}$ 进行泰勒展开（$\displaystyle f(x) = \sum_{i=0}^{\infty } \frac{f^{(i)}{x_0}}{i!} (x - x_0)^i$）。
泰勒展开的余项收敛条件：$\displaystyle \lim_{i\rightarrow\infty}\left( \frac{f^{(i)}{(x_0)}}{i!}(x - x_0)^i\right) = 0$ 的条件是 $x - x_0 < 1$ 。在本题中 $x\in[1,2]$ ，$x_0$ 取 1.5 这样在 $i$ 取到30左右的时候 $(x-x_0)^i$ 就已经小到可以忽略了。
因此，我们考虑如何将$g(x)=\dfrac{b_i}{x+b_i}$在$x=1.5$处展开，也就是要求出在$i\in[0,30]$时的$g^{(i)}(x)$
结论是$\displaystyle g^{(i)}(x)=(-1)^i\dfrac{b_i\times i!}{(x+b_i)^{i+1}}$
证明：考虑使用数学归纳法
显然$i=0$时原式符合条件，假设当$i=a$时满足条件，则只需证明$i=a+1$时满足条件即可
由于有函数相除的求导公式$\left(\dfrac{f(x)}{g(x)}\right)’=\dfrac{f’(x)g(x)-f(x)g’(x)}{g^2(x)}$，则可以推出
得证
也就是说，根据泰勒展开，$\displaystyle g(x)=\sum_{i=0}^{\infty}(-1)^i\dfrac{b_i}{(x+b_i)^{(i+1)}}(x-x_0)^i$
有上面得到本题的 $\infty$ 取30 即可。
那么，对于$\sum g(x)$，$(x-x_0)^i$项前面的系数为每一个$g(x)$对应项系数的$\sum$
所以，使用一个数组$d$，存储$\sum g(x)$每一项的系数，对于每一个$b$所对应的$g(x)$，求出在$i\in[0,30]$时的$(-1)^i\dfrac{b_i}{(x+b_i)^{(i+1)}}$，累加进$d[i]$，则$d$数组所代表的多项式即为$\displaystyle\sum_{i=1}^m\dfrac{b_i}{x+b_i}$
接下来，遍历$a$数组，将每一个数当作$x$代入进多项式中（此处注意，多项式的自变量是$(x-x_0)$），用$m$减去所得的数即为该数答案
时间复杂度$O(30(n+m))$
Code：
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
|
#include<bits/stdc++.h>
using namespace std;
#define _ =read()
inline int read(){
int r = 0 , w = 1;
char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') w = -1; ch = getchar();}
while(ch >='0' && ch <='9') {r = r * 10 + ch -'0'; ch = getchar();}
return r * w;
}
namespace FileIO{
string InFile;
string OutFile;
void File(string s){
InFile = s + ".in";
OutFile = s + ".out";
freopen(InFile.data() , "r" , stdin);
freopen(OutFile.data() , "w" , stdout);
}
}
const int Maxn = 1000100;
double a[Maxn];
double b[Maxn];
int n;
int m;
const int Maxk = 30;
const double delta = 1.5;
double d[Maxn];
int main(){
n _ , m _;
for(int i = 1 ; i <= n ; i++) scanf("%lf" , &a[i]);
for(int i = 1 ; i <= m ; i++) scanf("%lf" , &b[i]);
for(int i = 1 ; i <= m ; i++){
double res = b[i] / (b[i] + delta);
double j = -(b[i] + delta);
d[0] += res;
for(int k = 1 ; k <= Maxk ; k++) res /= j , d[k] += res;
}
for(int i = 1 ; i <= n ; i++){
double res = 1.0;
double j = (a[i] - delta);
double ans = m;
for(int k = 0 ; k <= Maxk ; k++) ans -= res * d[k] , res *= j;
printf("%.15f\n" , ans);
}
getchar();
return 0;
}
|
来源：WinnieChen的考试
题意：
$K$ 维空间随机游走，问 $n$ 步之后走过的不同位置的个数的期望。
题解：
考虑对于每个格子会不会被经过。
$f[i]$ 表示 $i$ 步之后第一次经过某个格子的方案。
$g[i]$ 表示 $i$ 步之后在这个格子停下的方案。
$h[i]$ 表示从一个位置出发 $i$ 步回到原点的方案。
有： $\displaystyle f[i] = g[i] - \sum_{j+k = i} f[j] * h[k]$
考虑式子中的 $h[i]$ 与格子是哪个没有关系，所以式子是一个 $g \rightarrow f$ 的线性变换。
对所有的格子求和，有 $\displaystyle dp[i] = (2k)^i - \sum_{j+k = i} dp[j] * h[k]$
利用组合数直接求暴力卷积即可。
考虑求$h[i]$ ， 发现每一维度是独立的，直接进行背包就行。
Code：
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
|
#include<bits/stdc++.h>
using namespace std;
#define _ =read()
inline int read(){
int r = 0 , w = 1;
char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') w = -1; ch = getchar();}
while(ch >='0' && ch <='9') {r = r * 10 + ch -'0'; ch = getchar();}
return r * w;
}
namespace FileIO{
string InFile;
string OutFile;
void File(string s){
InFile = s + ".in";
OutFile = s + ".out";
freopen(InFile.data() , "r" , stdin);
freopen(OutFile.data() , "w" , stdout);
}
}
const int Maxn = 2050;
int n;
int m;
int k;
int P;
int C[Maxn][Maxn];
int f[Maxn];
int g[Maxn];
int h[Maxn];
int ans;
int pw[Maxn];
signed main(){
n _ , k _ , P _;
C[0][0] = 1;
for(int i = 1 ; i <= n ; i++){
C[i][0] = 1 , C[i][i] = 1;
for(int j = 1 ; j < i ; j++){
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
}
}
f[0] = 1, m = n >> 1;
for(int i = 1 ; i <= k ; i++){
for(int j = 0 ; j <= m ; j++) g[j] = f[j];
for(int j = 0 ; j <= m ; j++) f[j] = 0;
for(int j = 0 ; j <= m ; j++){
for(int o = 0 ; o <= m - j ; o++){
f[j + o] = (f[j + o] + 1ll * g[j] * C[j + o << 1][o << 1] % P * C[o << 1][o]) % P;
}
}
}
for(int i = 0 ; i <= m ; i++){
h[i] = f[i];
for(int j = 1 ; j < i ; j++){
h[i] = (h[i] - 1ll * h[j] * f[i - j] % P) % P;
h[i] = (h[i] + P) % P;
}
}
pw[0] = 1;
for(int i = 1 ; i <= n ; i++) pw[i] = 2ll * pw[i - 1] * k % P;
ans = 1ll * (n + 1) * pw[n] % P;
for(int i = 1 ; i <= m ; i++){
ans = (ans - 1ll * h[i] * pw[n - i * 2] % P * (n - 2 * i + 1) % P) % P;
if(ans < 0) ans += P;
}
cout << ans;
getchar();
return 0;
}
|
来源：WinnieChen的考试
题意：
给定一颗树，$q$ 次询问 $A$ 在 $ t_1$ 时刻从 $x$ 出发， $B$ 在 $t_2$ 时刻从 $y$ 出发，速度相同，问两人是否同时出现在一条边上（不包括顶点）。
题解：
和之前考试的题比较像，那题求得是能否相遇。
这题直接用 $LCA$ 求出路径的交，如果是同向的，比较一下时间差和路径上最长的边；如果是异向的，要判断会不会在端点相遇。
Code：