NOIPのテンプレートまとめ
このブログはまだ完全に書き終わっていないので、後で更新しますが、いつになったのか分かりません.しかし、小さな貢献をして、皆さんに役に立つことを望んでいます.
数論
GCD
LL gcd(LL a, LL b) { return !b ? a : gcd(b, a%b); }EXGCD
// gcd(a, b) = a*x+b*y;
LL exgcd(LL a, LL b, LL &x, LL &y) {
if(!b) { x = 1; y = 0; return a; }
LL x0, y0, d = exgcd(b, a%b, x0, y0);
x = y0; y = x0-(a/b)*y0;
return d;
}LUCAS
// C(n,m) = C(n/p, m/p)*C(n%p, m%p) (mod p) (when 0 <= m <= n)
// C(n,m) = 0 (mod p) (when m > n)
LL lucas(LL n, LL m, LL MOD) {
if(m > n) return 0;
if(n < MOD) return comb(n, m, MOD);
return lucas(n/MOD, m/MOD, MOD)*comb(n%MOD, m%MOD, MOD)%MOD;
}拡張LUCAS
ぎゃくげん
// a^-1
LL inv(LL a, LL MOD) {
LL x,y;
exgcd(a, MOD, x, y);
return (x%MOD+MOD)%MOD;
}
vfac[0] = vfac[1] = 1;
for(int i = 2; i <= maxn; i++) vfac[i] = (MOD-MOD/i)*vfac[MOD%i]%MOD;CRT
// x = a (mod m)
LL crt(LL *va, LL *vm, int n) {
LL sum = 1, ans = 0;
for(int t = 0; t < n; t++) sum *= vm[t];
for(int t = 0; t < n; t++) {
LL mi = sum/vm[t], vmi = inv(mi, vm[t]);
ans += mi*vmi%sum*va[t]%sum;
if(ans >= sum) ans -= sum;
}
return ans;
}拡張CRT
配列の組合せ
カトラン数
inline LL catalan(LL N, LL MOD) { return comb(2*N, N, MOD)/(N+1); }まちぎょうれつ
// D(1) = 0, D(2) = 1
// D(n) = (n-1)*(D(n-1)+D(n+2))
LL D[maxn];
void cuopai(int N, int MOD) {
D[1] = 0, D[2] = 1;
for(int i = 3; i <= N; i++) D[i] = (i-1)*(D[i-1]+D[i-2])%MOD;
}スターリングすう
高速べき乗
inline LL powermod(LL a, LL b, LL MOD) {
LL ans = 1; a %= MOD;
while(b) {
if(b&1) ans = ans*a%MOD, b--;
b >>= 1; a = a*a%MOD;
}
return ans%MOD;
}マトリックス高速べき乗
ふるいほう
//
int pri[maxn];
void checkprime(int N) {
pri[1] = 1;
for(int i = 2; i <= sqrt(N); i++) if(!pri[i])
for(int j = 2; j*i <= N; j++) pri[i*j] = 1;
} せんけいふるい
//
bool isprime[maxn];
int prime[maxn],mu[maxn],phi[maxn],tao[maxn],d[maxn],cnt_pri;
void linear_sieve(int N) {
isprime[1] = mu[1] = phi[1] = tao[1] = 1; d[1] = 0;
for(int i = 2; i <= N; i++) {
if(!isprime[i]) prime[++cnt_pri] = i, mu[i] = -1, phi[i] = i-1, tao[i] = 2, d[i] = 1;
for(int t = 0; t < cnt_pri; t++) {
int j = prime[t]*i;
if(j > N) break;
isprime[j] = 1;
mu[j] = mu[prime[t]]*mu[i];
phi[j] = phi[prime[t]]*phi[i];
tao[j] = tao[i]<<1;
d[j] = 1;
if(!(i%prime[t])) { mu[j] = 0; phi[j] = prime[t]*phi[i]; tao[j] = tao[i]/(d[i]+1)*(d[i]+2); d[j] = d[i]+1; break; }
}
}
}ガウス消元
リニアベース
図論
さいたんらく
floyd
dijkstra
SPFA
さぶんこうそくシステム
最短パスツリー
二分図
ハンガリー
にぶんずせんしょく
find union set
パス圧縮
#include ランク別集計
#include
"), lsa = 0;
else lsa = Query(a, b), printf("%d
",lsa);
}
return 0;
}
オーラかいろ
Tarjan
カットポイント
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idc;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == fa) continue;
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) iscut[u]++;
} else low[u] = min(low[u], dfn[v]);
}
}ブリッジエッジ
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idc;
int times = 0;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) bridge[++bridgecnt] = i;
} else if(v == fa) {
if(times) low[u] = min(low[u], dfn[v]);
times++;
} else low[u] = min(low[u], dfn[v]);
}
}しゅくてん
#include inline void read(T &x) {
int flag = 1; x = 0;
char ch = (char)getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = (char)getchar(); }
while(ch >= '0' && ch <= '9') { x = (x<<1)+(x<<3)+ch-'0'; ch = (char)getchar(); }
x *= flag;
}
inline void add(int u, int v) { e[++cnt].to = v; e[cnt].nxt = lst[u]; lst[u] = cnt; }
inline void ins(int u, int v) { in[v] = 1; ed[++cnt].to = v; ed[cnt].nxt = lst2[u]; lst2[u] = cnt; }
void tarjan(int x) {
int now = 0;
low[x] = dfn[x] = ++ind;
q[++top] = x; inq[x] = 1;
for(int i = lst[x]; i; i = e[i].nxt)
if(!dfn[e[i].to]) tarjan(e[i].to), low[x] = min(low[x], low[e[i].to]);
else if(inq[e[i].to]) low[x] = min(low[x], dfn[e[i].to]);
if(low[x] == dfn[x]) {
scc++;
while(now != x) {
inq[now = q[top--]] = 0;
blg[now] = scc;
sv[scc] += v[now];
sw[scc] += w[now];
}
}
}
void dp(int x) {
for(int i = lst2[x]; i; i = ed[i].nxt) {
dp(ed[i].to);
for(int j = m-sw[x]; j >= 0; j--)
for(int k = 0; k <= j; k++) f[x][j] = max(f[x][j], f[x][k]+f[ed[i].to][j-k]);
}
for(int j = m; j >= 0; j--) f[x][j] = j >= sw[x] ? f[x][j-sw[x]]+sv[x] : 0;
}
int main() {
read(n); read(m);
for(int i = 1; i <= n; i++) read(w[i]);
for(int i = 1; i <= n; i++) read(v[i]);
for(int i = 1; i <= n; i++) { read(d); if(d) add(d, i); }
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
cnt = 0;
for(int x = 1; x <= n; x++)
for(int i = lst[x]; i; i = e[i].nxt)
if(blg[e[i].to] != blg[x]) ins(blg[x], blg[e[i].to]);
for(int i = 1; i <= scc; i++) if(!in[i]) ins(scc+1, i);
dp(scc+1);
printf("%d
",f[scc+1][m]);
return 0;
}
MST
#includeトポロジのソート
ツリーチェーン分割
ツリー
重心
ちょつけい
dfsシーケンス
LCA
ばいりつ
定数クエリー
データ構造
はいれつ
チェーンテーブル
キュー
ゆうげんキュー
STテーブル
スタック
手書きの山
STL
左偏樹
#include
" );
else {
str[fx] >>= 1; str[fy] >>= 1;
int hp1 = merge(ls[fx], rs[fx]);
int hp2 = merge(ls[fy], rs[fy]);
ls[fx] = rs[fx] = dis[fx] = 0;
ls[fy] = rs[fy] = dis[fy] = 0;
fx = merge(fx, hp1);
fy = merge(fy, hp2);
int ans = merge(fx, fy);
printf( "%d
", str[ans] );
}
}
}
return 0;
}