数学基础知识

各种类型的范围

int：0~4e9
long long:9e18
double: 位数9 精度：1e(-16)

函数

log(x)：以e为底取x的对数
log2(x):以2为底
log10(x):以10为底
round(x):四舍五入函数
floor(x):向下取整
ceil(x):向上取整
求x是m的几次幂：log(x)/log(m)
取几个数最大值：max=({a,b,c,d})

公式

$i^{2}$ 的平方和公式：
$1^{2}$+ $2^{2}$+$3^{2}$+...+$n^{2}$=$\frac{n*(n-1)*(2n+1)}{6}$

$i^{3}$ 的前n项和:
$1^{3}$+ $2^{3}$+$3^{3}$+...+$n^{3}$= $\frac{n^{2}* (n+1)^{2}}{4}$

n * m矩形的子矩阵个数：
（1+2+...+n)* (1+2+...+m)=$\frac{n*(n+1)*m*(m+1)}{4}$

组合数公式：
$C_{n}^{m}$ =$\frac{n!}{m!*(n-m)!}$

三角函数

sin，cos，tan函数的参数都是弧度，返回的是其正弦余弦正切的值

asin，acos，atan函数的参数都是数，返回的是其角度的值。

角度转弧度：r= $\frac{\alpha \pi }{180}$

$\pi$ 是3.1415926535

特殊的数列

斐波那契数列：1 1 2 3 5

卡特兰数：1 2 5 14 42 132
通式： $\frac{C_{2n}^{n}}{n+1}$
应用：多边形刨分成三角形，要求刨分线不能交叉
2*n个数两两连线，要求不能有交叉，求方案数
特点：划分的线一旦分开，分成的几部分就没有关系了
四边形：2 五边形：5 六边形：14

小知识点

把一个正方形分成n个小正方形（大小可以不想等），除了2，3,5块不能分，其他都可以分

遍历n个点，每个点只遍历一次的走法有n!种

一个n * m的网格点上能构成的三角形的数量是：
$C_{(n+1)*(m+1)}^{3}-(n+1)* C_{m+1}^{3} - (m+1)* C_{n+1}^{3} - \sum_{j=1}^{n} \sum_{i=1}^{m} (m-i+1) *(n-j+1)*(\gcd(i, j)-1) *2$
方法就是先枚举出所有点能组成的三角形的数量，然后再减去在一条线上的三个点构成的三角形的数量。 ​ 这是专门的一道题(等我补补写题解) ：https://www.luogu.com.cn/problem/P3166

把一个二维矩阵s逆时针旋转90度之后得到的矩阵p是：

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        p[i][j]=s[n-j+1][i];

给一个数i，找到在l~r这一段他的最小倍数：
（先找到小于l的数和i的商，然后商再+1乘上i判断一下是不是小于等于r，如果是那最小倍数就是他，如果大于r，说明l-r里没有他的倍数）
$(\left \lfloor \frac{l-1}{i} \right \rfloor +1)*i$

一个长度为n的数组的子段个数是:
$\frac{n*(n-1)}{2}$

包含a[i]和a[i+1]的区间的个数为（n-i）*i（以i和i-1中间为界，坐标有i个数，可以有i个开始，右边有n-i个数，可以有n-1个结尾）

组合数：当将n个含有m个相同的块的块全排列，方式有 $\frac{n!}{m!}$ 种（去掉m个快块全排列的情况）

​

_int 128

是一个比较大的数据类型，最大为10^38，可以解决大整数问题

#include<bits/stdc++.h>
using namespace std;
const int N =  55;
//读入函数
inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
//输出函数
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
//使用的时候直接定义即可
__int128 f[N][N];
__int128 w[N];
const __int128 inf = 1e27;
//当输入的时候直接写要输入的数=read(）
//输出的时候print（要输出的数）
int main(){
    int n;
    cin >>n;
    for(int i =1 ; i <= n ; i++) w[i] = read();
    print(f[1][n]);
    return 0;
}

ksm

int ksm(int a,int b,int p){
	a%=p;
	int ans=1%p;
	while(b){
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}

gcd

int gcd(int a,int b) {
	return b? gcd(b,a%b):a;
}