模板整理（未完成）

DP

01背包（每种物品只有一个）

//n 物品数量，v 背包容量 
//size 单个物品体积，value 单个物品价值
void bag01()
{
    for(int i=0;i<n;i++)
    for(int j=v;j>=size[i];j--)
    {
        dp[j]=max(dp[j],dp[j-size[i]]+value[i]);
    }
    cout<<dp[v]<<endl;
}

完全背包（每种物品有无穷多）

void complete()
{
    for(int i=0;i<n;i++)
    for(int j=size[i];j<=v;j++)
    {
        dp[j]=max(dp[j],dp[j-size[i]]+value[i]);
    }
    cout<<dp[v]<<endl;
}

多重背包（每种物品数量有限）

//n 物品数量，v 背包容量 
//size 单个物品体积，value 单个物品价值，num 该物品的数量 
void multiply()
{
    for(int i=0;i<n;i++)  
    {  
        int d1=1,d2=num[i];  
        while(d1<d2)  
        {  
            for(int j=v;j>=d1*size[i];j--)  
            {  
                dp[j]=max(dp[j],dp[j-d1*size[i]]+value[i]*d1);  
            }  
            d2-=d1;  
            d1*=2;  
        }  
        for(int j=v;j>=d2*size[i];j--) dp[j]=max(dp[j],dp[j-d2*size[i]]+value[i]*d2);  
    } 
    cout<<dp[v]<<endl;
}

LIS（最长上升子序列）

//这个是计算连续的上升序列  如：1，2，3,4这种
void lis(int n)//n是数组元素的个数
{
    for(int i=1;i<=n;i++)
    {
        b[a[i]]=b[a[i]-1]+1;
        ans=std::max(ans,b[a[i]]);
    }
}
 
//这个计算的是递增的（不需要连续递增）如：1,3,5,7这种
int a[maxn];
int dp[maxn];
int n;
void longest()
{
    dp[0]=a[0];
    int pos;
    int L=1;
    for(int i=0;i<n;i++)
    {
        pos=lower_bound(dp,dp+L,a[i])-dp;
        dp[pos]=a[i];
        L=max(L,pos+1);
    }
    cout<<L<<endl;
}

LCS（最长公共子序列）

//状态转移方程：
// if( s[i]==t[j] ) 
//     dp[i+1][j+1] = dp[i][j] + 1; 
// else 
//     dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]); 
int dp[maxn][maxn];
char a[maxn],b[maxn];
int vis[maxn][maxn];//只求长度的时候可以去掉
// 如果要输出公共子序列，把int改成void，并把return去掉
int LCS()
{
    int len1,len2,i,j;
    len1=strlen(a);
    len2=strlen(b);
    memset(dp,0,sizeof(dp));
    for(i=1;i<=len1;i++)
        for(j=1;j<=len2;j++)
        {
            if(a[i-1]==b[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else if(dp[i-1][j]>=dp[i][j-1])
            {
                dp[i][j]=dp[i-1][j];
                vis[i][j]=1;
            }
            else 
            {
                dp[i][j]=dp[i][j-1];
                vis[i][j]=-1;
            }
        }
    return dp[len1][len2];
}
// 这个函数可以将LCS打印出来
void Print(int i, int j)//i，j分别代表a，b字符串的长度
{
    if(i==0||j==0)
        return;
    if(!vis[i][j])//如果a[i]和b[j]子母相同，输出
    {
        Print(i-1,j-1);
        printf("%c",a[i-1]);
    }
    else if(vis[i][j]==1)//如果dp[i-1][j]>dp[i][j-1]
        Print(i-1,j);
    else//如果dp[i][j-1]>=dp[i-1][j]
        Print(i,j-1);
}

数论

素数

素数筛法

1.线性筛选法——欧拉筛法

欧拉筛法通过红色标记部分保证每个合数只会被它的最小质因数筛去，时间复杂度降低到O(n)。
代码实现：

#include <stdio.h>
#include <string.h>
#define MAXN 100000
#define MAXL 1000000
int prime[MAXN];
_Bool check[MAXL];
 
int main(void)
{
    int n, count;
    while (~scanf("%d", &n))
    {
        memset(check, 0, sizeof(check));
        count = 0;
        for (int i = 2; i <= n; i++)
        {
            if (!check[i])
                prime[count++] = i;
            for (int j = 0; j < count; j++)
            {
                if (i*prime[j] > MAXL)
                    break; // 过大的时候跳出
                check[i*prime[j]] = 1;
                if ((i%prime[j]) == 0) // 如果i是一个合数，而且i % prime[j] == 0
                    break; 
            }
        }
        for (int i = 0; i < count; i++)
            printf("%d\n", prime[i]);
    }
    return 0;
}

2.小应用：求n的阶乘的因子数，题目n的范围（1000）；

数论的原理，n的阶乘的因子个数等于n的素因子个数的幂的乘积；
代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int k[1005]; 
const LL mod=1e9+7;
int main()
{
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int l=i;
        for(int j=2;j<=l;j++)
        {
            while(l%j==0)
            {
                k[j]++;
                l/=j;
            }   
        }
        if(l) k[l]++;
    }
    LL sum=1;
    for(int i=2;i<=n;i++)
    {
        if(k[i])
        {
            sum*=(k[i]+1);
            sum=sum%mod;
        }
    }                   
    printf("%lld\n",sum%mod);
    return 0;
}

3.查找出小于等于MAXN的素数（生成连续素数表）

/*
 *  素数筛选，查找出小于等于MAXN的素数
 *  prime[0]存素数的个数
 */

const int MAXN = 100000;
int prime[MAXN + 1];

void getPrime()
{
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= MAXN; i++)
    {
        if (!prime[i])
        {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++)
        {
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

同时得到欧拉函数表和素数表（线性筛）

 /*
 *  同时得到欧拉函数和素数表
 */
const int MAXN = 10000000;

bool check[MAXN + 10];
int phi[MAXN + 10];
int prime[MAXN + 10];
int tot;    //  素数个数

void phi_and_prime_table(int N)
{
    memset(check, false, sizeof(check));
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!check[i])
        {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; j++)
        {
            if (i * prime[j] > N)
            {
                break;
            }
            check[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else
            {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
    return ;
}

GCD

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

LCM

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;//如果先运算a*b，很可能超数据范围
}

EX_GCD

一般用来求解不定方程，求解线性同余方程，求解模的逆元等
公式： ax+by=c;

功能：用来解二元一次方程组；

注意事项：a,b均为正数;取最小正整数解
引理：存在 x , y 使得 gcd(a,b)=ax+by

int exgcd(int a,int b,int &x,int &y)
{
    // 无最大公约数
    if(a==0&&b==0)
        return -1;
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

例题：。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

#include<bits/stdc++.h>
#define LL long long 
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
using namespace std;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    LL r=exgcd(b,a%b,x,y);
    LL t=y;
    y=x-(a/b)*y;
    x=t;
    return r;
}
int main()
{
    LL a,b,x,y,n,m,l,k1,k2;//k2就是方程的一个x的解
    cin>>x>>y>>m>>n>>l;
    LL d=x-y;
    a=l;
    b=n-m;
    LL c=exgcd(a,b,k1,k2);//c是最大公约数
    if(d%c)//方程有解的条件
        printf("Impossible");
    else{
        LL s=k2*d/c;
        
        LL v=a/c;//对结果取余的最小的范围
        printf("%lld\n",(s%v+v)%v);
    }
    return 0;
}

快速幂

时间复杂度O(log(n))

int Pow(int a,int b,int c)
{
    int res=1;
    while(b>0)
    {
        if(b&1) res=res*a%c;
        a=a*a%c;
        b>>=1;
    }
    return res;
}

中国剩余定理（CRT）

求M%A=a,M%B=b,…中的M，其中A,B,C…互质

//chu是除数，yu是余数
//注意只适用于除数两两互质
#define ll long long
int ex_gcd(ll a, ll b, ll &x, ll &y) 
{
    ll d;
    if(b == 0) 
    {
        x = 1; 
        y = 0;
         return a;
    }
    d = ex_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll chinese_remainder(ll b[], ll w[], ll len) 
{ 
    ll i, d, x, y, m, n, ret;
    ret = 0; n = 1; 
    for(i=0; i < len ;i++) 
        n *= w[i];
    for(i=0; i < len ;i++) 
    { 
        m = n / w[i];
        d=ex_gcd(w[i], m, x, y);
        ret = (ret + y*m*b[i]) % n;
    }
    return (n + ret%n) % n;
}

中国剩余定理扩展

求M%A=a,M%B=b,…中的M，其中A,B,C…不互质

ll a[maxn],b[maxn];//a是除数，b是余数
ll ex_gcd(ll a,ll b,ll &x,ll &y) 
{
    ll d;
    if(b==0) 
    {
        x=1; 
        y=0;
         return a;
    }
    d=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
ll ex_crt(ll *a, ll *b, int n)
{
    ll M=a[1],R=b[1],x,y;
    for (int i=2;i<=n;i++)
    {
        ll d=ex_gcd(M,a[i],x,y);
        if((b[i]-R)%d) 
            return -1;
        x=(b[i]-R)/d*x%(a[i]/d);
        R+=x*M;
        M=M/d*a[i];
        R%=M;
    }
    return R>0?R:R+M;
}

求逆元

EX_GCD求逆元

//要求a和m互质
// ax = 1(mod m)
int mod_reverse(int a,int m)
{
    int x,y;
    int d=exgcd(a,m,x,y);
    if(d==1)
        return (x%m+m)%m;
    else
        return -1;
}

简洁写法

注意：这个只能求a<m的情况，而且必须保证a和m互质

//求 ax = 1( mod m) 的 x 值，就是逆元 (0<a<m)
int inv(int a,int m)
{
    if(a==1)
        return 1;
    return inv(m%a,m)*(m-m/a)%m;
}

利用欧拉函数求逆元

x和m互质（m可以不是素数）；时间复杂度O(sqrt(n))

//求欧拉函数值
int eurler_phi(int n)
{
    int res = n;
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            res = res / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n != 1) 
        res = res / n * (n - 1);
    return res;
}
//求逆元
int inv(int a,int m)
{
    return Pow(a,eurler_phi(m)-1,m);
}

线性时间求逆元

时间复杂度O(n)

// 逆元打表
int inv[maxn];
inv[1] = 1;
for(int i=2;i<maxn;i++)
    inv[i]=(mod-mod/ i)*inv[mod%i]%mod;

快速幂求逆元

原理是费马小定理，要求m为素数

// a和m互质，m为素数
int inv(int a,int m)
{
    return Pow(a,m-2,m);
}

二分乘法（快速乘）

用来解决乘法的结果远超int范围，但需要的结果有取余的乘法运算

ll qmul(ll a,ll b,ll m)
{
    ll ans=0;
    ll k=a;
    ll f=1;//f是用来存负号的
    if(k<0)
        {f=-1;k=-k;}
    if(b<0)
        {f*=-1;b=-b;}
    while(b){
        if(b&1)
            ans=(ans+k)%m;
        k=(k+k)%m;
        b>>=1;
    }
    return ans*f;
}

欧拉函数

对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(n)。
欧拉函数公式：φ(N)=N(1-1/P1)(1-1/P2)…(1-1/Pn)

直接求

int Eular(int n)
{
    int eu = n;
    for (int i = 2 ; i * i <= n ; i++)
    {
        if (n % i == 0)
        {
            eu -= eu / i;
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)      //n本身也是个质因子
        eu -= eu / n;
    return eu; 
}

打表求

void Eular()
{
    euler[1]=1;
    for(int i=2;i<maxn;i++)
        euler[i]=i;
    for(int i=2;i<maxn;i++)
        if(euler[i]==i)
            for(int j=i;j<maxn;j+=i)
                euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
}

唯一分解定理

任何大于１的自然数，都可以唯一分解成有限个质数的乘积

$$n=p^{a_{1}}_{1}p^{a_{2}}_{2}\ldots p^{a}_{k}=\prod ^{k}_{i=1}p^{a_{i}}_{i}$$

这里pi均为素数，其指数ai是正整数

找到数n的所有质因子

// pri记录质因子，k记录质因子个数
int pri[maxn],k;
void resolve(int n)
{
    k=0;
    int N=n;
    for(int i=2;i*i<=n;i++)
    {
        if(N%i==0)
        {
            pri[k++]=i;
            while(N%i==0)
                N/=i;
        }
    }
    if(N>1)
        num[k++]=N;
}

约数个数定理

计算一个数约数的个数

根据唯一分解定理：

$$n=\prod ^{k}_{i=1}p^{a_{i}}_{i}$$

则n的正约数个数为：

$$f\left( n\right) =\prod ^{k}_{i=1}\left( a_{i}+1\right)$$

如：将278000分解质因数

$$278000=2^{4}\times 3^{3}\times 5^{3}\times 7^{1}$$

可以计算出278000的正约数共有

$$\left( 4+1\right) \times \left( 3+1\right) \times \left( 1+1\right)=40个$$

int prime[maxn],nprime;    
int vis[maxn];    
void getprime(){  
    nprime = 0;  
    memset(vis,0,sizeof(vis));  
    for(int i = 2; i <= 450; i++){  
        int t = 450/i;  
        for(int j = 2; j <=t; j++)  
            vis[i*j] = 1;  
    }  
    for(int i = 2; i <= 450; i++){  
        if(!vis[i])  
            prime[nprime++] = i;  
    }  
}  
int factor_count(int n){    
    int ans = 1,sum;    
    int k = sqrt(n*1.0);    
    for(int i = 0; prime[i] < k; i++){    
        if(n % prime[i] == 0){    
            sum = 0;    
            while(n % prime[i] == 0){    
                sum++;    
                n /= prime[i];    
            }    
            ans *= (a+1);   //ans为n的约数的个数 
        }    
    }    
    if(n > 1)    
        ans *= 2;    
    return ans;    
}

约数和定理

正整数n的所有正约数的和为

f(n)=(p1^0 + p1^1 + p1^2 +…+ p1^a1)(p2^0 + p2^1 + p2^2 +…+ p2^a2)…(pk^0 + pk^1 + pk^2 +…+ pk^ak)

int prime[maxn],nprime;
int vis[maxn];
void getprime(){
    nprime = 0;
    memset(vis,0,sizeof(vis));
    for(int i = 2; i <= 450; i++){
        int t = 450/i;
        for(int j = 2; j <=t; j++)
            vis[i*j] = 1;
    }
    for(int i = 2; i <= 450; i++){
        if(!vis[i])
            prime[nprime++] = i;
    }
}
int pow_mod(int a,int n,int MOD){
    int ans = 1;
    while(n){
        if(n&1)
            ans = (ans*a)%MOD;
        n >>= 1;
        a = (a*a)%MOD;
    }
    return ans;
}
int factor_sum(int n){
    int ans = 1,sum;
    int k = sqrt(n*1.0);
    for(int i = 0; prime[i] < k; i++){
        if(n % prime[i] == 0){
            sum = 0;
            while(n%prime[i] == 0){
                sum++;
                n /= prime[i];
            }
            ans *= (pow_mod(prime[i],sum+1,MOD)-1)/(prime[i]-1);
        }
    }
    if(n > 1)
        ans *= ans(n*n-1)/(n-1);
    return ans;
}

元根

m是正整数，a是正数，若a mod m的阶等于φ(m)，则a为模m的一个元根（φ(m)表示m的欧拉函数）

给出一个素数p，找出p最小的元根

我的理解：找到最小的数x，使得

$$x^{\phi \left( n\right) }\% n=1$$

#include <bits/stdc++.h>
using namespace std;
int p[maxn];
int k;
ll Pow(ll a,ll b,ll c)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%c;
        b>>=1;
        a=a*a%c;
    }
    return res;
}
// 查找n的素因子
void getp(ll n)
{
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            p[k++]=i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        p[k++]=n;
}
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    k=0;
    // 素数的欧拉函数值为n-1
    // 对欧拉值进行分解
    getp(n-1);
    for(int i=2;i<n;i++)
    {
        int flag=0;
        for(int j=0;j<k;j++)
        {
            if(Pow(i,(n-1)/p[j],n)==1)
            {
                flag++;
                break;
            }
        }
        if(!flag)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

容斥原理（二进制状态枚举）

int n; 
for(int i=0;i<(1<<n);i++)
{ // 相当于枚举所有的情况 o(2^n*n)    
    for(int j = 0; j < n ;j++)
    {
        printf("%d ",(i>>j)&1);
    }
}
 
/**********应用*************/
// 二进制枚举计算[1,n]区间内有多少和数组a互质/不互质的数
ll ans = 0; 
for(int i = 1; i < (1 << n); i++)
{ // 相当于枚举所有的情况 o(2^n*n)  
    int  cnt = 0; ll tmp = 1;
    for(int j = 0; j < n ;j++)
    {    // a[j] 
        if(i >> j & 1) 
        {
            cnt ++;
            tmp = lcm(tmp, a[j]); 
        }
    }   
    if(cnt & 1) ans += n / tmp;
    else ans -= n / tmp; 
}

与1~n中与n互质的数的平方和

平方和公式：

$$\sum ^{n}_{i=1}i^{2}=\dfrac {n\left( n+1\right) \left( 2n+1\right) }{6}$$

把n进行质因子分解，进行容斥，结果=总和-不互质的平方和
不互质平方和为：

$$\sum ^{n}_{k=1}\left( k\ast m\right) ^{2}=m^{2}\sum ^{\dfrac {n}{m}}_{k=1}k^{2}=m^{2}\dfrac {\dfrac {n}{m}\left( \dfrac {n}{m}+1\right) \left( 2\dfrac {n}{m}+1\right) }{6}$$

把n进行质因子分解，进行容斥，结果=总和-不互质的平方和
不互质平方和为：

#include <cstdio> 
#include <algorithm>
using namespace std;
typedef long long LL;

const int maxn = 1e6 + 10;
LL arr[maxn];
int p;

LL get(LL x, LL y) {
    LL cnt = x / y;
    //这里return的是推出来的公式
    return ((y * y) * (cnt * (cnt + 1) * (2 * cnt + 1) / 6));
}

void getp(LL n) {  //分解质因子 
    p = 0;
    for(int i = 2; i * i <= n; i++) {  
        if(n % i == 0) {  
            arr[p++] = i;
            while(n % i == 0)  
                n /= i;  
        }  
    }  
    if(n > 1) arr[p++] = n;
}

int main() {
    LL n;
    while(scanf("%lld", &n) != EOF) {
        if(n == 0 || n == 1) {
            puts("0");
            continue;
        }
        getp(n);
        LL sum = n * (n + 1) * (2 * n + 1) / 6;
        LL ans = 0;
        for(int i = 1; i < (1 << p); i++) { //状压 
            LL res = 0, cnt = 1;
            for(int j = 0; j < p; j++) {
                if(i & (1 << j)) {
                    cnt *= arr[j];
                    res++;
                }
            }
            if(res & 1) ans += get(n, cnt); //容斥 
            else ans -= get(n, cnt);
        }
        printf("%lld\n", sum - ans);
    }
    return 0;
}

DLS模板

杜教筛

有些时候也有一些奇形怪状的函数比如

$$f\left( n\right) =\prod \left( p^{a_{i}}_{i}+1\right)$$

其中pi为质数，ai>0且

$$n=\prod p^{a_{i}}_{i}$$

接着出题人给了一个挺大的n（一般在10^10左右）。最后要求输出这个式子的值（可能会对一个大数进行取模）
杜教筛差不对就是拿来解决这类问题的它给出了一个比较通用的技巧，使得可以在O(n^(2/3))或者O(n^(3/4))的时间复杂度内求得结果
例如：

$$f\left( ij\right) =\sum ^{a}_{i=1}\sum ^{b}_{j=1}\dfrac {aj}{b}\left[ \left( a,b\right) =1\right]$$

f(i,j)是一个积性函数，求前缀和

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include <tr1/unordered_map>
typedef long long ll;
using namespace std;
using namespace std::tr1;
 
const int P=1000000007;
const int inv2=(P+1)/2;
const int inv3=(P+1)/3;
const int maxn=1000000;
 
int prime[2000000],num;
int miu[maxn+5];
ll sumd[maxn+5],t1[maxn+5],t2[maxn+5]; int d[maxn+5];
 
inline void Pre(){
  miu[1]=1; sumd[1]=1;
  for (int i=2;i<=maxn;i++){
    if (!d[i]) d[i]=prime[++num]=i,sumd[i]=1+i,t1[i]=1+i,t2[i]=i,miu[i]=-1;
    for (int j=1;j<=num && (ll)i*prime[j]<=maxn;j++){
      d[i*prime[j]]=prime[j]; int k=i*prime[j];
      if (i%prime[j]==0){
    miu[k]=0;
    t2[k]=t2[i]*prime[j],t1[k]=t1[i]+t2[k],sumd[k]=sumd[i]/t1[i]*t1[k];
    break;
      }
      miu[i*prime[j]]=miu[i]*miu[prime[j]];
      sumd[k]=sumd[i]*sumd[prime[j]],t1[k]=1+prime[j],t2[k]=prime[j];
    }
  }
  for (int i=1;i<=maxn;i++)
    miu[i]=((ll)i*((P+miu[i])%P)%P+miu[i-1])%P,(sumd[i]+=sumd[i-1])%=P;
}
 
unordered_map<ll,int> S;
 
inline void add(int &x,int y){
  x+=y; if (x>=P) x-=P;
}
 
inline int sum1(ll n){ return (n+1)%P*(n%P)%P*inv2%P;}
inline int sum1(ll l,ll r){ return (l+r)%P*((r-l+1)%P)%P*inv2%P; }
 
inline int Sum(ll n){
  if (n<=maxn) return miu[n];
  if (S.find(n)!=S.end()) return S[n];
  int tem=1; ll l,r;
  for (l=2;l*l<=n;l++) add(tem,P-l*Sum(n/l)%P);
  for (ll t=n/l;l<=n;l=r+1,t--)
    r=n/t,add(tem,P-(ll)sum1(l,r)*Sum(t)%P);
  return S[n]=tem;
}
/*
inline int F(ll n){
  int t1=0,t2=0; ll l,r;
  for (l=1;l*l<=n;l++) add(t1,l%P*(n/l)%P),add(t2,sum1(n/l)%P);
  for (ll t=n/l;l<=n;l=r+1,t--)
    r=n/t,add(t1,(ll)sum1(l,r)*(n/l)%P),add(t2,(r-l+1)%P*sum1(n/l)%P);
  return (ll)t1*t2%P;
}
*/
 
inline int F(ll n){
  if (n<=maxn) return (ll)sumd[n]*sumd[n]%P;
  int t1=0; ll l,r;
  for (l=1;l*l<=n;l++) add(t1,l%P*(n/l)%P);
  for (ll t=n/l;l<=n;l=r+1,t--)
    r=n/t,add(t1,(ll)sum1(l,r)*(n/l)%P);
  return (ll)t1*t1%P;
}
 
int main(){
  ll n,l,r; int Ans=0;
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  Pre();
  scanf("%lld",&n);
  for (l=1;l*l<=n;l++) add(Ans,(ll)(Sum(l)+P-Sum(l-1))%P*F(n/l)%P);
  for (ll t=n/l;l<=n;l=r+1,t--)
    r=n/t,add(Ans,(ll)(Sum(r)+P-Sum(l-1))%P*F(n/l)%P);
  printf("%d\n",Ans);
  return 0;
}

杜教BM模板

自动计算线性递推式（例如：f[x]=2f[x-1]+f[x-2]），推出前几项，压进vector就可以直接输出结果了（有些递推式也可以用矩阵快速幂来求）

例如：计算线性递推式：

$$a\left[ i\right]=2\times a\left[ i-1\right]-a\left[ i-2\right]+3\times a\left[ i-3\right]+2\times a\left[ i-4\right]$$

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1e9+7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head
int _,n;
namespace linear_seq {
    const int N=10010;
    ll res[N],base[N],_c[N],_md[N];
 
    vector<int> Md;
    void mul(ll *a,ll *b,int k) {
        rep(i,0,k+k) _c[i]=0;
        rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
        for (int i=k+k-1;i>=k;i--) if (_c[i])
            rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
        rep(i,0,k) a[i]=_c[i];
    }
    int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
//        printf("%d\n",SZ(b));
        ll ans=0,pnt=0;
        int k=SZ(a);
        assert(SZ(a)==SZ(b));
        rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
        Md.clear();
        rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
        rep(i,0,k) res[i]=base[i]=0;
        res[0]=1;
        while ((1ll<<pnt)<=n) pnt++;
        for (int p=pnt;p>=0;p--) {
            mul(res,res,k);
            if ((n>>p)&1) {
                for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
                rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
            }
        }
        rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
        if (ans<0) ans+=mod;
        return ans;
    }
    VI BM(VI s) {
        VI C(1,1),B(1,1);
        int L=0,m=1,b=1;
        rep(n,0,SZ(s)) {
            ll d=0;
            rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
            if (d==0) ++m;
            else if (2*L<=n) {
                VI T=C;
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L; B=T; b=d; m=1;
            } else {
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        return C;
    }
    int gao(VI a,ll n) {
        VI c=BM(a);
        c.erase(c.begin());
        rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
        return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
    }
};
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        vector<int>v;
        /**
         * 下面放入推出的前几项（项数越多结果越准确）
         */
        v.push_back(3);
        v.push_back(9);
        v.push_back(20);
        v.push_back(46);
        v.push_back(106);
        v.push_back(244);
        v.push_back(560);
        v.push_back(1286);
        v.push_back(2956);
        v.push_back(6794);
        v.push_back(15610);
        v.push_back(35866);
        //VI{1,2,4,7,13,24}
        ll n;
        scanf("%lld",&n);
        printf("%lld\n",linear_seq::gao(v,n-1));
    }
}

阶乘最后非零位

/*
 *  阶乘最后非零位 复杂度O(nlongn)
 *  返回改为，n以字符串方式传入
 */
#define MAXN 10000

const int mod[20] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2};

int lastDigit(char *buf)
{
    int len = (int)strlen(buf);
    int a[MAXN], i, c, ret = 1;
    if (len == 1)
    {
        return mod[buf[0] - '0'];
    }
    for (i = 0; i < len; i++)
    {
        a[i] = buf[len - 1 - i] - '0';
    }
    for (; len; len -= !a[len - 1])
    {
        ret = ret * mod[a[1] % 2 * 10 + a[0]] % 5;
        for (c = 0, i = len - 1; i >= 0; i--)
        {
            c = c * 10 + a[i];
            a[i] = c / 5;
            c %= 5;
        }
    }
    return ret + ret % 2 * 5;
}

斯特林公式

求n阶乘的近似值

公式：

$$\lim _{n\rightarrow \infty }\left( \dfrac {n}{\pi }\right) ^{n}\sqrt {\dfrac {2\pi n}{n!}}=1$$

可以得出：

$$n!\approx \sqrt {2\pi n}\left( \dfrac {n}{e}\right) ^{n}$$

利用斯特林公式计算n阶乘的长度

公式：(需要对len取整)

$$len=\dfrac {\lg 2\pi n}{2}+n\lg \dfrac {n}{e}+1$$

#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)  
const double E=exp(1);
int main()
{
    int t;
    int n;
    cin>>n;
    long long ans=1+0.5*log10(2*pi*n)+n*log10(n/E);
    cout<<ans<<endl;
    return 0;
}

卡特兰数

求n对括号合法的匹配方式

$$C^{n}_{2n}-C^{n+1}_{2n}$$

卡特兰数公式

令h(0)=1,h(1)=1;catalan数满足递推式：h(n)= h(0)h(n-1)+h(1)h(n-2) + … +h(n-1)h(0) (n>=2)
另类递推式：h(n)=h(n-1)(4n-2)/(n+1);
递推关系的解为：

$$h\left( n\right) =\dfrac {C^{n}_{2n}}{n+1} \left(n= 1,2,3\ldots \right)$$

递推关系的另类解为：

$$h\left( n\right) =C^{n}_{2n}-C^{n-1}_{2n} \left(n= 1,2,3\ldots \right)$$

可以用卡特兰数解决的常见问题

（1）一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
（2）在n x n的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？
（3）将一个凸n+2边形区域分成三角形区域的方法数？
（4）圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？
（5）有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？
代码实现

#include <stdio.h>
#include<string.h>
int a[105][1000];//大数运算 
int b[105]; //储存对应卡特兰数有多少位 
void catalan() //求卡特兰数
{
    int i, j, len, carry, temp;
    a[1][0] = b[1] = 1;
    len = 1;
    for(i = 2; i <= 100; i++)
    {
        for(j = 0; j < len; j++) //乘法
        a[i][j] = a[i-1][j]*(4*(i-1)+2);
        carry = 0;
        for(j = 0; j < len; j++) //处理相乘结果
        {
            temp = a[i][j] + carry;
            a[i][j] = temp % 10;
            carry = temp / 10;
        }
        while(carry) //进位处理
        {
            a[i][len++] = carry % 10;
            carry /= 10;
        }
        carry = 0;
        for(j = len-1; j >= 0; j--) //除法
        {
            temp = carry*10 + a[i][j];
            a[i][j] = temp/(i+1);
            carry = temp%(i+1);
        }
        while(!a[i][len-1]) //高位零处理
        len --;
        b[i] = len;
    }
}
 
int main() {
    catalan();
    for(int i=1;i<=100;i++)
    {
        for(int j=b[i]-1;j>=0;j--)
        {
            printf("%d",a[i][j]);
        }
        printf("\n");
    }
}

STL

set

基本操作：

s.begin()       //  返回指向第一个元素的迭代器
s.clear()       //  清除所有元素
s.count()       //  返回某个值元素的个数
s.empty()       //  如果集合为空，返回true(真）
s.end()         //  返回指向最后一个元素之后的迭代器，不是最后一个元素
s.equal_range() //  返回集合中与给定值相等的上下限的两个迭代器
s.erase()       //  删除集合中的元素
s.find()        //  返回一个指向被查找到元素的迭代器
s.get_allocator()   //  返回集合的分配器
s.insert()      //  在集合中插入元素
s.lower_bound() //  返回指向大于（或等于）某值的第一个元素的迭代器
s.key_comp()    //  返回一个用于元素间值比较的函数
s.max_size()    //  返回集合能容纳的元素的最大限值
s.rbegin()      //  返回指向集合中最后一个元素的反向迭代器
s.rend()        //  返回指向集合中第一个元素的反向迭代器
s.size()        //  集合中元素的数目
s.swap()        //  交换两个集合变量
s.upper_bound() //  返回大于某个值元素的迭代器
s.value_comp()  //  返回一个用于比较元素间的值的函数

最长路

有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次，最少需要走多少路

输入：
第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路

输出：
一个结果表示答案

思路：所有路径长度*2减去最长路的长度

#include<bits/stdc++.h>
#define ll long long
#define msy(a) memset(a,-1,sizeof(a))
const double E=exp(1);
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
vector<pair<int, ll> >  G[maxn];
ll dis[maxn], mmax;
//计算最长路，maxx是最长路
void dfs(int x)
{
    int size = G[x].size();
    for(int i=0; i<size; ++i)
    {
        int u = G[x][i].first;
        if(dis[u] == -1)
        {
            dis[u] = G[x][i].second + dis[x];
            mmax = max(mmax, dis[u]);
            dfs(u);
        }
    }
}
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    msy(dis);
    int n, x;
    cin >> n >> x;
    int u, v;
    ll w, ans = 0;
    for(int i=1; i<n; ++i)
    {
        cin >> u >> v >> w;
        G[u].push_back(make_pair(v, w));
        G[v].push_back(make_pair(u, w));
        ans+=w;
    }
    ans*=2;
    dis[x] = 0;
    dfs(x);
    ans -= mmax;
    cout << ans << endl;
    return 0;
}

分段打表

题意：计算1+1/2+1/3+……+1/n ;

思路：分段打表，将每1000的和存一下，需要计算时找出对应的1000的权值，再计算后面的部分相加即可

#include <cstdio>
#include <cmath>
double a[100005];
 
void init(){
    int tm = 1;
    a[0] = 0;
    for (int i = 1; i <= 100002; ++i){
        a[i] = a[i-1];//a[i]计算的从(i-1)*1000+1到i*1000的和 
        for (int j = tm; j <= tm+999; ++j){
            a[i] += 1.0/j;
        }
        tm = tm+1000;
    }
}
int main(){
    int t;
    scanf("%d",&t);
    init();
    int Case = 1;
    while (t--){
        int n;
        scanf("%d",&n);
        int r = n/1000*1000;//找出他的对应1000的位置 
        for (int i = r+1; i <= n; ++i){//计算一下剩余的值的和 
            tmp += 1.0/i;
        }
        double tt;
         tt = a[n/1000];
        //printf("%lf %lf\n",tt,tmp);
        double ans = tt+tmp;
        printf("Case %d: %.9lf\n",Case++,ans);
    }
    return 0;
}

SG函数

结论：游戏和的SG函数等于各个游戏SG函数的Nim和
应用条件：当进行游戏有多种选取方式，可以打sg表或者用dfs得到

例题：
有三堆石子，每堆石子的数量为n,m,k.每次每人可以拿去的石子数量为斐波那契的项的数量，
1、 这是一个二人游戏;
2、 一共有3堆石子，数量分别是m, n, p个；
3、 两人轮流走;
4、 每走一步可以选择任意一堆石子，然后取走f个；
5、 f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量）；
6、 最先取光所有石子的人为胜者；

//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
#include <stdio.h>
#include <string.h>
#define MAXN 1000 + 10
#define N 20
int f[N],SG[MAXN],S[MAXN];
void getSG(int n){
    int i,j;
    memset(SG,0,sizeof(SG));
    for(i = 1; i <= n; i++){
        memset(S,0,sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;
        for(j = 0;;j++) if(!S[j]){
            SG[i] = j;
            break;
        }
    }
}
int main(){
    int n,m,k;
    f[0] = f[1] = 1;
    for(int i = 2; i <= 16; i++)
        f[i] = f[i-1] + f[i-2];
    getSG(1000);
    while(scanf("%d%d%d",&m,&n,&k),m||n||k){
        if(SG[n]^SG[m]^SG[k]) printf("Fibo\n");
        else printf("Nacci\n");
    }
    return 0;
}