代数基本定理的证明

1. 代数基本定理 (一个$n$次方程至多有$n$个实数根.)

2. 引理-1: 极值定理

假设函数$f$定义在闭区间$(a,b)$内, 并且点$c$在$(a,b)$区间内, 如果点$c$为函数的局部最大值或最小值, 则点$c$一定为该函数的临界点, 即$f’(c)=0$或$f’(c)$不存在.

证明: 首先假设$f$在$x=c$处有一个局部最小值. 如果$f’(c)$不存在, 则它就是一个临界点, 即证. 另一方面, 如果$f’(c)$存在, 那么:
$$
f’(c)=\lim\limits_{h\to0}\frac{f(c+h)-f(c)}{h}.
$$
由于$f$在$c$上有一个局部最小值, 因而我们知道当$c+h$非常接近$c$时, $f(c+h)\ge f(c)$. 当然, 只有当$h$接近于$0$时, $c+h$才会非常接近$c$. 对于这样的$h$, 上述分式中的分子$f(c+h)-f(c)$一定是非负的.
当$h>0$时, 量$\frac{f(c+h)-f(c)}{h}$一定是非负的; 因此左极限$\lim\limits_{h\to0^+}{\frac{f(c+h)-f(c)}{h}} \ge 0$;

当$h<0$时, 量$\frac{f(c+h)-f(c)}{h}$一定是非正的; 因此右极限$\lim\limits_{h\to0^-}{\frac{f(c+h)-f(c)}{h}} \le 0$;

因为双侧极限存在, 所以左右极限相等,都为$0$, 即只有当$f’(c)=0$时或$f’(c)$不存在时, 点$c$为函数$f$的局部最小值.

当$f$在$x=c$处有一个局部最大值时, 同理可证. $\qquad \Box$

3. 引理-2: 罗尔定理

假设函数$f$在闭区间$[a,b]$内连续, 在开区间$(a,b)$内可导. 如果$f(a)=f(b)$, 那么在开区间$(a,b)$内至少存在一点$c$, 使得$f’(c)=0$.

证明: (1). 若区间最大值和区间最小值都出现在端点$a,b$上. 由于$f(a)=f(b)$, 那么该函数在区间$[a,b]$内一定是常数, 则对于任意在此区间内的点$c$, 都有$f’(c)=0$.

(2). 若区间最小值不出现在端点$a$上, 则区间最小值一定在区间$(a,b)$上, 设为点$c$. 由于$f$在开区间$(a,b)$内可导, 由极值定理, 得: $f’(c)=0$.

(3). 若区间最大值不出现在端点$a$上, 同(2)可证. $\qquad \Box$

4. 回到原命题

设该$n$次多项式为$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$, 若其有$n+1$个实数根, 设为$x_1<x_2<\cdots<x_{n+1}$. 显然其在$\mathbb{R}$上可导, 对区间$[x_1,x_2]$, $[x_2, x_3]$, $\cdots$, $[x_n, x_{n+1}]$使用罗尔定理, 得:

$n-1$次多项式$f’(x)=b_{n-1}x^{b-1}+\cdots+b_0$至少有$n$个实数根, 设为$y_1<y_2<\cdots<y_n$,且其在$\mathbb{R}$上可导, 对区间$[y_1,y_2]$, $[y_2,y_3]$, $\cdots$, $[y_{n-1}, y_n]$使用罗尔定理, 得:

$\cdots\cdots\cdots$

最终可得$1$次多项式$f^{(n-1)}(x)=Ax+B$至少有$2$个实数根, 矛盾!

所以$n$次多项式$f(x)$至多有$n$个实数根. $\qquad \Box$

实现高精度存储, 比较和运算(加, 减, 乘, 除, 模, 绝对值)
这个高精度里面保存了
- 数字($v$数组)
- 负数标志($is$ $minus$变量)

思路

1. 初始化函数
   (1). 最开始$is$ $minus$为$false$
   (2). 为了方便, $v$数组要清除

2. $change()$函数
   (1). 处理前导$0$
   (2). 处理$-0$
   (3). 处理有数字超过$10$
   (4). 处理最高位有进位

3. 重载$=$号 ($BigIntger = BigIntger$)
   (1). 新建一个$BigIntger$类
   (2). 将这个变量的$is$ $minus$变成这一个的$is$ $minus$
   (3). 将这个变量的$v$数组变成这一个的$v$数组

4. 重载比较符号

   1. $<$号
      (1). 如果两个数为一正一负, 则第一个的$is$ $minus$的值就是答案
      (2). 如果两个数都是正数, 则按照原本的比较方式进行运算
      (3). 否则, 就按照原本的比较方式取反进行运算
   2. $>$号
      (1). 直接返回$b<a$
   3. $!=$号
      (1). 直接返回$a>b$||$a>b$
   4. $==$号
      (1). 直接返回$!(a!=b)$
   5. 重载$<=$号
      (1). 直接返回$(a==b)||(a<b)$
   6. 重载$>=$号
      (1). 直接返回$(a==b)||(a>b)$

5. 加法
   (1). 如果$a$和$b$同正负
   · 则按照普通的高精度加法加了即可, $c$和$a$、$b$同正负
   (2). 否则
   · if $a$的绝对值>$b$的绝对值
   · 则$c$相当于$a的绝对值-b的绝对值$, $c$和$a$同正负
   · else
   · 则$c$相当于$b的绝对值-a的绝对值$, $c$和$b$同正负

6. 减法
   (1). 将$a-b$看成$a+(-b)$即可以用已经写好的加法完成

7. 乘法
   (1). 最后结果的$is$ $minus$为两个$is$ $minus$的异或值
   (2). 然后使用普通的高精度乘法即可

8. 除法
   (1). 最后结果的$is$ $minus$为两个$is$ $minus$的异或值
   (2). 然后使用普通的高精度除法即可

9. mod运算
   (1). $a \mod{b} = a-[\frac{a}{b}]$

10. 快速幂
    (1). 基本上相当于普通的快速幂

11. 重载输入$>>$符号
    (1). 首先读入一个字符串
    (2). 如果第一个字符为’-‘, 则这个数的$is$ $minus$更新成$true$
    (3). 倒序存储每一位数字

12. 重载输出$<<$符号
    (1). 如果$is$ $minus$为$true$, 则先输出一个负号
    (2). 倒序输出所有数字

#ifndef _MINUS_OF_BIGINTGER_H
#define _MINUS_OF_BIGINTGER_H

#include<bits/stdc++.h>
using namespace std;

struct BigIntger{
    bool is_minus;
    vector<int> v;

    // 将一个不合法的数等价变换成合法的数 
    BigIntger& change(){
        while(this->v.size() > 1 && this->v.back() == 0) // 前导0 
            this->v.pop_back();
        if(this->v.back() == 0 && this->v.size() == 1 && this->is_minus) // -0 
            this->is_minus = false;
        for(int i = 1; i < this->v.size(); i ++){ // 有数字超过10 
            this->v[i] += this->v[i - 1] / 10;
            this->v[i - 1] %= 10;
        }
        while(this->v.back() >= 10){ // 最高位有进位 
            this->v.push_back(this->v.back() / 10);
            this->v[this->v.size() - 2] %= 10;
        }
        return *this;
    }

    BigIntger& operator = (const BigIntger& b){
        this->is_minus = false;
        this->v.clear();
        this->is_minus = b.is_minus;
        for(int i = 0; i < b.v.size(); i ++)
            this->v.push_back(b.v[i]);
        return *this;
    }

    BigIntger& operator = (int x){
        this->is_minus = false, this->v.clear();
        if(x < 0){
            x = -x;
            this->is_minus = true;
        }
        while(x > 0){
            this->v.push_back(x % 10);
            x /= 10;
        }
        return *this;
    }
};

// 比较
bool operator < (const BigIntger a, const BigIntger b){
    int x = a.v.size(), y = b.v.size();
    if(a.is_minus != b.is_minus)
        return a.is_minus; 
    if(a.is_minus == false){
        if(x != y)
            return x < y;
        for(int i = x - 1; i >= 0; i --)
            if(a.v[i] != b.v[i])
                return a.v[i] < b.v[i];
        return false;
    }
    else{
        if(x != y)
            return x > y;
        for(int i = x - 1; i >= 0; i --)
            if(a.v[i] != b.v[i])
                return a.v[i] > b.v[i];
        return false;
    }
}

bool operator > (const BigIntger a, const BigIntger b){
    return (b < a);
}

bool operator == (const BigIntger a, const BigIntger b){
    return (!(a > b)) && (!(a < b));
}

bool operator <= (const BigIntger a, const BigIntger b){
    return (a < b) || (a == b);
}

bool operator >= (const BigIntger a, const BigIntger b){
    return (a > b) || (a == b);
}

bool operator != (const BigIntger a, const BigIntger b){
    return !(a == b);
}

// 绝对值函数 
BigIntger& abs(BigIntger x){
    BigIntger& y = x;
    y.is_minus = false;
    return y;
}

// input
istream& operator >> (istream& in, BigIntger& n){
    string s;
    in >> s;
    n.v.clear();
    n.is_minus = false;
    if(s[0] == '-')
        n.is_minus = true;
    for(int i = s.size() - 1; i >= (s[0] == '-'); i --)
        n.v.push_back(s[i] - '0');
    n.change();
    return in;
}

// output
ostream& operator << (ostream& out, BigIntger& n){
    n.change();
    int x = n.v.size();
    if(x == 0){
        out << x;
        return out;
    }
    if(n.is_minus == true)
        out << '-';
    for(int i = n.v.size() - 1; i >= 0; i --)
        out << n.v[i];
    return out;
}

// 加法 
BigIntger& operator += (BigIntger& a, BigIntger& b){
    a.change(), b.change();
    if(a.is_minus == b.is_minus){
        if(a.v.size() < b.v.size())
            a.v.resize(b.v.size());
        for(int i = 0; i < b.v.size(); i ++)
            a.v[i] = b.v[i] + a.v[i];
        return a.change();
    }
    else{
        BigIntger x = abs(a);
        BigIntger y = abs(b);
        if(x >= y){
            if(a.v.size() < b.v.size())
                a.v.resize(b.v.size());
            for(int i = 0; i < b.v.size(); i ++){
                while(a.v[i] < b.v[i]){
                    a.v[i + 1] --;
                    a.v[i] += 10;
                }
                a.v[i] = a.v[i] - b.v[i];
            }
            return a.change();
        }
        else{
            a.is_minus = !a.is_minus;
            if(a.v.size() < b.v.size())
                a.v.resize(b.v.size());
            for(int i = 0; i < a.v.size(); i ++){
                while(a.v[i] > b.v[i]){
                    a.v[i + 1] ++;
                    a.v[i] -= 10;
                }
                a.v[i] = b.v[i] - a.v[i];
            }
            return a.change();
        }
    }
}

BigIntger operator + (BigIntger a, BigIntger b){
    BigIntger c = a;
    c += b;
    return c;
}

// 减法 
BigIntger& operator -= (BigIntger& a, BigIntger b){
    BigIntger& c = b;
    c.is_minus = 1 - b.is_minus;
    a += c;
    return a;
}

BigIntger operator - (BigIntger a, BigIntger b){
    BigIntger c = a;
    c -= b;
    return c;
}

// 乘法 
BigIntger operator * (BigIntger a, BigIntger b){
    a.change(), b.change();
    BigIntger c;
    c.is_minus = a.is_minus ^ b.is_minus;
    c.v.resize(a.v.size() + b.v.size());
    for(int i = 0; i < a.v.size(); i ++)
        for(int j = 0; j < b.v.size(); j ++)
            c.v[i + j] += a.v[i] * b.v[j];
    c.change();
    return c;
}

BigIntger& operator *= (BigIntger& a, BigIntger& b){
    return a = a * b;
}

// 除法 
BigIntger operator / (BigIntger a, BigIntger b){
    BigIntger ans, now;
    ans.v.clear(), ans.is_minus = a.is_minus ^ b.is_minus;
    now.v.clear(), now.is_minus = false;
    for(int i = a.v.size() - 1; i >= 0; i --){
        now.v.push_back(a.v[i]);
        int d = 0;
        while(now >= b){
            now -= b;
            d ++;
        }
        ans.v.push_back(d);
    }
    ans.change();
    return ans;
}

BigIntger& operator /= (BigIntger& a, BigIntger b){
    return a = (a / b);
}

// mod 运算 
BigIntger operator % (BigIntger a, BigIntger b){
    return a - (a / b) * b;
}

BigIntger& operator %= (BigIntger& a, BigIntger b){
    return a = (a % b);
}

// 快速幂
BigIntger quick_pow(BigIntger a, int k){
    BigIntger ans, zero, one;
    ans.is_minus = false, zero.is_minus = false, one.is_minus = false;
    ans.v.clear(), zero.v.clear(), one.v.clear();
    ans.v.push_back(1), one.v.push_back(1);
    while(k > 0){
        if(k & 1){
            ans = ans * a;
        }
        a = a * a;
        k /= 2;
        cout << ans << ' ' << a << ' ' << k << endl;
    }
    return ans;
}

#endif

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 55, M = 42;

LL f[N][N][M];
int w[N];

void add(LL a[], LL b[]){
    LL c[M];
    memset(c, 0, sizeof(c));

    int t = 0;

    for(int i = 0; i < M; i ++){
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }

    memcpy(a, c, sizeof(c));
}

void mul(LL a[], LL b){
    LL c[M];
    memset(c, 0, sizeof(c));

    LL t = 0;

    for(int i = 0; i < M; i ++){
        t += a[i] * b;
        c[i] += t % 10;
        t /= 10;
    }

    memcpy(a, c, sizeof(c));
}

bool cmp(LL a[], LL b[]){
    for(int i = M - 1; i >= 0; i --)
        if(a[i] != b[i])
            return a[i] < b[i];

    return false;
}

void print(LL a[]){
    int k = M - 1;
    while(k >= 0 && a[k] == 0)
        k --;

    while(k >= 0){
        printf("%lld", a[k]);
        k --;
    }
}

int main(){
    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; i ++)
        scanf("%d", &w[i]);

    for(int len = 3; len <= n; len ++)
        for(int l = 1; l + len - 1 <= n; l ++){
            int r = l + len - 1;
            f[l][r][M - 1] = 1;

            for(int k = l + 1; k <= r - 1; k ++){
                LL tmp[M]; memset(tmp, 0 ,sizeof(tmp)); tmp[0] = 1;
                mul(tmp, w[l]), mul(tmp, w[k]), mul(tmp, w[r]);
                add(tmp, f[l][k]), add(tmp, f[k][r]);

                if(cmp(tmp, f[l][r]))
                    memcpy(f[l][r], tmp, sizeof(tmp));
            }
        }

    print(f[1][n]);

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 205;

int f[N][N], w[N];

int main(){
    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; i ++){
        scanf("%d", &w[i]);

        w[i + n] = w[i];
    }

    for(int len = 1; len <= n + 1; len ++)
        for(int l = 1; l + len - 1 <= 2 * n; l ++){
            int r = l + len - 1;

            for(int k = l + 1; k <= r - 1; k ++)
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }

    int res = 0;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i][i + n]);

    printf("%d\n", res);

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 405;

int w[N], s[N];
int f[N][N], g[N][N]; // f存最小值, g存最大值 

int main(){
    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; i ++){
        int t;
        scanf("%d", &t);

        w[i] = w[i + n] = t;
    }

    for(int i = 1; i <= 2 * n; i ++)
        s[i] = s[i - 1] + w[i];

    memset(f, 0x3f, sizeof(f));
    memset(g, -0x3f, sizeof(g));

    for(int len = 1; len <= n; len ++)
        for(int l = 1; l + len - 1 <= 2 * n; l ++){
            int r = l + len - 1;

            if(len == 1)
                f[l][r] = g[l][r] = 0;

            else{
                for(int k = l; k < r; k ++){
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }

    int minv = INT_MAX, maxv = INT_MIN;

    for(int i = 1; i <= n; i ++){
        minv = min(minv, f[i][i + n - 1]);
        maxv = max(maxv, g[i][i + n - 1]);
    }

    printf("%d\n%d\n", minv, maxv);

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second

const int N = 19, M = 1 << N;
const double eps = 1e-8;

pair<double, double> q[N];
int path[N][N];

int f[M];

int n, m;

int cmp(double x, double y){
    if(fabs(x - y) < eps)
        return 0;

    if(x < y)
        return -1;
    else
        return 1;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        int m; // 题干中的m没有任何作用
        scanf("%d %d", &n, &m);

        for(int i = 0; i < n; i ++)
            scanf("%lf %lf", &q[i].x, &q[i].y);

        memset(path, 0, sizeof(path)); // 注意这里, 因为有多组数据

        for(int i = 0; i < n; i ++){
            path[i][i] = 1 << i;
            for(int j = 0; j < n; j ++){
                double x1 = q[i].x, y1 = q[i].y;
                double x2 = q[j].x, y2 = q[j].y;

                if(!cmp(x1, x2)) // x1 = x2的情况
                    continue;

                double a = (y1 / x1 - y2 / x2) / (x1 - x2), b = y1 / x1 - a * x1;

                if(cmp(a, 0) >= 0)
                    continue;

                int state = 0;
                for(int k = 0; k < n; k ++){
                    double x = q[k].x, y = q[k].y;
                    if(!cmp(y, a * x * x + b * x)) // 点k也在这条抛物线上
                        state += (1 << k);
                }

                path[i][j] = state;
            }
        }

        memset(f, 0x3f, sizeof(f));
        f[0] = 0; // 初始化

        for(int i = 0; i + 1 < 1 << n; i ++){
            int x = 0;

            for(int j = 0; j < n; j ++) // 找到一个没有被覆盖的x
                if(!(i >> j & 1)){
                    x = j;
                    break;
                }

            for(int j = 0; j < n; j ++)
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }

        printf("%d\n", f[(1 << n) - 1]);
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 105, M = 1030;

vector<int> state;

int f[2][M][M];
int g[N];
int cnt[M];

int n, m;

bool check(int u){
    for(int i = 0; i < m; i ++)
        if((u >> i & 1) && ((u >> i + 1 & 1) || (u >> i + 2 & 1)))
            return false;

    return true;
}

int count(int u){
    int res = 0;

    for(int i = 0; i < m; i ++)
        if(u >> i & 1)
            res ++;

    return res;
}

int main(){
    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < m; j ++){
            char c;
            cin >> c;
            if(c == 'H')
                g[i] += 1 << j;
        }

    for(int i = 0; i < 1 << m; i ++)
        if(check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }

    for(int i = 1; i <= n + 2; i ++)
        for(int y = 0; y < state.size(); y ++)
            for(int z = 0; z < state.size(); z ++)
                for(int x = 0; x < state.size(); x ++){
                    int a = state[x], b = state[y], c = state[z];

                    if((a & b) || (a & c) || (b & c))
                        continue;

                    if((g[i] & c) | (g[i - 1] & b))
                        continue;

                    f[i & 1][y][z] = max(f[i & 1][y][z], f[i - 1 & 1][x][y] + cnt[c]);
                }

    printf("%d\n", f[n + 2 & 1][0][0]);

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 13, M = 1 << N, Mod = 1e8;

int f[N][M];
int g[N];

vector<int> state;
vector<int> head[M];

int n, m;

bool check(int u){
    for(int i = 0; i < m - 1; i ++)
        if((u >> i & 1) && (u >> (i + 1) & 1))
            return false;

    return true;
}

int main(){
    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < m; j ++){
            int t;
            scanf("%d", &t);

            g[i] += (!t) << j;
        }

    for(int i = 0; i < 1 << m; i ++)
        if(check(i))
            state.push_back(i);

    for(int i = 0; i < state.size(); i ++)
        for(int j = 0; j < state.size(); j ++){
            int a = state[i], b = state[j];
            if((a & b) == 0)
                head[i].push_back(j);
        }

    f[0][0] = 1;
    for(int i = 1; i <= n + 1; i ++)
        for(int a = 0; a < state.size(); a ++)
            for(int x = 0; x < head[a].size(); x ++){
                int b = head[a][x];

                if(g[i] & state[a])
                    continue;

                f[i][a] = (f[i][a] + f[i - 1][b]) % Mod;
            }

    printf("%d\n", f[n + 1][0]);

    return 0;
}

连通性状态压缩DP

#include<bits/stdc++.h>
using namespace std;

const int N = 12, M = 1 << N, K = 105;

vector<int> state;
int cnt[M];
vector<int> head[M];

long long f[N][K][M];

int n, k;

bool check(int u){
    for(int i = 0; i < n; i ++)
        if((u >> i & 1) && (u >> (i + 1) & 1))
            return false;

    return true;
}

int count(int u){
    int res = 0;
    for(int i = 0; i < n; i ++)
        if(u >> i & 1)
            res ++;

    return res;
}

void init(){
    for(int i = 0; i < (1 << n); i ++)
        if(check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }

    for(int i = 0; i < state.size(); i ++)
        for(int j = 0; j < state.size(); j ++){
            int a = state[i], b = state[j];

            if((a & b) == 0 && check(a | b))
                head[i].push_back(j);
        }
}

int main(){
    scanf("%d %d", &n, &k);

    init();

    f[0][0][0] = 1;
    for(int i = 1; i <= n + 1; i ++)
        for(int j = 0; j <= k; j ++)
            for(int a = 0; a < state.size(); a ++)
                for(int x = 0; x < head[a].size(); x ++){
                    int b = head[a][x], c = cnt[state[a]];

                    if(j >= c)
                        f[i][j][a] += f[i - 1][j - c][b];
                }

    printf("%lld\n", f[n + 1][k][0]);

    return 0;
}