SaoZhu Team Code Library 2017.11

ACM

for newest edition, click here

East China Normal University

Chen WeiWen - Software Engineering cww970329@qq.com

Cao ZhiJie - Computer Science

Zhu XuLiang - Mathematics

常用STL

map的Upperbound

map<int,int>::iterator se = mp.upper_bound(mid);
返回迭代器

优先队列

priority_queue<int>Q;//采用默认优先级构造队列
priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
Q.push(x);
int x = Q.top(); Q.pop();

multiset

begin()        返回指向第一个元素的迭代器
clear()        清除所有元素
count()        返回某个值元素的个数
empty()        如果集合为空，返回 true
end()          返回指向最后一个元素的迭代器
erase()        删除集合中的元素 ( 参数是一个元素值，或者迭代器)
find()         返回一个指向被查找到元素的迭代器
insert()       在集合中插入元素
size()         集合中元素的数目
lower_bound()  返回指向大于（或等于）某值的第一个元素的迭代器
upper_bound()  返回大于某个值元素的迭代器
equal_range()  返回集合中与给定值相等的上下限的两个迭代器
multiset <point> po;
multiset <point>::iterator L, R, it;

离散化lower_lound

lower_bound 第一个出现的值大于等于val的位置

upper_bound 最后一个大于等于val的位置，也是有一个新元素val进来时的插入位置

sort(a + 1, a + A+1);
A = unique(a + 1, a + A+1) - (a + 1);
for (int i = 1; i <= n; i++){ // segtree
    int L = lower_bound(a+1, a+A+1, l[i]) - a;
    int R = lower_bound(a+1, a+A+1, r[i]) - a;
    T.update(L, R, i, 1, T.M+1,1);
}
------------use in ChairTree-------------------
for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    Rank[i] = arr[i];
}
sort(Rank + 1, Rank + n+1);//Rank存储原值
int m = unique(Rank + 1, Rank + n +1) - (Rank + 1);//这个m很重要，WA一天系列
for (int i = 1; i <= n; i++) {//离散化后的数组，仅仅用来更新
    arr[i] = lower_bound(Rank + 1, Rank + m+1, arr[i]) - Rank;
}
==================CZJ排序去重===================
sort(vecs.begin(), vecs.end());
vecs.resize(unique(vecs.begin(), vecs.end()) - vecs.begin());

vector 的插入删除

// erase the 6th element
myvector.erase (myvector.begin()+5);
// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);
// ------------inserting into a vector-----------
#include <iostream>
#include <vector>
int main (){
  std::vector<int> myvector (3,100);
  std::vector<int>::iterator it;
  it = myvector.begin();
  it = myvector.insert ( it , 200 );
  myvector.insert (it,2,300);
  // "it" no longer valid, get a new one:
  it = myvector.begin();
  std::vector<int> anothervector (2,400);
  myvector.insert (it+2,anothervector.begin(),anothervector.end());
  int myarray [] = { 501,502,503 };
  myvector.insert (myvector.begin(), myarray, myarray+3);
  std::cout << "myvector contains:";
  for (it=myvector.begin(); it<myvector.end(); it++) std::cout << ' ' << *it;
  std::cout << '\n';
  return 0;
}

bitset

构造函数
bitset<n> b;
b有n位，每位都为0.参数n可以为一个表达式.
如bitset<5> b0;则"b0"为"00000";
bitset<n> b(unsigned long u);
b有n位,并用u赋值;如果u超过n位,则顶端被截除
如:bitset<5>b0(5);则"b0"为"00101";
bitset<n> b(string s);
b是string对象s中含有的位串的副本
string bitval ( "10011" );
bitset<5> b0 ( bitval4 );
则"b0"为"10011";
bitset<n> b(s, pos);
b是s中从位置pos开始位的副本,前面的多余位自动填充0;
string bitval ("01011010");
bitset<10> b0 ( bitval5, 3 );
则"b0" 为 "0000011010";
bitset<n> b(s, pos, num);
b是s中从位置pos开始的num个位的副本,如果num<n,则前面的空位自动填充0;
string bitval ("11110011011");
bitset<6> b0 ( bitval5, 3, 6 );
则"b0" 为 "100110";
bool any()      是否存在置为1的二进制位？和none()相反
bool none()     是否不存在置为1的二进制位,即全部为0？和any()相反.
size_t count()  二进制位为1的个数.
size_t size()   二进制位的个数
flip()          把所有二进制位逐位取反
flip(size_t pos)把在pos处的二进制位取反
bool operator[]( size_type _Pos )获取在pos处的二进制位
set()           把所有二进制位都置为1
set(pos)        把在pos处的二进制位置为1
reset()         把所有二进制位都置为0
reset(pos)      把在pos处的二进制位置为0
test(size_t pos)在pos处的二进制位是否为1？
unsigned long to_ulong( )用同样的二进制位返回一个unsigned long值
string to_string ()返回对应的字符串.

STL补充

Stringstream的使用：

　　string str;  
　　stringstream ss;  
　　while(getline(cin,str)){ //getline函数的返回值是其中的流cin。一旦cin读取错误就是false。  
　　　　ss<<str;    //将string送入流中。  
　　　　int a,sum=0;  
　　　　while(ss >> a) sum+=a;     //当流里没有东西的时候，退出循环。  
　　　　cout<<sum<<endl;  
　　}

STL补充
lower_bound: 返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。

upper_bound: 返回一个ForwardIterator，指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值。重载函数使用自定义比较操作。

inplace_merge: 合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序。

merge: 合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。

nth_element: 将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作。

sort: 以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。

stable_sort: 与sort类似，不过保留相等元素之间的顺序关系。

unique: 清除序列中重复元素，和remove类似，它也不能真正删除元素。重载版本使用自定义比较操作。

next_permutation: 取出当前范围内的排列，并重新排序为下一个字典序排列。重载版本使用自定义的比较操作。

prev_permutation: 取出指定范围内的序列并将它重新排序为上一个字典序排列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。

scanf 用法及陷阱

格式字符 说明
%c 读入一个字符
%d 读入十进制整数
%i 读入十进制，八进制，十六进制整数
%o 读入八进制整数
%x 读入十六进制整数
%X 同上
%c 读入一个字符
%s 读入一个字符串
%f 读入一个浮点数
%p 读入一个指针
%u 读入一个无符号十进制整数

scanf一个double数据，是%lf，printf一个float或者double都是%f

大写L,加f输出long double。最后的f小写和大写没影响，但是第一个 l 必须大写成L。

unsigned long long %llu

printf 对齐方式

1.默认左对齐

2.在打印数字宽度前面加一个-,左对齐%-10d

3.在数字宽度前面不加-,右对齐%10d

rope

丧心病狂的可持久化平衡树

1）头文件 #include
2)调用命名空间 using namespace __gnu_cxx;

rope适用于大量、冗长的串操作，而不适合单个字符操作

rope本质是封装好的类似块状链表的东东，有人说是logn的，但也有说是n^0.5的。rope不支持一切数值操作，如第k大

先介绍几个可能使用到的函数

1）append()

string &append(const string &s,int pos,int n); // 把字符串s中从pos开始的n个字符连接到当前字符串的结尾

或

a.append(b);

2）substr()

s.substr(0,5); // 获得字符串s中从第零位开始长度为5的字符串（默认时长度为刚好开始位置到结尾）

定义/声明

rope<char> str;
r="abcdefg"

具体内容
总的来说，

1）运算符：rope支持operator += -= + - < ==
2）输入输出：可以用<<运算符由输入输出流读入或输出。
3）长度/大小：调用length()，size()都可以哦
4）插入/添加等：
push_back(x);  // 在末尾添加x
insert(pos,x);  // 在pos插入x，自然支持整个char数组的一次插入
erase(pos,x);  // 从pos开始删除x个
copy(pos,len,x);  // 从pos开始到pos+len为止用x代替
replace(pos,x);  // 从pos开始换成x
substr(pos,x);  // 提取pos开始x个
at(x)/[x];  // 访问第x个元素

访问

1）迭代器：不说，在竞赛是超时大忌

2）单点访问，直接用数组形式调用下标即可

应用

一、bzoj1269 文本编辑器

实现操作：
1.（已知）move k：移动光标到目标，初始为0
2.（已知）prev：光标前移一个字符
3.（已知）next：光标后移一个字符
4.insert n s：在光标后插入长度为n的字符串s光标位置不变
5.delete n 删除光标后的n个字符，光标位置不变
6.rotate n 反转光标后的n个字符，光标位置不变
7.get 输出光标后一个字符，光标位置不变

solution

为实现反转操作且保证不超时，我们不调用rope自带的可怕函数，暴力构建两个rope，插入时一个正序插入一个倒序插入，区间即为子串赋值

#include<cstdio>
#include<ext/rope>
#include<iostream>
using namespace std;
using namespace __gnu_cxx;
inline int Rin(){
  int x=0,c=getchar(),f=1;
  for(;c<48||c>57;c=getchar())
    if(!(c^45))f=-1;
  for(;c>47&&c<58;c=getchar())
    x=(x<<1)+(x<<3)+c-48;
  return x*f;
}
int n,pos,x,l;
rope<char>a,b,tmp;
char sign[10],ch[1<<22],rch[1<<22];
int main(){
  n=Rin();
  while(n--){
    scanf("%s",sign);
    switch(sign[0]){
    case'M':pos=Rin();break;
    case'P':pos--;break;
    case'N':pos++;break;
    case'G':putchar(a[pos]);putchar('\n');break;
    case'I':
      x=Rin();
      l=a.length();
      for(int i=0;i<x;i++){
    do{ch[i]=getchar();}
    while(ch[i]=='\n');
    rch[x-i-1]=ch[i];
      }
      ch[x]=rch[x]='\0';
      a.insert(pos,ch);
      b.insert(l-pos,rch);
      break;
    case'D':
      x=Rin();
      l=a.length();
      a.erase(pos,x);
      b.erase(l-pos-x,x);
      break;
    case'R':
      x=Rin();
      l=a.length();
      tmp=a.substr(pos,x);
      a=a.substr(0,pos)+b.substr(l-pos-x,x)+a.substr(pos+x,l-pos-x);
      b=b.substr(0,l-pos-x)+tmp+b.substr(l-pos,pos);
      break;
    }
  }
  return 0;
}

线性代数

矩阵快速幂

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
LL n,m;
struct matrix{
    static const int MATRIX_N = 11;
    LL a[MATRIX_N][MATRIX_N];
    int row, col;
    matrix():row(MATRIX_N),col(MATRIX_N){memset(a,0,sizeof(a));}
    matrix(int x, int y):row(x),col(y){memset(a,0,sizeof(a));}
    LL* operator [] (int x){return a[x];}
    matrix operator * (matrix x){
        matrix tmp(row, x.col);
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++) if(a[i][j])//稀疏矩阵优化
                for(int k = 0; k < x.col; k++) if (x[j][k]){
                    tmp[i][k] += a[i][j] * x[j][k];
                    //mult(a[i][j], x[j][k], MOD);
                    tmp[i][k] %= MOD;
                }
        return tmp;
    }
    void operator *= (matrix x){*this = *this * x;}
    matrix operator ^ (LL x){
        matrix ret(row, col);
        for (int i = 0; i < col; i++) ret[i][i] = 1;
        matrix tmp = *this;
        for (; x; x >>= 1, tmp *= tmp){if (x&1) ret *= tmp;}
        return ret;
    }
    void print(){
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++) printf("%lld ",a[i][j]);
            puts("");
        }
    }
};
int main() {
    LL n;
    matrix B(3, 1);
    while(scanf("%lld%lld%lld%lld", &B[0][0], &B[1][0], &B[2][0], &n) == 4) {
        matrix A(3, 3);
        A[0][0] = 0; A[0][1] = 1; A[0][2] = 0;
        A[1][0] = 0; A[1][1] = 0; A[1][2] = 1;
        A[2][0] = 0; A[2][1] = 1; A[2][2] = 1;
        A = A ^ n;
        matrix C(3, 1);
        C = A * B;
        printf("%lld\n", (C[0][0] + C[1][0] + C[2][0]) % MOD);
    }
    return 0;
}

就是快速幂(czj)

//快速乘法
LL fast_multi(LL m, LL n, LL mod){
    LL ans = 0;//注意初始化是0，不是1 
    n = (n % mod + mod) % mod;
    for (;n; n >>= 1){
        if (n & 1) ans = (ans + m) % mod;
        m = (m + m) % mod;//和快速幂一样，只不过这里是加 
    }
    return ans % mod;
}
LL fast_pow(LL a, LL n, LL mod){//快速幂 
    LL ans = 1;
    for (;n;n >>= 1){
        if (n & 1) ans = fast_multi(ans, a, mod) % mod;//不能直接乘 
        a = fast_multi(a, a, mod) % mod;
    }
    return ans;
}

线性递推函数杜教模板(快速幂下岗了)

#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
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=1000000007;
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 _;
ll n;
namespace linear_seq {
    const int N=10010;
    ll res[N],base[N],_c[N],_md[N];
    vector<ll> Md;
    void mul(ll *a,ll *b,ll 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) { 
        ll ans=0,pnt=0;
        ll 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() {
    for (scanf("%d",&_);_;_--) {
        scanf("%lld",&n);
        printf("%d\n",linear_seq::gao(VI{31, 197, 1255, 7997, 50959, 324725, 2069239, 13185773, 84023455},n-2));
    }
}

高斯消元（naive）

判断是否有解

求解见红书

int Gauss(matrix a, int m, int n){
    int x_cnt = 0;
    int col, k;         //col为列号,k为行号
    for (k=0,col=0;k<m&&col<n; ++k, ++col){
        int r = k;      //r为第col列的一个1
        for (int i=k;i<m;++i) if (a[i][col])r=i;
        if (!a[r][col]){ k--; continue;}
        if (r!=k)for (int i=col;i<=n;++i)
            swap( a[r][i], a[k][i]);
        for (int i=k+1;i<m; ++i)if (a[i][col])//消元
            for (int j=col;j<=n;++j) a[i][j] ^= a[k][j];
    }
    for (int i=k;i<m;++i) if (a[i][n])return -1;
    if (k<=n)return n-k;     //返回自由元个数
}

bitset优化XOR方程组

//HDU 5833 XOR GUASS bitset, 白书P160
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
const int mod = 1e9+7;
int n, vis[maxn], prime[maxn], cnt;
void pre_deal(){
    for(int i = 2; i < maxn; i++){
        if (vis[i]) continue;
        prime[cnt++] = i;
        for(int j = i; j < maxn; j += i) vis[j] = 1;
    }
}
bitset <330> A[305]; //A[i][j]就表示第j个数的这个i素数是奇数还是偶数
int main(){
    pre_deal();
    int T, ks = 0; scanf("%d", &T);
    while(T--){
        printf("Case #%d:\n", ++ks);
        for(int i = 0; i < 305; i++) A[i].reset();
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            long long x;
            scanf("%lld", &x);
            for(int j = 0; j < cnt; j++){
                if(x%prime[j] == 0){
                    int flag = 0;
                    while(x%prime[j] == 0){
                        x /= prime[j];
                        flag ^= 1;
                    }
                    A[j][i] = flag;
                }
            }
        }
        int i = 0, j = 0; //xor消元之后j就是秩
        for(i = 0; i < n; i++){
            int id = -1;
            for(int k = j; k < cnt; k++){
                if(A[k][i]){id = k; break;}
            }
            if(id == -1) continue;
            swap(A[j], A[id]);
            for(int k = j + 1; k < cnt; k++)
                if(A[k][i]) A[k] ^= A[j];
            j++;
        }
        int ans = 1;
        for(int i = 0; i < n - j; i++) ans = ans * 2 % mod;
        ans--;
        printf("%d\n", ans);
    }
    return 0;
}

16行FFT

模板题：多项式乘法

#include<bits/stdc++.h>
using namespace std;
const double PI = acos (-1.);
const int N = 1 << 22;
std::complex <double> AA[N], BB[N];
void fft (std::complex <double> a[], int n, int f) {
    for (int i = 0, j = 0; i < n; ++i) {
        if (i > j) std::swap (a[i], a[j]);
        for (int t = n >> 1; (j ^= t) < t; t >>= 1);
    }
    static std::complex <double> w[N];
    for (int i = 0; i <= n; ++i)
        w[i] = std::complex <double> (cos (2 * PI * i / n), sin (2 * PI * i / n));
    for (int i = 2; i <= n; i <<= 1)
        for (int j = 0; j < n; j += i)
            for (int k = 0; k < (i >> 1); ++k) {
                std::complex <double> A = a[j + k];
                std::complex <double> B = w[f ? n - n / i * k : n / i * k] * a[j + k + (i >> 1)];
                a[j + k] = A + B; a[j + k + (i >> 1)] = A - B;
            }
    if (f) for (int i = 0; i < n; ++i) a[i] = std::complex <double> (a[i].real () / n, a[i].imag ());
}
int main(){
    int A, B;
    std::cin >> A >> B;
    for (int i = 0; i <= A; ++i) {
        int u; std::cin >> u;
        AA[i] = std::complex <double> (u, 0);
    }
    for (int i = 0; i <= B; ++i) {
        int u; std::cin >> u;
        BB[i] = std::complex <double> (u, 0);
    }
    int n = 1;
    while (n <= A + B + 1) n *= 2;
    fft (AA, n, 0);
    fft (BB, n, 0);
    for (int i = 0; i < n; ++i) AA[i] = AA[i] * BB[i];
    fft (AA, n, 1);
    for (int i = 0; i <= A + B; ++i) std::cout << (int) round (AA[i].real ()) << " \n"[i == A + B];
    return 0;
}

NTT（对任意数取模）

// 多项式乘法 系数对MOD=1000000007取模， 常数巨大，慎用  
// 只要选的K个素数乘积大于MOD*MOD*N,理论上MOD可以任取。  
#define MOD 1000000007  
#define K 3  
const int m[K] = {1004535809, 998244353, 104857601};  
#define G 3  
int qpow(int x, int k, int P) {  
    int ret = 1;  
    while(k) {  
        if(k & 1) ret = 1LL * ret * x % P;  
        k >>= 1;  
        x = 1LL * x * x % P;  
    }  
    return ret;  
}  
struct _NTT {  
    int wn[25], P;  
    void init(int _P) {  
        P = _P;  
        for(int i = 1; i <= 21; ++i) {        
            int t = 1 << i;        
            wn[i] = qpow(G, (P - 1) / t, P);        
        }  
    } 
    void change(int *y, int len) {  
        for(int i = 1, j = len / 2; i < len - 1; ++i) {        
            if(i < j) swap(y[i], y[j]);        
            int k = len / 2;        
            while(j >= k) {        
                j -= k;        
                k /= 2;        
            }        
            j += k;        
        }   
    }  
    void NTT(int *y, int len, int on) {  
        change(y, len);        
        int id = 0;        
        for(int h = 2; h <= len; h <<= 1) {        
            ++id;        
            for(int j = 0; j < len; j += h) {        
                int w = 1;        
                for(int k = j; k < j + h / 2; ++k) {        
                    int u = y[k];        
                    int t = 1LL * y[k+h/2] * w % P;       
                    y[k] = u + t;        
                    if(y[k] >= P) y[k] -= P;        
                    y[k+h/2] = u - t + P;        
                    if(y[k+h/2] >= P) y[k+h/2] -= P;    
                    w = 1LL * w * wn[id] % P;  
                }        
            }        
        }        
        if(on == -1) {        
            for(int i = 1; i < len / 2; ++i) swap(y[i], y[len-i]);        
            int inv = qpow(len, P - 2, P);        
            for(int i = 0; i < len; ++i)     
                y[i] = 1LL * y[i] * inv % P;  
        }        
    }  
    void mul(int A[], int B[], int len) {  
        NTT(A, len, 1);  
        NTT(B, len, 1);  
        for(int i = 0; i < len; ++i) A[i] = 1LL * A[i] * B[i] % P;  
        NTT(A, len, -1);  
    }  
}ntt[K];  
int tmp[N][K], t1[N], t2[N];  
int r[K][K];  
int CRT(int a[]) {  
    int x[K];  
    for(int i = 0; i < K; ++i) {  
        x[i] = a[i];  
        for(int j = 0; j < i; ++j) {  
            int t = (x[i] - x[j]) % m[i];  
            if(t < 0) t += m[i];  
            x[i] = 1LL * t * r[j][i] % m[i];  
        }  
    }  
    int mul = 1, ret = x[0] % MOD;  
    for(int i = 1; i < K; ++i) {  
        mul = 1LL * mul * m[i-1] % MOD;  
        ret += 1LL * x[i] * mul % MOD;  
        if(ret >= MOD) ret -= MOD;  
    }  
    return ret;  
}  
void mul(int A[], int B[], int len) {  
    for(int id = 0; id < K; ++id) {
        for(int i = 0; i < len; ++i) {  
            t1[i] = A[i];
            t2[i] = B[i];
        }  
        ntt[id].mul(t1, t2, len);  
        for(int i = 0; i < len; ++i) tmp[i][id] = t1[i];  
    }  
    for(int i = 0; i < len; ++i){
        A[i] = CRT(tmp[i]);
    }  
}  
void init() {  
    for(int i = 0; i < K; ++i) {
        for(int j = 0; j < i; ++j) {
            r[j][i] = qpow(m[j], m[i] - 2, m[i]);  
        }
    }
    for(int i = 0; i < K; ++i) ntt[i].init(m[i]);
}

单纯形法

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const double EPS=1e-9;
int n,m;
/*
求解的为标准形式
max z=CX
满足    AX<=B
        X>=0
约定 B>=0
对于形式为
min z=CX
满足    AX >= B
        X>=0
约定B>=0
可以转换为对偶形式
max w=(B^T)Y
满足    (A^T)Y<=(C^T)
        Y>=0
hint:^T表示矩阵翻转
*/
namespace Linear_Programming{
double A[10100][1010],b[10100],c[1010],v;
void Pivot(int l,int e){
    int i,j;
    b[l] /= A[l][e];
    for (i = 1; i <= n; i++) if (i != e) 
        A[l][i] /= A[l][e];
    A[l][e] = 1 / A[l][e];
    for(i=1; i<=m; i++)
        if(i != l && fabs(A[i][e]) > EPS){
            b[i] -= A[i][e] * b[l];
            for(j = 1; j <= n; j++) if (j != e)
                A[i][j] -= A[i][e] * A[l][j];
            A[i][e] = -A[i][e] * A[l][e];
        }
    v += c[e]*b[l];
    for(i=1; i<=n; i++) if(i!=e)
        c[i]-=c[e]*A[l][i];
    c[e] = -c[e] * A[l][e];
}
double Simplex(){
    int i,l,e;
    while(1){
        for(i=1; i<=n; i++) if(c[i]>EPS) break;
        if((e=i) == n+1) return v;
        double temp = INF;
        for(i = 1; i <= m; i++)
            if( A[i][e]>EPS && b[i]/A[i][e]<temp )
                temp = b[i] / A[i][e], l = i;
        if (temp == INF) return INF;
        Pivot(l,e);
    }
}