c++ ライブラリ - yanprog @ ウィキ

ソート

sort(a.begin(), a.end(), greater<int>()) ; 
 

AhoCorasick

const int D=27;
struct AHO{
	vvi next;
	vvi hit;
	AHO(vvi pat){
		next.pb(vi(D,-1));
		hit.pb(vi());
		REP(ip,pat.size()){
			int st=0;
			REP(i,pat[ip].size()){
				int c=pat[ip][i];
				if(next[st][c]==-1){
					next[st][c]=next.size();
					next.pb(vi(D,-1));
					hit.pb(vi());
				}
				st=next[st][c];
				if(i==pat[ip].size()-1) hit[st].pb(ip);
			}
		}
 
		vi failuer;
		failuer.resize(next.size());
		queue<int> P;
		REP(c,D) if(next[0][c]!=-1) P.push(next[0][c]) ;
		REP(c,D) if(next[0][c]==-1) next[0][c]=0;
 
		while(!P.empty()){
			int st=P.front(); P.pop();
			REP(i,hit[failuer[st]].size()){
				hit[st].pb(hit[failuer[st]][i]);
			}
			REP(c,D){
				int nst=next[st][c];
				if(nst==-1 || nst==0)continue;
				failuer[nst]=next[failuer[st]][c];
				P.push(nst);
			}
			REP(c,D){
				if(next[st][c]==-1)next[st][c]=next[failuer[st]][c];
			}
		}
	}
};
 

文字列

vector<int> vectorFromString(string s){
  istringstream iss(s);
  vector<int> ret;
  int n;
  while(!iss.eof()){
    iss >> n;
    ret.push_back(n);
  }
  return ret;
}
 
 
string concantenate(vector<string> s){
	string ret;
	for(int i=0;i<s.size();i++){
		for(int j=0;j<s[i].size();j++){
			ret.pb(s[i][j]);
		}
	}
	return ret;
}
 
 

数学

ll extgcd(ll a, ll b, ll &x, ll &y){
  ll d=a;
  if(b!=0){
    d=extgcd(b, a%b, y, x);
    y-=(a/b)*x;
  }
  else{
    x=1,y=0;
  }
  return d;
}
 
ll modinverse(ll a, ll b){
  ll x,y;
  extgcd(a,b, x, y);
  return (x%b+b)%b;
}
 
 
struct modular{
  ll value;
  modular(){
    value=0;
  }
  modular(ll v){
    value=(v%mod+mod)%mod;
  }
  modular operator+(const modular b){
    return modular(value+b.value);
  }
  modular operator-(const modular b){
    return modular( value-b.value );
  }
  modular operator*(const modular b){
    return modular( value*b.value );
  }
  modular operator/(const modular b){
    return modular( value*modinverse(b.value, mod) );
  }
};
 
modular operator+(ll a, modular b){
  return modular(a)+b;
}
modular operator-(ll a, modular b){
  return modular(a)-b;
}
modular operator*(ll a, modular b){
  return modular(a)*b;
}
modular operator/(ll a, modular b){
  return modular(a)/b;
}
 
modular powm(moaular a, ll n){
	if(n==0)return a;
	if(n%2)return a*powm(a*a,n/2);
	return powm(a*a,n/2);
}
 
 
 
int sum(vector<int>& seq){
  int ret=0;
  REP(i, seq.size())ret+=seq[i];
  return ret;
}
 
ll truemod(ll n, ll m){
  return (n%m+m)%m;
}
 
ll fact(int n){
  if(n==0)return 1;
  else return n*fact(n-1);
}
 
ll comb(vi xn){
  int k=0;
  REP(i,xn.size())k+=xn[i];
  ll x=fact(k);
  ll y=1;
  REP(i,xn.size())y*=fact(xn[i]);
  return x/y;
}
 
vvi factor;
void seive(int n){
  factor.resize(n);
  FOR(p,2,n){
    if(factor[p].size()==0){
      for(int k=p;k<n;k+=p){
        int m=k;
        while(m%p==0){
          factor[k].pb(p);
          m/=p;
        }
      }
    }
  }
}
 
int isprime[8000];
vi make_primelist(int upto){
  REP(i, upto){
    isprime[i]=1;
  }
  FOR(p,2,upto){
    if(p*p>upto)break;
    if(isprime[p]==0)continue;
    int k=p+p;
    while(k<upto){
      isprime[k]=0;
      k+=p;
    }
  }
  vi ret;
  FOR(i,2,upto){
    if(isprime[i]==1)ret.push_back(i);
  }
  return ret;
}
 
 
comb([2,3,4])=(2+3+4)!/(2!3!4!)
 
 
vvl mul(vvl a, vvl b){
  int n1=a.size(), n2=b.size(), n3=b[0].size();
  vvl ret;
  ret.resize(n1);
  REP(i,n1)ret[i].resize(n3);
  REP(i,n1) REP(j,n3) REP(k,n2) ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%mod;
  return ret;
}
 
vvl powm(vvl s, vvl t, ll n){
  if(n==0)return t;
  if(n%2==0)return powm(mul(s,s), t, n/2);
  else return powm(mul(s,s), mul(s,t), n/2);
}
 
 
ll det(vvl x){
  ll h=1;
  int n=x.size();
  REP(i,n) REP(j,n) x[i][j]=truemod(x[i][j],mod);
  REP(i,n){
    FOR(j,i,n){
      if(x[j][i]!=0 && j!=i){
        REP(k,n)swap(x[j][k], x[i][k]);
        h*=-1;
        break;
      }
    }
    if(x[i][i]==0)return 0;
    ll v=modinverse(x[i][i], mod);
    h=truemod(h*x[i][i],mod);
    FOR(j,i+1,n){
      ll v2=v*x[j][i]%mod;
      REP(k,n) x[j][k]=truemod(x[j][k]-x[i][k]*v2,mod);
    }
  }
  return h;
}
 
ll CRTsolve(vl as, vl ns){
	ll N=1;
	REP(i,ns.size())N*=ns[i];
	ll ret=0;
	debug(N);
	REP(i,ns.size()){
		ll r,s;
		extgcd(ns[i], N/ns[i], r, s);
		ret+=as[i]*(N/ns[i])%N*s%N;
		ret%=N;
	}
	return (N+ret%N)%N;
}
 
 
 

フーリエ変換

const double pi=4.0*atan(1.0);
typedef complex<double> Complex;
const Complex I(0,1);
 
void fft_2(int delta,vector<Complex> &a){
	int n=a.size();
	double theta=delta*2*pi/n;
	for (int m = n; m >= 2; m >>= 1) {
		int mh = m >> 1;
		for (int i = 0; i < mh; i++) {
			Complex w = exp(i*theta*I);
			for (int j = i; j < n; j += m) {
				int k = j + mh;
				Complex x = a[j] - a[k];
				a[j] += a[k];
				a[k] = w * x;
			}
		}
		theta *= 2;
	}
	int i = 0;
	for (int j = 1; j < n - 1; j++) {
		for (int k = n >> 1; k > (i ^= k); k >>= 1);
		if (j < i) swap(a[i], a[j]);
	}
}
 
vector<Complex> pr(const vector<Complex> &a, const vector<Complex> &b){
	assert(a.size()==b.size());
	vector<Complex> ret(a.size());
	REP(i,ret.size()){
		ret[i]=a[i]*b[i];
	}
	return ret;
}
 
//bluestein's FFT
 
vector<Complex> fft(const vector<Complex> &x){
	int n=x.size();
	int m=1;
	while(m<2*n)m*=2;
	vector<Complex> a(m),b(m);
	for(ll i=0; i<n; i++){
		a[i]=( x[i]*exp(-pi*i*i/n*I) );
		b[i]=( exp(pi*i*i/n*I ) );
		if(i!=0)b[m-i]=b[i];
	}
	fft_2(1, a);
	fft_2(1, b);
	vector<Complex> c=pr(a,b);
	fft_2(-1,c);
	assert(c.size()==m);
	REP(i,c.size())c[i]/=m;
	assert(c.size()>=n);
	vector<Complex> ret(n);
	REP(i,n){
		ret[i]=c[i]*exp(-pi*i*i/n*I );
	}
	return ret;
}
 

最大流

//最大流を求める。頂点の個数の上限をMAX_Vにセットしておく。
//add_edge(A,B,C)でAからBへ容量Cの元辺を追加する。
// max_flow(s,t)でsからtへの最大流量を求める。
 
const int MAX_V=5010;
ll INF=1LL<<62-1;
 
struct edge{
	int to;
	ll cap;
	int rev;
};
 
struct cal_max_flow{
	vector<edge> G[MAX_V];
	int level[MAX_V];
	int iter[MAX_V];
 
	void add_edge(int from,int to,ll cap){
		G[from].pb((edge){to,cap,G[to].size()});
		G[to].pb((edge){from,0,G[from].size()-1});
	}
 
	void bfs(int s){
		nclr(level);
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(!que.empty()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}
 
	ll dfs(int v, int t, ll f){
		if(v==t)return f;
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(e.cap>0 && level[v]<level[e.to]){
				ll d=dfs(e.to, t, min(f,e.cap));
				if(d>0){
					e.cap-=d;
					G[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
 
	ll max_flow(int s,int t){
		ll flow=0;
		while(true){
			clr(iter);
			bfs(s);
			if(level[t]<0)return flow;
			ll f;
			while(f=dfs(s,t,INF)){
				flow+=f;
			}
		}
		return flow;
	}
};
 

最小費用流

struct edge{int to;ll cap;ll cost;int rev;
};
 
typedef pair<ll,int> pli;
 
const int MAX_V=40;
ll INF=1LL<<62-1;
 
struct cal_min_cost_flow{
	vector<edge> G[MAX_V];
	ll h[MAX_V];	//potential
	ll dist[MAX_V];
	int prev_v[MAX_V];
	int prev_e[MAX_V];
	void add_edge(int from, int to, ll cap, ll cost){
		G[from].pb( (edge){to,cap,cost,G[to].size()} );
		G[to].pb( (edge){from,0,-cost,G[from].size()-1} );
	}
 
	ll min_cost_flow(int s, int t, ll f){
		ll res=0;
		REP(v,MAX_V)h[v]=0;
 
		while(f>0){
			REP(v,MAX_V)dist[v]=INF;
			priority_queue<pli, vector<pli>, greater<pli> > Q;
			Q.push(pli(0,s));
			dist[s]=0;
 
			while(!Q.empty()){
				int v=Q.top().second; ll d=Q.top().first; Q.pop();
				if(dist[v]<d)continue; //古いのが残ってるかも
				assert(dist[v]==d);
 
				REP(i,G[v].size()){
					edge &e=G[v][i];
					int nv=e.to;
					ll nd=d+e.cost+h[v]-h[nv];
					if(e.cap>0 && dist[nv]> nd ){
						dist[nv]=nd;
						prev_v[nv]=v;
						prev_e[nv]=i;
						Q.push(pli(nd, nv));
					}
				}
			}
 
			if(dist[t]==INF)return -1;
			REP(v,MAX_V) h[v]+=dist[v];
 
			ll d=f; //流す量
			for(int v=t; v!=s; v=prev_v[v]){
				d=min(d, G[prev_v[v]][prev_e[v]].cap) ;
			}
			f-=d;
			res+=d*h[t];
 
			for(int v=t; v!=s; v=prev_v[v]){
				edge &e=G[prev_v[v]][prev_e[v]];
				e.cap-=d;
				G[v][e.rev].cap+=d;
			}
 
		}
		return res;
	}
};
 

グラフ

struct union_find{
	vi par,rank;
	union_find(int N){
		par=vi(N);
		rank=vi(N);
		REP(i,N){
			par[i]=i;
			rank[i]=0;
		}
	}
 
	int find(int x){
		assert(x<par.size());
		if(par[x]==x)return x;
		return par[x]=find(par[x]);
	}
 
	void unite(int x, int y){
		x=find(x);
		y=find(y);
		if(x==y)return;
		if(rank[x]<rank[y])par[x]=y;
		else{
			par[y]=x;
			if(rank[x]==rank[y])rank[x]++;
		}
  }
};
 
 
struct edge{
	int to;
	ll w;
};
 
/*bool comp_for_kruskal(const edge &e1, const edge &e2){
	return e1.w > e2.w;
}*/
 
struct graph{
	vector<vector<edge> > G;
	graph(int N){
		G=vector<vector<edge> >(N);
	}
 
	void add_edge(int s, int t, ll w){
		G[s].pb((edge){t,w});
		G[t].pb((edge){s,w});
	}
 
	vl dijkstra(int s){
		vl ret(G.size(), -1);
		priority_queue<pli,vector<pli>, greater<pli> > Q;
		Q.push(pli(0,s));
		while(!Q.empty()){
			ll w=Q.top().first;
			int t=Q.top().second;
			Q.pop();
			if(ret[t]!=-1)continue;
			ret[t]=w;
			REP(i,G[t].size()){
				Q.push(pli(w+G[t][i].w, G[t][i].to));
			}
		}
		return ret;
	}
 
 
 
	/*ll kruskal(){
		vector<edge> all_edge;
		REP(i,G.size()){
			REP(j,G[i].size()) all_edge.pb(G[i][j]);
		}
 
		sort(all_edge.begin(), all_edge.end(), comp_for_kruskal);
 
		union_find uf(G.size());
		ll ret=0;
		REP(i,all_edge.size()){
			edge e=all_edge[i];
			if( uf.find(e.from) != uf.find(e.to) ){
				ret += e.w;
				uf.unite(e.from, e.to);
			}
		}
		return ret;
	}*/
 
};
 
 

Range Minimun Query

struct RMQ{
	vl a;
	int n;
	RMQ(vl z){
		n=1;
		while(n<z.size())n*=2;
		a.clear();
		a.resize(2*n,INF);
		for(int i=0;i<z.size();i++){
			a[i+n]=z[i];
		}
		for(int i=n-1;i>=1;i--){
			a[i]=min(a[2*i], a[2*i+1]);
		}
	}
 
	void updata(int pos, ll val){
		pos+=n;
		a[pos]=val;pos/=2;
		while(pos){
			a[pos]=min(a[pos*2], a[pos*2+1]);
			pos/=2;
		}
	}
 
	ll get(int from, int to){
		ll ret=INF;
		from+=n;
		to+=n;
		while(from<to){
			if(from%2){
				ret=min(ret, a[from]);
				from++;
			}
			if(to%2){
				ret=min(ret, a[to-1]);
				to--;
			}
			from/=2;
			to/=2;
		}
		return ret;
	}
};
 

Fenwick_Tree

struct fenwick_tree{
	vector<ll> x;
	fenwick_tree(int n){
		int m=1;
		while(m<n)m*=2;
		x=vector<ll> (m);
	}
	// [i,j)区間
	void range(int i,int j, ll d){
		if(i!=0){
			range(0,j,d);
			range(0,i,-d);
			return;
		}
		j-=1;
		for(j;j>=0;j=(j&(j+1))-1){
			x[j]+=d;
		}
	}
	ll point(int k){
		ll ret=0;
		for(;k<x.size(); k|=k+1) ret+=x[k];
		return ret;
	}
};
 
 

その他

辞書順でlb以上の最小元
 
string cal(string lb){
	if(check(lb))return lb;
	ll n=sz(lb);
	string a;
	bool ok=false;
	for (ll pos = n-1; pos >=0 ; --pos){
		a=string(lb.begin(), lb.begin()+pos+1);
		for(char c=lb[pos]+1; c<='9'; c++){
			a[pos]=c;
			if(check(a))goto J;
		}
	}
	return "";
J:
	ll m=n-sz(a);
	rep(k,m){
		for(char c='0'; c<='9'; c++){
			if(check(a+c)){
				a+=c;
				break;
			}
		}
	}
	assert(sz(a)==n);
	return a;
}
 
AnagralListで使用。
string comp(string xs,vi xn,int th){
  int k=0;
  REP(i,xn.size())k+=xn[i];
  if(k==0)return"";
  REP(i,xs.size()){
    char c=xs[i];
    int m=xn[i];
    if(m==0)continue;
    xn[i]--;
    ll g=comb(xn);
    if(th<g){
      string t;
      t.push_back(c);
      return t+comp(xs,xn,th);
    }
    xn[i]++;
    th-=g;
  }
}
 
struct ANT{
	int x,y,dx,dy;
	ANT(){x=0,y=0,dx=1,dy=0;}
	void L(){
		int ndx=-dy,ndy=dx;
	  dx=ndx;dy=ndy;
	}
	void R(){
		L();L();L();
	}
	void W(){
	  x+=dx;y+=dy;
	}
};
 
 

数列の推測

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
 
 
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define debug2(x)  cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl;
 
 
 
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
 
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
 
 
ll mod=1000000007;
 
ll extgcd(ll a, ll b, ll &x, ll &y){ 
  ll d=a; 
  if(b!=0){ 
    d=extgcd(b, a%b, y, x); 
    y-=(a/b)*x; 
  } 
  else{ 
    x=1,y=0; 
  } 
  return d; 
} 
 
ll modinverse(ll a, ll b){
  ll x,y;
  extgcd(a,b, x, y);
  return (x%b+b)%b;
}
 
ll truemod(ll n, ll m){ 
  return (n%m+m)%m; 
} 
 
 
ll det(vvl x){
  ll h=1;
  int n=x.size();
  REP(i,n) REP(j,n) x[i][j]=truemod(x[i][j],mod);
  REP(i,n){
    FOR(j,i,n){
      if(x[j][i]!=0 && j!=i){
        REP(k,n)swap(x[j][k], x[i][k]);
        h*=-1;
        break;
      }
    }
    if(x[i][i]==0)return 0;
    ll v=modinverse(x[i][i], mod);
    h=truemod(h*x[i][i],mod);
    FOR(j,i+1,n){
      ll v2=v*x[j][i]%mod;
      REP(k,n) x[j][k]=truemod(x[j][k]-x[i][k]*v2,mod);
    }
  }
  return h;
}
 
vvl inverseMatrix(vvl x, vvl y){
  int n=x.size();
  REP(i,n) REP(j,n){
    x[i][j]=truemod(x[i][j], mod);
  }
  REP(i,n){
    FOR(j,i,n){
      if(x[j][i]!=0){
        if(j!=i){
          REP(k,n)swap(x[j][k], x[i][k]);
          REP(k,y[0].size()) swap(y[j][k], y[i][k]);
        }
        break;
      }
    }
    ll v=modinverse(x[i][i], mod);
    REP(k,n)x[i][k]=truemod(x[i][k]*v, mod);
    REP(k,y[0].size())y[i][k]=truemod(y[i][k]*v, mod);
    REP(j,n) if(i!=j){
      ll v2=x[j][i];
      REP(k,n) x[j][k]=truemod(x[j][k]-x[i][k]*v2, mod);
      REP(k,n) y[j][k]=truemod(y[j][k]-y[i][k]*v2, mod);
    }
  }
  REP(i,x.size()){
    debug2(x[i]);
  }
 
  return y;
}
 
vvl toeplitz(vl v, int start, int n){
  vvl x(n);
  REP(i,n)x[i].resize(n);
  REP(i,n) REP(j,n) x[i][j]=v[start+i+j];
  return x;
}
 
 
int main(){
  vl v;
  ll a=1,b=1;
  REP(i,100){
    v.push_back(a);
    a=3*b+7*a;
    b=2*a+5*b;
  }
  debug2(v);
 
  FOR(i,1,10) cout << i << "  " << det(toeplitz(v, 2, i)) << endl;
  vvl z=inverseMatrix(toeplitz(v,0,2), toeplitz(v,1,2));
  REP(i,z.size()){
    debug2(z[i]);
  }
 
  return 0;
}