XCPC中的高等数学

约 445 个字 58 行代码 预计阅读时间 2 分钟

在《高等数学》同济大学数学系编，7版，的基础上，根据XCPC出现过的题目，摘取了部分知识点

函数

有界性

$\forall x,f(x)\le MAX$，$MAX$ 称为上界

$\forall x,f(x)\ge MIN$，$MIN$ 称为下界

$\forall x,|f(x)|<=M$，$M$ 称为界

初等函数

1. 幂函数：$y=x^k$
2. 指数函数：$y=a^x$
3. 对数函数：$y=\log_a x$
4. 三角函数：$y=\sin x,\cos x,\tan x=\frac{\sin x}{\cos x},\cot x=\frac 1{\tan x},\sec x=\frac 1{\cos x},\csc x=\frac 1{\sin x}$
5. 反三角函数：$y=\arcsin x$ 等

由以上5种，基本初等函数，经过有限次的四则运算和有限次的函数复合，的函数为初等函数

函数的极限存在的充分必要条件

$x$ 从左侧趋于 $x_0$ 记作 $x\rightarrow x_0^-$，$x$ 从右侧趋于 $x_0$ 记作 $x\rightarrow x_0^+$

$\lim\limits_{x\rightarrow x_0^-}f(x)=A=\lim\limits_{x\rightarrow x_0^+}f(x)$

无穷小与无穷大

无穷小定义

如果函数 $\lim\limits_{x\rightarrow x_0或x\rightarrow \infty}f(x)=0$，那么称函数 $f(x)$ 为当 $x\rightarrow x_0或x\rightarrow \infty$ 时的无穷小

无穷大定义

如果函数 $\lim\limits_{x\rightarrow x_0或x\rightarrow \infty}f(x)=\infty$，那么称函数 $f(x)$ 为当 $x\rightarrow x_0或x\rightarrow \infty$ 时的无穷大

无穷大和无穷小的联系

在自变量的同一变化过程中，如果 $f(x)$ 为无穷大，那么 $\frac 1{f(x)}$ 为无穷小；

反之，如果 $f(x)$ 为无穷小，且 $f(x)\ne 0$，那么 $\frac 1{f(x)}$ 为无穷大；

极限运算法则

1. 有限个无穷小之和是无穷小
2. 有界函数与无穷小的乘积是无穷小
3. 有限个无穷小之积是无穷小
4. 四则运算，即 $\lim f(x)=A,\lim g(x)=B$
   $\lim[f(x)+g(x)]=\lim f(x)+\lim g(x)=A+B$
   $\lim[f(x)-g(x)]=\lim f(x)-\lim g(x)=A-B$
   $\lim[f(x)g(x)]=\lim f(x)\lim g(x)=AB$
   $\lim[\frac{f(x)}{g(x)}]=\frac {\lim f(x)}{\lim g(x)}=\frac AB$，且 $B\ne 0$
5. 4的推论，$c$ 为常数，$\lim[cf(x)]=c\lim f(x)$
6. 4的推论，$n$ 为正整数，$\lim[f(x)]^n=[\lim f(x)]^n$
7. 复合函数的极限运算法则，先求内层函数的极限，再把这个极限代回去求外层函数的极限

几个重要极限

1. $\lim\limits_{x\rightarrow 0}\frac {\sin x}{x}=1$
2. $\lim\limits_{x\rightarrow 0}\cos x=1$
3. $\lim\limits_{x\rightarrow\infty}\left(1+\frac 1x \right)^x=e$

无穷小的比较

常见等价无穷小

1. $\sin x\sim x$
2. $\tan x\sim x$
3. $1-\cos x\sim \frac 12 x^2$
4. $e^x-1\sim x$
5. $\ln(1+x)\sim x$
6. $\sqrt[n]{1+x}-1\sim\frac xn$

等价无穷小运算法则

设 $\alpha\sim\tilde\alpha,\beta\sim\tilde\beta$，且 $\lim\frac{\tilde\beta}{\tilde\alpha}$ 存在，则 $\lim\frac{\beta}{\alpha}=\lim\frac{\tilde\beta}{\tilde\alpha}$

函数的求导法则

1. 设 $u=u(x),v=v(x)$
   $[u+v]'=u'+v'$
   $[u-v]'=u'-v'$
   $[uv]'=u'v+uv'$
   $[\frac uv]'=\frac{u'v+uv'}{v^2}$，且 $v\ne 0$
2. 反函数的求导法则，即函数 $x=f(y)$，反函数 $y=f^{-1}(x)$
   $[f^{-1}(x)]'=\frac 1{f'(y)}$
3. 复合函数的求导法则，即 $y=f(u),u=g(x)$
   $[f(g(x))]'=f'(u)g'(x)$

基本初等函数的导数公式

1. $(x^k)'=kx^{k-1}$
2. $(a^x)'=a^x\ln a$
3. $(\log_a x)'=\frac 1{xln a}$
4. $(\sin x)'=\cos x$
5. $(\cos x)'=-\sin x$
6. $(\tan x)'=\sec^2 x$
7. $(\cot x)'=-\csc^2 x$
8. $(\sec x)'=\sec x\tan x$
9. $(\csc x)'=-\csc x\cot x$
10. $(\arcsin x)'=\frac 1{\sqrt{1-x^2}}$
11. $(\arccos x)'=-\frac 1{\sqrt{1-x^2}}$
12. $(\arctan x)'=\frac 1{1+x^2}$
13. $(arccot~x)'=-\frac 1{1+x^2}$

高阶导数

对导数再次求导，即可得更高阶导数

洛必达法则

对于 $\frac 00,\frac{\infty}{\infty}$ 型的极限的商，不能用“商的极限等于极限的商”这一法则，因此用洛必达法则，即

$\lim\frac{f(x)}{F(x)}=\lim\frac{f'(x)}{F'(x)}$

泰勒公式

用多项式近似表达函数，即

$f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+...+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x)$

题目

2021ICPC网络赛2G

Given $2n$ integers, $a_1,a_2,…,a_n,b_1,b_2,…,b_n,$ and an integer $t$. You need to calculate:

$\lim\limits_{x→0}\frac{\sum\limits_{i=1}^na_i\times ln(1+b_i\times x)}{x^t}$.

Input

The first line consists of two integers $n,t$.

In the following $n$ lines, the $i$-th line consists of two integers $a_i,b_i$.

$1≤n≤100000,−100≤a_i,b_i≤100,0≤t≤5$.

Output

Please output the result of this limit.

If the result is $\infty$, please output "infinity" (without quotes). And if the result is an integer, please output this integer directly. Otherwise, the answer must be $\frac ab$, such that $a$ and $b$ are coprime and $b≥2$, please output "$a/b$".

Sample Input 1

2 2
1 1
1 -1

Sample Output 1

-1

Sample Input 2

2 1
1 1
1 -1

Sample Output 2

0

Sample Input 3

2 3
1 1
1 -1

Sample Output 3

infinity

Solution

$\lim\limits_{x→0}\frac{\sum\limits_{i=1}^na_i\times ln(1+b_i\times x)}{x^t}$

$\sum\limits_{i=1}^na_i\lim\limits_{x→0}\frac{ln(1+b_i\times x)}{x^t}$

直接对后半部分洛必达会发现洛1次之后就不是 $\frac 00$ 的形式，因此泰勒公式来近似后半部分

$f(x)=ln(1+b_i\times x)$

$f'(x)=\frac{b_i}{1+b_ix}$

$f''(x)=\frac{-b_i^2}{1+2b_ix+b_i^2x^2}$

$f'''(x)=\frac{2b_i^3+2b_i^4x}{1+4b_ix+6b_i^2x^2+4b_i^3x^3+b_i^4x^4}$

$f''''(x)=\frac{-6b_i^4-24b_i^5x-36b_i^6x^2-24b_i^7x^3-6b_i^8x^4}{(1+4b_ix+6b_i^2x^2+4b_i^3x^3+b_i^4x^4)^2}$

$f'''''(x)=...$

$x_0=0$

$f(x)=b_ix-\frac 12b_i^2x^2+\frac{1}{3}b_i^3x^3-\frac 1{4}b_i^4x^4+\frac 15b_i^5x^5+...$

$ans=\sum\limits_{i=1}^na_i\lim\limits_{x\to 0}\frac {f(x)}{x^t}$

$t=0,ans=0$

$t=1,ans=\sum\limits_{i=1}^na_ib_i$

$t=2,ans=\sum\limits_{i=1}^na_i\frac{-b_i^2}{2}$

$t=3,ans=\sum\limits_{i=1}^na_i\frac{b_i^3}{3}$

$t=4,ans=\sum\limits_{i=1}^na_i\frac{-b_i^4}{4}$

$...$

由于只有 $\frac 00$ 形式能一直洛，所以中间结果如果不是 $\frac 00$，那答案为 $\infty$

ll g[7];
string solve(int n,int t)
{
    if(t==0)
        return "0";
    ll a,b;
    for(int i=0;i<n;++i)
    {
        cin>>a>>b;
        for(int j=1;j<=t;++j)
        {
            a*=b;
            if(j&1)
                g[j]+=a;
            else
                g[j]-=a;
        }
    }
    for(int i=1;i<t;++i)
    {
        if(g[i])
            return "infinity";
    }
    ll gc=__gcd(g[t],(ll)t);
    string ans=to_string(g[t]/gc);
    if(t!=gc)
        ans+=" "+to_string(t/gc);
    return ans;
}

2021ICPC昆明C

There is an empty cup, and a dumb robot is going to fill it with $1$ liter of water.

For every turn, the robot will randomly select a real number $t$ between $0$ and $x$ ($x$ is a given number) and then fill the cup with $t$ liter of water. The robot will repeat it until the cup is full (at least $1$ liter of water has been filled).

You need to answer the expected number of turns the robot should fill.

Input

The first line contains an integer $T(T\leq 10000)$, denoting the number of test cases.

In the following $T$ lines, each line contains a real number $x(0.05\leq x\leq 10^9)$, describing a test case.

It is guaranteed that $x$ contains no more than $3$ decimal places.

Output

For each test case, output one line with a real number, denoting the expected number of turns.

Any answer with a relative or absolute error less than $10^{-4}$ will be accepted.

Sample Input 1

2
0.3
1.5

Sample Output 1

7.3332227396
1.9477340411

Solution

设 $f(x)$ 为每次均匀随机走 $[0,a]$，达到大于等于 $x$ 的期望次数，由全期望公式

$$f(x)=1+\int_{max(0,x-a)}^x\frac{f(t)}adt$$

对两边求导

$$af'(x)=f(x)-f(x-a)$$

定义近似计算

$$a\frac{f(x+\Delta x)-f(x)}{\Delta x}=f(x)-f(x-a)$$

$$f(x+\Delta x)=f(x)+\frac{\Delta x}a(f(x)-f(x-a))$$

$f(0)=1$ 表示无穷小期望为1，那么 $ans=f(1)$

由于是多组数据，原问题步长 $[0,a]$，大于等于1的期望步数，等价于，步长 $[0,1]$，大于等于 $\frac 1a$ 的期望步数，故上式改为

$$f(x+\Delta x)=f(x)+\Delta x(f(x)-f(x-1))$$

$ans=f(\frac 1a)$

const int maxn = 1e5;
const double dx = 1.0 / maxn;
double f[maxn * 20 + 100];
void init()
{
    f[0] = 1;
    for(int i=0;i<maxn;++i)
        f[i + 1] = (dx+1) * f[i];
    for (int i = maxn; i < 20 * maxn + 99; i++)
        f[i + 1] = f[i] + dx * (f[i] - f[i - maxn]);
}
double solve(double x)
{
    return f[(int)(maxn / x)];
}

推精准式子

转化为步长为 $[0,1]$ 的问题

$$f'(x)=f(x)-f(x-1)$$

对 $x$ 范围分类讨论

---

当 $x\in(0,1],f(x-1)=0$

$f'(x)=f(x)$，满足这个式子，已知的有 $e^x$

所以，$f(x)=Ce^x$

当 $x\to 0^+$,$f(x)\to 1$，所以 $f(x)=e^x$

---

当 $x\in(1,2],f(x-1)=e^{x-1}$

$f'(x)=f(x)-e^{x-1}$，满足这个式子，嗯凑凑出 $-xe^{x-1}$

所以，$f(x)=-xe^{x-1}$

当 $x\to 1^-$,$f(x)\to e$，

由于连续性，$x\to 1^+$,$f(x)\to e$，

和 $f(1^+)=-1e^{1-1}$ 差了 $1+e$

因此补上一些东西使式子成立，而 $Ce^x$ 不影响式子成立

所以，$f(x)=Ce^x-xe^{x-1}=(1+\frac 1e)e^x-xe^{x-1}=e^x-(x-1)e^{x-1}$

---

当 $x\in(2,3],f(x-1)=e^{x-1}-(x-2)e^{x-2}$

$f'(x)=f(x)-(e^{x-1}-(x-2)e^{x-2})$，满足这个式子，嗯凑凑出 $-xe^{x-1}+\frac 12(x-2)^2e^{x-2}$

所以，$f(x)=-xe^{x-1}+\frac 12(x-2)^2e^{x-2}$

当 $x\to 2^-$,$f(x)\to e$，

由于连续性，$x\to 1^+$,$f(x)\to e^2-e$，

和 $f(2^+)=-2e^{2-1}$ 差了 $e^2+e$

因此补上一些东西使式子成立，而 $Ce^x$ 不影响式子成立

所以，$f(x)=Ce^x-xe^{x-1}+\frac 12(x-2)^2e^{x-2}=(1+\frac 1e)e^x-xe^{x-1}+\frac 12(x-2)^2e^{x-2}=e^x-(x-1)e^{x-1}+\frac 12(x-2)^2e^{x-2}$

---

仿照以上方法，发现规律，$x\in(k,k+1]$

$$f(x)=\sum\limits_{i=0}^k\frac{(-1)^i}{i!}(x-i)^ie^{x-i}$$

$ans=f(\frac 1a)$

double solve(double x)
{
    x = 1 / x;
    double ans = 0, fac = 1;
    for (int i = 0; i < x; i++)
    {
        if (i & 1)
            ans -= fac * pow(x - i, i) * exp(x - i);
        else
            ans += fac * pow(x - i, i) * exp(x - i);
        fac /= (i + 1);
    }
    return ans;
}

2022ICPC沈阳A

此题暂时未上gym，等上gym了再更新Solution

Both Alice and Bob have a set of real numbers, and both sets are the union of some disjoint closed intervals. They will independently pick a real number uniformly at random from their own set, and you need to calculate the expected absolute difference between the two real numbers.

More formally, given a set of real numbers $S=\cup [l,r]$ , picking a real number $x$ from the set $S$ uniformly at random means that $P(x \in [l1, r1]) = P(x \in [l2, r2])$ holds for any two intervals $[l1, r1], [l2, r2] \subseteq S$ with the same length, i.e., $r1 − l1 = r2 − l2$.

Input

The first line contains two integers $n$ and $m (1 ≤ n, m ≤ 10^5)$, the number of intervals that form Alice’s set and Bob’s set respectively.

Each of the following $n + m$ lines contains two integers $l$ and $r (−10^9 ≤ l ≤ r ≤ 10^9)$, describing a closed interval $[l, r]$. The first $n$ intervals form Alice’s set and the next $m$ intervals form Bob’s set. Note that an interval $[l, r]$ with $l = r$ is a degenerate interval that contains a single real number.

It is guaranteed that the intervals that form someone’s set are pairwise disjoint.

Output

Output a single real number, indicating the expected absolute difference of the two real numbers picked by Alice and Bob separately.

Your answer is acceptable if its absolute or relative error does not exceed $10^{−9}$. Formally speaking, suppose that your output is $a$ and the jury’s answer is $b$, your output is accepted if and only if $\frac{|a−b|}{ max(1,|b|)} ≤ 10^{−9}$.

Sample Input 1

1 1
0 1
0 1

Sample Output 1

0.333333333333333

Sample Input 2

1 1
0 1
1 1

Sample Output 2

0.5

Note

In the first sample case, both Alice and Bob can pick any real number from $[0, 1]$, and the expected absolute difference is $\int_0^1\int_0^1 |x − y| dx dy =\frac 13$.

In the second sample case, Alice can pick any real number from $[0, 1]$ while Bob can only pick 1, and therefore the expected absolute difference is $\int_0^1 |x − 1| dx =\frac 12$.