@一句话题解

Hello, 2020!

codechef - SADPAIRS：求点双，建出圆方树，然后对于 G 相同的点集建虚树 + 差分一下即可求出答案。唯一需要注意的可能是图不一定连通，可以建虚点解决。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 400000;
const int MAXG = 1000000;

struct Graph{
	struct edge{
		int to; edge *nxt;
	}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt;
	Graph() {ecnt = edges;}
	void addedge(int u, int v) {
//		printf("! %d %d
", u, v);
		edge *p = (++ecnt);
		p->to = v, p->nxt = adj[u], adj[u] = p;
		p = (++ecnt);
		p->to = u, p->nxt = adj[v], adj[v] = p;
	}
}G1, G2, G3;

#define rep(G, x) for(Graph::edge *p=G.adj[x];p;p=p->nxt)
typedef long long ll;

int dfn[MAXN + 5], low[MAXN + 5], stk[MAXN + 5], tp, dcnt, cnt;
void dfs1(int x, int f) {
	dfn[x] = low[x] = (++dcnt);
	rep(G1, x) {
		if( p->to == f ) continue;
		if( !dfn[p->to] ) {
			stk[++tp] = p->to;
			dfs1(p->to, x), low[x] = min(low[x], low[p->to]);
			if( low[p->to] >= dfn[x] ) {
				G2.addedge(++cnt, x);
				do {
					G2.addedge(cnt, stk[tp]);
				}while( stk[tp--] != p->to );
			}
		}
		else low[x] = min(low[x], dfn[p->to]);
	}
}

int fa[20][MAXN + 5], dep[MAXN + 5];
void dfs2(int x, int f) {
	fa[0][x] = f;
	for(int i=1;i<20;i++)
		fa[i][x] = fa[i-1][fa[i-1][x]];
	dfn[x] = (++dcnt), dep[x] = dep[f] + 1;
	rep(G2, x) {
		if( p->to == f ) continue;
		dfs2(p->to, x);
	}
}
int lca(int x, int y) {
	if( dep[x] < dep[y] ) swap(x, y);
	for(int i=19;i>=0;i--)
		if( dep[fa[i][x]] >= dep[y] )
			x = fa[i][x];
	if( x == y ) return x;
	for(int i=19;i>=0;i--)
		if( fa[i][x] != fa[i][y] )
			x = fa[i][x], y = fa[i][y];
	return fa[0][x];
}

int N, E;
ll ans[MAXN + 5], res[MAXN + 5];
vector<int>v[MAXG + 5];

bool cmp(int x, int y) {
	return dfn[x] < dfn[y];
}

int a[MAXN + 5], tot;
void insert(int x) {
	if( !tp ) stk[++tp] = x;
	else {
		int l = lca(x, stk[tp]);
		while( tp && dfn[l] < dfn[stk[tp]] ) {
			int y = stk[tp--]; a[++tot] = y;
			if( !tp || dfn[l] > dfn[stk[tp]] )
				stk[++tp] = l, G3.addedge(l, y);
			else G3.addedge(stk[tp], y);
		}
		stk[++tp] = x;
	}
}
bool tag[MAXN + 5];
int build(int i) {
	tot = 0;
	for(int j=0;j<v[i].size();j++)
		insert(v[i][j]), tag[v[i][j]] = true;
	while( tp ) {
		int y = stk[tp--]; a[++tot] = y;
		if( tp ) G3.addedge(stk[tp], y);
	}
	return a[tot];
}
int siz[MAXN + 5];
void dfs3(int x, int f) {
	siz[x] = tag[x];
	rep(G3, x) {
		if( p->to == f ) continue;
		dfs3(p->to, x), siz[x] += siz[p->to];
	}
}
void dfs4(int x, int f, int tot) {
	ll del = 0, tmp = tag[x];
	rep(G3, x) {
		if( p->to == f ) continue;
		if( x == N + 1 )
			dfs4(p->to, x, siz[p->to]);
		else {
			dfs4(p->to, x, tot);
			ll k = 1LL*siz[p->to]*(tot - siz[p->to]);
			res[fa[0][p->to]] += k, res[x] -= k;
		}
		del += tmp*siz[p->to], tmp += siz[p->to];
	}
	ans[x] += del + 1LL*tmp*(tot - siz[x]);
}
void clear() {
	G3.ecnt = G3.edges;
	for(int i=1;i<=tot;i++)
		G3.adj[a[i]] = NULL, tag[a[i]] = false;
}

void dfs5(int x, int f) {
	rep(G2, x) {
		if( p->to == f ) continue;
		dfs5(p->to, x), res[x] += res[p->to];
	}
	ans[x] += res[x];
}

int main() {
	scanf("%d%d", &N, &E), cnt = N + 1;
	for(int i=1;i<=N;i++) {
		int G; scanf("%d", &G);
		v[G].push_back(i);
	}
	for(int i=1;i<=E;i++) {
		int a, b; scanf("%d%d", &a, &b);
		G1.addedge(a, b);
	}
	for(int i=1;i<=N;i++)
		if( !dfn[i] ) dfs1(i, 0), G2.addedge(N + 1, i);
	dcnt = 0, dfs2(N + 1, 0);
	for(int i=1;i<=MAXG;i++)
		if( v[i].size() ) {
			sort(v[i].begin(), v[i].end(), cmp);
			int rt = build(i); dfs3(rt, 0), dfs4(rt, 0, siz[rt]), clear();
		}
	dfs5(N + 1, 0);
	for(int i=1;i<=N;i++)
		printf("%lld
", ans[N + 1] + ans[i]);
}

atcoder - AGC030D：考虑每一对数的贡献。从后往前作 dp，定义 f[0/1][i][j][k] 表示经过最后 i 次操作，有多少种可能 j 在 k 前面/后面。i 一维可以滚动数组。用一些 trick 就可以得到 O(n^2) 的算法。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 3000;
const int MOD = int(1E9) + 7;
inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
inline int mul(int x, int y) {return 1LL*x*y%MOD;}

int pw2[MAXN + 5];
void init() {
	pw2[0] = 1;
	for(int i=1;i<=MAXN;i++)
		pw2[i] = mul(2, pw2[i-1]);
}

int f[2][MAXN + 5][MAXN + 5], lst[MAXN + 5][MAXN + 5];
void update(int l, int r, int k) {
	f[0][l][r] = mul(f[0][l][r], pw2[lst[l][r] - k - 1]);
	f[1][l][r] = mul(f[1][l][r], pw2[lst[l][r] - k - 1]);
	lst[l][r] = k;
}
void transform(int &x, int &y) {
	int t = (x + y) % MOD;
	x = y = t;
}

int A[MAXN + 5], X[MAXN + 5], Y[MAXN + 5];
int main() {
	init();
	int N, Q; scanf("%d%d", &N, &Q);
	for(int i=1;i<=N;i++) scanf("%d", &A[i]);
	for(int i=1;i<=Q;i++) scanf("%d%d", &X[i], &Y[i]);
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
			f[0][i][j] = 1, lst[i][j] = Q + 1;
	for(int i=Q;i>=1;i--) {
		if( X[i] > Y[i] ) swap(X[i], Y[i]);
		for(int j=1;j<=X[i]-1;j++) {
			update(j, X[i], i), update(j, Y[i], i);
			transform(f[0][j][X[i]], f[0][j][Y[i]]);
			transform(f[1][j][X[i]], f[1][j][Y[i]]);
		}
		for(int j=X[i]+1;j<=Y[i]-1;j++) {
			update(X[i], j, i), update(j, Y[i], i);
			transform(f[0][X[i]][j], f[1][j][Y[i]]);
			transform(f[1][X[i]][j], f[0][j][Y[i]]);
		}
		for(int j=Y[i]+1;j<=N;j++) {
			update(X[i], j, i), update(Y[i], j, i);
			transform(f[0][X[i]][j], f[0][Y[i]][j]);
			transform(f[1][X[i]][j], f[1][Y[i]][j]);
		}
		update(X[i], Y[i], i);
		transform(f[0][X[i]][Y[i]], f[1][X[i]][Y[i]]);
	}
	int ans = 0;
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++) {
			update(i, j, 0);
			if( A[i] < A[j] ) ans = add(ans, f[1][i][j]);
			if( A[i] > A[j] ) ans = add(ans, f[0][i][j]);
		}
	printf("%d
", ans);
}

codechef - CSUBSQ：先容斥转成 |max - min| < W。固定选 i 为 max，则需要询问 [i-W+1, i-1] 求个背包的结果。分治，每次处理中点 mid 到两边的背包，利用这个信息处理跨越中点询问区间。最后只有两个背包 + 一个物件，直接 O(K) 枚举。时间复杂度 O(NKlogN)。加了取模优化是真的快。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXK = 50;
const int MAXN = 100000;
const int MOD = int(1E9) + 7;
int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}

int f[MAXK + 5][MAXN + 5], g[MAXK + 5][MAXN + 5], ans;

int l[MAXN + 5], r[MAXN + 5], A[MAXN + 5];
int N, K, W;

int get() {
	for(int i=0;i<K;i++)
		for(int j=0;j<=N;j++)
			f[i][j] = 0;
	f[0][0] = 1;
	for(int j=1;j<=N;j++)
		for(int i=0;i<K;i++)
			f[i][j] = add(f[i][j-1], f[i<A[j]?i-A[j]+K:i-A[j]][j-1]);
	return f[0][N];
}

void update(int k) {
	ans = (ans >= k ? ans - k : ans + MOD - k);
}
void divide_conquer(int L, int R) {
	if( L == R ) {
		if( l[L] == r[L] )
			update(A[L] == 0), update(A[L] + A[L-1] == 0 || A[L] + A[L-1] == K);
		else if( l[L] > r[L] )
			update(A[L] == 0);
		return ;
	}
	int M = (L + R) >> 1;
	
	for(int i=0;i<K;i++) f[i][M + 1] = 0;
	f[0][M + 1] = 1;
	for(int j=M;j>=L;j--)
		for(int i=0;i<K;i++)
			f[i][j] = add(f[i][j+1], f[i<A[j]?i-A[j]+K:i-A[j]][j+1]);
	
	for(int i=0;i<K;i++) g[i][M] = 0;
	g[0][M] = 1;
	for(int j=M+1;j<=R;j++)
		for(int i=0;i<K;i++)
			g[i][j] = add(g[i][j-1], g[i<A[j]?i-A[j]+K:i-A[j]][j-1]);
			
	for(int i=M+2;i<=R+1&&i<=N;i++)
		if( L <= l[i] && l[i] <= M ) {
			for(int j=0;j<K;j++)
				update(1LL*f[j][l[i]]*g[(K-j+K-A[i])%K][r[i]]%MOD);
		}
		
	divide_conquer(L, M), divide_conquer(M + 1, R);
}

void solve() {
	scanf("%d%d%d", &N, &K, &W);
	for(int i=1;i<=N;i++)
		scanf("%d", &A[i]), l[i] = max(1, i - W + 1), r[i] = i - 1;
	ans = get(); update(1);
	if( W ) divide_conquer(1, N);
	printf("%d
", ans);
}
//i - W < j
int main() {
	int T; scanf("%d", &T);
	while( T-- ) solve();
}

atcoder - AGC035C：N = 2^M 无解。N = 2^M - 1 时，取 P = 2^(M-1)，连 (i+P)+N -> i -> P -> (i+P) -> i+N (1 <= i < P) 即可，P+N 随便连向一个 i+N。若 N = 2^M - 1 + R，前面的 2^M - 1 一样构造，连 P -> 2^M，剩下的 k 只需要找对应的 j 使得 j xor P 是 k xor 2^M，连向 j 即可。

#include <cstdio>
int main() {
	int N, M; scanf("%d", &N);
	for(M = 0; (M << 1 | 1) <= N; M = (M << 1 | 1));
	if( N == 1 || M + 1 == N )
		puts("No");
	else {
		puts("Yes");
		int P = (M + 1) >> 1;
		for(int i=1;i<P;i++) {
			printf("%d %d
", i + N + P, i);
			printf("%d %d
", i, P);
			printf("%d %d
", P, i + P);
			printf("%d %d
", i + P, i + N);
		}
		printf("%d %d
", P + N, N + 1);
		if( M != N ) {
			printf("%d %d
", P, M + 1);
			printf("%d %d
", M + 1 + N, M + 2 + N);
			for(int i=M+2;i<=N;i++) {
				int x = i - (M + 1);
				if( x < P ) printf("%d %d
", i + N, x + P);
				else if( x == P ) printf("%d %d
", i + N, x);
				else printf("%d %d
", i + N, x - P);
				printf("%d %d
", M + 1, i);
			}
		}
	}
}

poj - 1228：N 个点恰好组成一个凸包，首先需要这 N 个点在凸包上，其次需要加入任意一个点都会出现 > 180° 的角，等价于凸包上的任意两个相邻的点之间连的边，都在凸包上与一个 = 180° 的角相邻。注意特判 N 个点共线的情况（包括 N = 1, N = 2 等特殊情况）。

#include <cstdio>
#include <algorithm>
using namespace std;

const double INF = 1E9;
const int MAXN = 2000;

struct point{
	double x, y;
	point() : x(), y() {}
	point(double _x, double _y) : x(_x), y(_y) {}
	
	friend point operator - (point a, point b) {return point(a.x - b.x, a.y - b.y);}
	friend bool operator < (point a, point b) {return (a.x == b.x ? a.y < b.y : a.x < b.x);}
	friend double operator ^ (point a, point b) {return a.x*b.y - a.y*b.x;}
	
	friend double slope(point a, point b) {
		if( a.x == b.x )
			return a.y < b.y ? INF : -INF;
		else return (a.y - b.y) / (a.x - b.x);
	}
	friend void convex(point *A, int n, point *B, int &m) {
		static point t[MAXN + 5], s[MAXN + 5];
		for(int i=0;i<n;i++) t[i] = A[i]; sort(t, t + n);
		
		int cnt = 0, tp = 0;
		for(int i=0;i<n;i++) {
			while( tp >= 2 && slope(s[tp - 1], s[tp]) > slope(s[tp], t[i]) )
				tp--;
			s[++tp] = t[i];
		}
		for(int i=1;i<=tp;i++) B[cnt++] = s[i];
		tp = 0;
		for(int i=0;i<n;i++) {
			while( tp >= 2 && slope(s[tp - 1], s[tp]) < slope(s[tp], t[i]) )
				tp--;
			s[++tp] = t[i];
		}
		for(int i=tp-1;i>=2;i--) B[cnt++] = s[i];
		m = cnt;
	}
	friend void read(point &A) {
		scanf("%lf%lf", &A.x, &A.y);
	}
};

point p[MAXN + 5];

void solve() {
	int n; scanf("%d", &n);
	for(int i=0;i<n;i++) read(p[i]);
	int m; convex(p, n, p, m);
	if( n == 1 || n == 2 || n != m )
		puts("NO");
	else {
		int cnt = 1; p[n] = p[0], p[n+1] = p[1];
		for(int i=2;i<=n+1;i++) {
			if( (p[i] - p[i-1]) ^ (p[i-1] - p[i-2]) ) {
				if( cnt == 1 ) {
					puts("NO");
					return ;
				}
				cnt = 1;
			}	
			else cnt++;
		}
		puts("YES");
	}
}

int main() {
	int T; scanf("%d", &T);
	while( T-- ) solve();
}

codeforces - 963E：直接高斯消元 O(R^6)。注意到网格图，那么当 |i - j| > 2*R 时 a[i][j] 恒等于 0。那么每一行消元只会用到 R*R 个元素，所以优化一下复杂度就是 O(R^4)。注意到对角线上的元素在消元过程中不可能变为 0（考虑方程的实际意义是 dp 转移式），所以不需要交换行。另外，本题需要消成上三角 + 回代。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = int(1E9) + 7;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

#define lb(x) max(0, x - d)
#define rb(x) min(n - 1, x + d)

struct mint{
	int x; mint(int _x=0) : x(_x) {}
	friend mint operator + (mint a, mint b) {return a.x + b.x >= MOD ? a.x + b.x - MOD : a.x + b.x;}
	friend mint operator - (mint a, mint b) {return a.x - b.x < 0 ? a.x - b.x + MOD : a.x - b.x;}
	friend mint operator * (mint a, mint b) {return 1LL*a.x*b.x%MOD;}
	friend mint pow(mint b, int p) {
		mint ret = 1;
		for(int i=p;i;i>>=1,b*=b)
			if( i & 1 ) ret *= b;
		return ret;
	}
	friend mint operator / (mint a, mint b) {return a*pow(b, MOD-2);}
	friend void operator += (mint &a, mint b) {a = a + b;}
	friend void operator -= (mint &a, mint b) {a = a - b;}
	friend void operator *= (mint &a, mint b) {a = a * b;}
	friend void operator /= (mint &a, mint b) {a = a / b;}
};

mint A[8000][8000];
void gauss(int n, int d) {
	for(int i=0;i<n;i++) {
		mint k = pow(A[i][i], MOD-2);
		for(int j=i;j<=rb(i);j++)
			A[i][j] *= k;
		A[i][n] *= k;
		for(int j=i+1;j<=rb(i);j++) {
			k = A[j][i];
			for(int p=i;p<=rb(i);p++)
				A[j][p] -= k*A[i][p];
			A[j][n] -= k*A[i][n];
		}
	}
	for(int i=n-1;i>=0;i--)
		for(int j=i-1;j>=0;j--)
			A[j][n] -= A[i][n] * A[j][i];
}

int R; mint p[4], s;
int id[105][105], cnt;

int main() {
	scanf("%d", &R);
	for(int i=0;i<4;i++) scanf("%d", &p[i].x), s += p[i];
	for(int i=0;i<4;i++) p[i] /= s;
	int mx = 0;
	for(int i=-R;i<=R;i++)
		for(int j=-R;j<=R;j++)
			if( i*i + j*j <= R*R )
				id[i+R][j+R] = (cnt++);
	for(int i=-R;i<=R;i++)
		for(int j=-R;j<=R;j++) {
			if( i*i + j*j > R*R ) continue;
			int t1 = id[i+R][j+R];
			for(int k=0;k<4;k++) {
				int x0 = i + dx[k], y0 = j + dy[k];
				if( x0*x0 + y0*y0 > R*R ) continue;
				int t2 = id[x0+R][y0+R];
				A[t1][t2] -= p[k], mx = max(mx, abs(t1 - t2));
			}
			A[t1][t1] = A[t1][cnt] = 1;
		}
	gauss(cnt, mx);
	printf("%d
", A[id[R][R]][cnt].x);
}

bzoj - 1152：概率生成函数模板题。详见论文《浅谈生成函数在掷骰子问题上的应用》（杨懋龙）。推出来 (ans = sum_{i}n^i*[字符串有长度为 i 的 border])，用 kmp 即可，时间复杂度 O(n)。

#include <cstdio>

const int MAXN = 100000;
const int MOD = int(1E4);

int pw[MAXN + 5];

int a[MAXN + 5], f[MAXN + 5], n, t;
void solve() {
	int m; scanf("%d", &m);
	for(int i=1;i<=m;i++)
		scanf("%d", &a[i]);
	f[0] = -1, f[1] = 0;
	for(int i=2;i<=m;i++) {
		f[i] = f[i-1];
		while( f[i] != -1 && a[f[i]+1] != a[i] )
			f[i] = f[f[i]];
		f[i]++;
	}
	int ans = 0;
	for(int p=m;p;p=f[p])
		ans = (ans + pw[p])%MOD;
	printf("%04d
", ans);
}

int main() {
	scanf("%d%d", &n, &t);
	pw[0] = 1;
	for(int i=1;i<=MAXN;i++)
		pw[i] = pw[i-1]*n%MOD;
	while( t-- ) solve();
}

codefoces - 235D：与 bzoj3451 挺类似的，只是把树换成了基环树。一样的思路做即可（还不用 fft）。

#include <cstdio>

const int MAXN = 3000;

struct edge{
	int to; edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = edges;
void addedge(int u, int v) {
	edge *p = (++ecnt);
	p->to = v, p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->nxt = adj[v], adj[v] = p;
}
#define rep(x) for(edge *p=adj[x];p;p=p->nxt)

bool vis[MAXN + 5], tag[MAXN + 5];
int a[MAXN + 5], cnt, siz;
void dfs1(int x, int f) {
	vis[a[++cnt] = x] = true;
	rep(x) {
		if( p->to == f ) continue;
		if( vis[p->to] ) {
			siz = 0;
			for(int j=cnt;;j--) {
				tag[a[j]] = true, siz++;
				if( a[j] == p->to ) break;
			}
		}
		else dfs1(p->to, x);
		if( siz ) break;
	}
	a[cnt--] = 0, vis[x] = false;
}

double ans;

double get(int s, int d) {
	if( s >= 2 ) {
		int p = s - 2, q = siz - s, r = d - s + 2;
		return 1.0 / (r + p) + 1.0 / (r + q) - 1.0 / (r + p + q);
	}
	else return 1.0 / d;
}
void dfs2(int x, int s, int d) {
	vis[x] = true, d++;
	if( tag[x] ) s++;
	ans += get(s, d);
	rep(x) {
		if( vis[p->to] ) continue;
		dfs2(p->to, s, d);
	}
}

int main() {
	int n; scanf("%d", &n);
	for(int i=1;i<=n;i++) {
		int a, b; scanf("%d%d", &a, &b);
		addedge(a + 1, b + 1);
	}
	dfs1(1, 0);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) vis[j] = false;
		dfs2(i, 0, 0);
	}
	printf("%.9f
", ans);
}

codeforces - 457D：考虑一个覆盖 x 行 y 列的方案中 2^(x+y) 的组合意义：所有子集。反过来，这样一个方案会在其他包含它的方案中被统计，那么除这 x 行 y 列空余位置随便填数即可。剩下的就很简单了。注意合理利用对数运算计算组合数与比较大小。

#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
using namespace std;

const int MAXM = 100000;

long double fct[MAXM + 5];
void init() {
	for(int i=1;i<=MAXM;i++)
		fct[i] = fct[i-1] + log10(i);
}
long double comb(int n, int m) {
	return fct[n] - fct[m] - fct[n-m];
}

int main() {
	init();
	int n, m, k; scanf("%d%d%d", &n, &m, &k);
	long double ans = 0;
	for(int i=0;i<=n;i++) {
		for(int j=0;j<=n;j++) {
			int t = (i + j)*n - i*j;
			if( k < t ) continue;
			long double d = comb(m-t, k-t) - comb(m, k) + comb(n, i) + comb(n, j);
			ans += pow(10, d);
			if( d > 99 ) {
				printf("1e99");
				return 0;
			}
		}
	}
	if( log10(ans) > 99 ) printf("1e99");
	else cout << fixed << setprecision(9) << ans;
}

topcoder - SRM686D1L2：答案为 (sum_{i=0}^{n}{n rack i}i^m)，斯特林反演并交换求和得到 (sum_{j=0}^{m}{m race j}j!(sum_{i=0}^{n}{n rack i}{n choose j}))，考虑 (sum_{i=0}^{n}{n rack i}{n choose j}) 的组合意义发现它等于 (sum_{i=0}^{n}{i rack j}{n choose i}(n-i)!)。O(nm) 预处理即可。

#include <cstdio>
#include <vector>
using namespace std;

const int MOD = int(1E9) + 7;
const int MAXM = 300;
const int MAXN = 100000;

int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
int mul(int x, int y) {return 1LL*x*y%MOD;}

int pow_mod(int b, int p) {
	int ret = 1;
	for(int i=p;i;i>>=1,b=mul(b,b))
		if( i & 1 ) ret = mul(ret, b);
	return ret;
}

int s1[MAXN + 5][MAXM + 5], s2[MAXM + 5][MAXM + 5];
int fct[MAXN + 5], ifct[MAXN + 5];
void init() {
	fct[0] = 1;
	for(int i=1;i<=MAXN;i++) fct[i] = mul(fct[i-1], i);
	ifct[MAXN] = pow_mod(fct[MAXN], MOD - 2);
	for(int i=MAXN-1;i>=0;i--)
		ifct[i] = mul(ifct[i+1], i+1);
	s1[0][0] = 1;
	for(int i=1;i<=MAXN;i++)
		for(int j=1;j<=MAXM;j++)
			s1[i][j] = add(s1[i-1][j-1], mul(s1[i-1][j], i-1));
	for(int j=0;j<=MAXM;j++)
		for(int i=1;i<=MAXN;i++)
			s1[i][j] = add(s1[i-1][j], mul(s1[i][j], ifct[i]));
	s2[0][0] = 1;
	for(int i=1;i<=MAXM;i++)
		for(int j=1;j<=MAXM;j++)
			s2[i][j] = add(s2[i-1][j-1], mul(s2[i-1][j], j));
}

class CyclesNumber{
	public :
		int get(int n, int m) {
			int ret = 0;
			for(int j=0;j<=m;j++)
				ret = add(ret, mul(s1[n][j], mul(s2[m][j], fct[j])));
			return mul(ret, fct[n]);
		}
		vector<int>getExpectation(vector<int>n, vector<int>m) {
			init(); vector<int>ans;
			for(int i=0;i<n.size();i++)
				ans.push_back(get(n[i], m[i]));
			return ans;
		}
};

atcoder - AGC030C：K <= 500 时直接一行一种颜色，否则构造 500*500 的方阵，按对角线涂颜色。保证每条对角线（模意义下）要么是一种颜色，要么是两种颜色交替出现，这样就可以构造 [500, 2*500] 内的所有数字。

#include <cstdio>

const int N = 500;

int a[N][N];

int main() {
	int K; scanf("%d", &K);
	if( K <= N ) {
		printf("%d
", K);
		for(int i=1;i<=K;i++) {
			for(int j=1;j<=K;j++)
				printf("%d%c", i, (j == K ? '
' : ' '));
		}
	}
	else {
		printf("%d
", N);
		int cnt = 0;
		for(int i=0;i<2*N-K;i++) {
			int x = 0, y = i, b = (++cnt);
			do {
				a[x][y] = b;
				x = (x + 1 == N ? 0 : x + 1);
				y = (y + 1 == N ? 0 : y + 1);
			}while( x );
		}
		for(int i=2*N-K;i<N;i++) {
			int x = 0, y = i, b[2] = {};
			b[0] = (++cnt), b[1] = (++cnt);
			do {
				a[x][y] = b[x & 1];
				x = (x + 1 == N ? 0 : x + 1);
				y = (y + 1 == N ? 0 : y + 1);
			}while( x );
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++)
				printf("%d%c", a[i][j], (j + 1 == N ? '
' : ' '));
		}
	}
}

codeforces - 1236F：连通块个数 = 点的个数 - 边的个数 + 环的个数。把方差拆成 E(x^2) - E^2(x) 的形式，然后就是个套路的平方期望。讨论一下即可。

#include <cstdio>
#include <vector>
using namespace std;
 
const int MAXN = 500000;
const int MOD = int(1E9) + 7;
 
struct mint{
	int x; mint(int _x=0) : x(_x) {}
	friend mint operator + (mint a, mint b) {return a.x + b.x >= MOD ? a.x + b.x - MOD : a.x + b.x;}
	friend mint operator - (mint a, mint b) {return a.x - b.x < 0 ? a.x - b.x + MOD : a.x - b.x;}
	friend mint operator * (mint a, mint b) {return 1LL*a.x*b.x%MOD;}
	friend void operator += (mint &a, mint b) {a = a + b;}
	friend void operator -= (mint &a, mint b) {a = a - b;}
	friend void operator *= (mint &a, mint b) {a = a * b;}
};
 
const mint INV2 = (MOD + 1) >> 1;
 
mint ipw2[MAXN + 10];
void init() {
	ipw2[0] = 1;
	for(int i=1;i<=MAXN+5;i++)
		ipw2[i] = ipw2[i-1]*INV2;
}
 
struct edge{
	int to; edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = edges;
void addedge(int u, int v) {
	edge *p = (++ecnt);
	p->to = v, p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->nxt = adj[v], adj[v] = p;
}
 
mint sum[MAXN + 5], deg[MAXN + 5], siz[MAXN + 5], all;
 
vector<int>v[MAXN + 5];
int n, m, tot;
 
int dfn[MAXN + 5], stk[MAXN + 5], dcnt, tp;
void dfs(int x, int f) {
	dfn[x] = (++dcnt), stk[++tp] = x;
	for(edge *p=adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		if( !dfn[p->to] ) dfs(p->to, x);
		else if( dfn[p->to] < dfn[x] ) {
			tot++;
			for(int i=tp;;i--) {
				v[tot].push_back(stk[i]);
				if( stk[i] == p->to ) break;
			}
			siz[tot] = v[tot].size(), all += ipw2[v[tot].size()];
			for(int i=0;i<v[tot].size();i++)
				sum[v[tot][i]] += ipw2[v[tot].size()];
		}
	}
	stk[tp--] = 0;
}
 
mint get1() {
	mint ret = 0, cnt = 1LL*m*(m-1)%MOD;
	for(int i=1;i<=n;i++) {
		ret += ipw2[1] + (n - 1)*ipw2[2]; // V * V
		ret -= (deg[i]*ipw2[2] + (m - deg[i])*ipw2[3])*2; // V * E
		ret += deg[i]*(deg[i] - 1)*ipw2[3]; // E * E
		cnt -= deg[i]*(deg[i]-1);
	}
	ret += cnt*ipw2[4] + m*ipw2[2]; // E * E
	
	for(int i=1;i<=tot;i++) {
		int s = v[i].size();
		ret += (siz[i]*ipw2[s] + (n - siz[i])*ipw2[s+1])*2; // V * F
		mint p = m - s, q = all - ipw2[s];
		for(int j=0;j<v[i].size();j++) {
			int x = v[i][j];
			ret -= (deg[x] - 2)*ipw2[s+1]*2; // E * F
			p -= deg[x] - 2;
			ret += (sum[x] - ipw2[s])*ipw2[s-1]; // F * F
			q -= (sum[x] - ipw2[s]);
		}
		ret -= (s*ipw2[s] + p*ipw2[s+2])*2; // E * F
		ret += ipw2[s] + q*ipw2[s]; // F * F
	}
	return ret;
}
 
mint get2() {
	mint ret = 0;
	ret += n*ipw2[1]; // V
	ret -= m*ipw2[2]; // E
	for(int i=1;i<=tot;i++) 
		ret += ipw2[v[i].size()]; // F
	return ret;
}
 
int main() {
	init(); scanf("%d%d", &n, &m);
	for(int i=1;i<=m;i++) {
		int u, v; scanf("%d%d", &u, &v);
		addedge(u, v), deg[u] += 1, deg[v] += 1;
	}
	dfs(1, 0);
	mint x = get1(), y = get2();
	printf("%d
", (x - y*y).x);
}

hdu - 4652：可以看成长度为 n，字符集大小为 m 的全相同/全不同字符串为终止状态的抛骰子期望次数。可以使用概率生成函数来解。因为这些字符串是对称的，所以它们的生成函数也是一样的。推出相同时为 (sum_{i=0}^{n-1}m^i)，不同时为 (sum_{i=1}^{n}frac{m^i}{m^{underline{i}}})。可以 O(n) 算。

#include <cstdio>
#include <cmath>
using namespace std;

void solve() {
	int op; scanf("%d", &op);
	int m, n; scanf("%d%d", &m, &n);
	if( op == 0 ) {
		printf("%.9f
", (m == 1 ? n : (pow(m,n)-1)/(m-1)));
	}
	else {
		double ans = 1;
		for(int i=n-1;i>=1;i--)
			ans = 1 + ans * m / (m - i);
		printf("%.9f
", ans);
	}
}

int main() {
	int T; scanf("%d", &T);
	while( T-- ) solve();
}

codeforces - 611G：旋转卡壳找经过某个点，能够将多边形面积进行尽可能均等划分的分界点。维护一下相邻点叉积、横纵坐标和即可。注意取模的问题，有些地方要比较大小所以不能取模。

#include <cstdio>

typedef long long ll;

const int MAXN = 500000;
const int MOD = int(1E9) + 7;

struct point{
	ll x, y; point() {}
	point(ll _x, ll _y) : x(_x), y(_y) {}
	
	friend point operator - (point a, point b) {return point(a.x - b.x, a.y - b.y);}
	friend ll operator ^ (point a, point b) {return a.x*b.y - a.y*b.x;}
	friend void operator -= (point &a, point b) {a = a - b;}
	
}p[MAXN + 5];

ll S; int n;

int nxt(int x) {return x + 1 == n ? 0 : x + 1;}
int lst(int x) {return x == 0 ? n - 1 : x - 1;}

int main() {
	scanf("%d", &n);
	for(int i=0;i<n;i++) scanf("%lld%lld", &p[i].x, &p[i].y);
	for(int i=n-1;i>=0;i--) p[i] -= p[0];
	for(int i=0;i<n;i++) S += p[nxt(i)]^p[i];
	ll t1 = 0; int j = n - 1;
	int ans = 0, t2 = 0, cnt = 0, sx = 0, sy = 0;
	for(int i=0;i<n;i++) {
		while( true ) {
			int k = nxt(j);
			ll s = t1 + (p[k]^p[j]) + (p[i]^p[k]);
			if( S - s < s ) break;
			t1 += (p[k]^p[j]), sx = (sx + p[k].x) % MOD, sy = (sy + p[k].y) % MOD;
			t2 = (t2 + t1%MOD) % MOD, cnt++, j = k;
		}
		
		ans = (ans - 2LL*t2%MOD)%MOD; // ans -= 2*t2;
		ans = (ans - 2*(p[i].x*sy - p[i].y*sx)%MOD)%MOD; // ans -= 2*(p[i].x*sy - p[i].y*sx);
		ans = (ans + (cnt-2)*(S%MOD)%MOD)%MOD; // ans += (cnt-2)*S;
		
		t1 -= (p[nxt(i)]^p[i]), sx = (sx - p[i].x) % MOD, sy = (sy - p[i].y) % MOD;
		t2 = (t2 - (cnt-1)*((p[nxt(i)]^p[i])%MOD)%MOD)%MOD, cnt--;
	}
	printf("%d
", (ans + MOD) % MOD);
}

codeforces - 1278F：可以考虑每个可能性的概率乘贡献，然后斯特林反演；也可以直接展开 E(X^k)=E((x1+x2+...+xn)^k)，考虑每一项的贡献。最后推出 (ans = sum_{p=0}^{k} frac{{krace p} imes p! imes {nchoose p}}{m^p})。

#include <cstdio>

const int MOD = 998244353;
const int MAXN = 5000;

int pow_mod(int b, int p) {
	int ret = 1;
	for(int i=p;i;i>>=1,b=1LL*b*b%MOD)
		if( i & 1 ) ret = 1LL*ret*b%MOD;
	return ret;
}

int s[MAXN + 5][MAXN + 5], c[MAXN + 5], fct[MAXN + 5], ipwm[MAXN + 5];

int n, m, k;
void init() {
	int im = pow_mod(m, MOD - 2);
	ipwm[0] = fct[0] = s[0][0] = c[0] = 1;
	for(int i=1;i<=k;i++) {
		ipwm[i] = 1LL*ipwm[i-1]*im%MOD;
		c[i] = 1LL*c[i-1]*(n-i+1)%MOD*pow_mod(i, MOD-2)%MOD;
		fct[i] = 1LL*fct[i-1]*i%MOD;
		for(int j=1;j<=k;j++)
			s[i][j] = (s[i-1][j-1] + 1LL*j*s[i-1][j]%MOD)%MOD;
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k), init();
	int ans = 0;
	for(int i=0;i<=k;i++)
		ans = (ans + 1LL*s[k][i]*fct[i]%MOD*c[i]%MOD*ipwm[i]%MOD)%MOD;
	printf("%d
", ans);
}

atcoder - ARC093E：最终要么是最小生成树（最小生成树不涂成相同颜色），要么是最小生成树换掉一条边（最小生成树涂成相同颜色）。然后随便做。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1000;
const int MAXM = 2000;
const int MOD = int(1E9) + 7;

int pw2[MAXM + 5];
void init() {
	pw2[0] = 1;
	for(int i=1;i<=MAXM;i++)
		pw2[i] = 2LL*pw2[i-1]%MOD;
}

struct edge{
	int u, v; ll w;
	friend bool operator < (const edge &a, const edge &b) {
		return a.w < b.w;
	}
}e[MAXM + 5], t[MAXM + 5];

ll G[MAXN + 5][MAXN + 5];

int fa[MAXN + 5];
vector<int>v[MAXN + 5];
int find(int x) {
	return (x == fa[x] ? x : find(fa[x]));
}
bool merge(int x, int y, ll w) {
	if( find(x) == find(y) ) return false;
	x = find(x), y = find(y);
	if( v[x].size() > v[y].size() ) swap(x, y);
	for(int i=0;i<v[x].size();i++)
		for(int j=0;j<v[y].size();j++)
			G[v[x][i]][v[y][j]] = G[v[y][j]][v[x][i]] = w;
	fa[x] = y;
	for(int i=0;i<v[x].size();i++)
		v[y].push_back(v[x][i]);
	return true;
}

int main() {
	init();
	int N, M; ll X;
	scanf("%d%d%lld", &N, &M, &X);
	for(int i=1;i<=M;i++)
		scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].w);
	sort(e + 1, e + M + 1);
	for(int i=1;i<=N;i++) fa[i] = i, v[i].push_back(i);
	ll A = 0; int cnt = 0;
	for(int i=1;i<=M;i++) {
		if( !merge(e[i].u, e[i].v, e[i].w) )
			t[++cnt] = e[i], t[cnt].w -= G[e[i].u][e[i].v];
		else A += e[i].w;
	}
	int ans = 0;
	if( A == X ) ans = (pw2[M] + MOD - pw2[M-N+1+1]) % MOD;
	sort(t + 1, t + cnt + 1);
	for(int i=1;i<=cnt;i++)
		if( A + t[i].w == X ) ans = (ans + pw2[cnt-i+1]) % MOD;
	printf("%d
", ans);
}

atcoder - ARC103D：如果存在两个点 X+Y 奇偶性不同则无解。否则，我们可以构造 {1, 2, 4, ...} （如果 X+Y 为偶数则多一个 1），每次走第 2^i 步时，总是保证 X,Y 一个模 2^(i+2) 为 0，一个模 2^(i+2) 为 2^(i+1) 即可。这样到最后一步 X,Y 一定一个为 0，一个为 2^m，直接走即可。

#include <cstdio>

typedef long long ll;

const int MAXN = 1000;

ll X[MAXN + 5], Y[MAXN + 5]; int N;

ll abs(ll x) {
	return x >= 0 ? x : -x;
}

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++)
		scanf("%lld%lld", &X[i], &Y[i]);
	int type = ((X[1] + Y[1]) & 1);
	for(int i=1;i<=N;i++) {
		if( type != ((X[i] + Y[i]) & 1) ) {
			type = -1;
			break;
		}
	}
	if( type == -1 ) {
		puts("-1");
		return 0;
	}
	else if( type == 0 ) {
		printf("%d
%d", 40, 1);
		for(int i=0;i<39;i++)
			printf(" %lld", (1LL<<i));
		puts("");
		for(int i=1;i<=N;i++) {
			putchar('L'), X[i]++;
			for(int j=0;j<38;j++) {
				ll t1 = (1LL << j), t2 = (1LL << (j + 1)), t3 = (1LL << (j + 2));
				if( abs(X[i] % t2) == t1 ) {
					if( abs(Y[i] % t3) + abs((X[i] + t1) % t3) == t2 )
						putchar('L'), X[i] += t1;
					else putchar('R'), X[i] -= t1;
				}
				else {
					if( abs(X[i] % t3) + abs((Y[i] + t1) % t3) == t2 )
						putchar('D'), Y[i] += t1;
					else putchar('U'), Y[i] -= t1;
				}
			}
			ll t1 = (1LL << 38), t2 = (1LL << 39), t3 = (1LL << 40);
			if( abs(X[i] % t2) == t1 ) {
				if( abs(Y[i] % t3) + abs((X[i] + t1) % t3) == t2 )
					puts("R"), X[i] -= t1;
				else puts("L"), X[i] += t1;
			}
			else {
				if( abs(X[i] % t3) + abs((Y[i] + t1) % t3) == t2 )
					puts("U"), Y[i] -= t1;
				else puts("D"), Y[i] += t1;
			}
		}
	}
	else {
		printf("%d
", 40);
		for(int i=0;i<40;i++)
			printf("%lld ", (1LL<<i));
		puts("");
		for(int i=1;i<=N;i++) {
			for(int j=0;j<39;j++) {
				ll t1 = (1LL << j), t2 = (1LL << (j + 1)), t3 = (1LL << (j + 2));
				if( abs(X[i] % t2) == t1 ) {
					if( abs(Y[i] % t3) + abs((X[i] + t1) % t3) == t2 )
						putchar('L'), X[i] += t1;
					else putchar('R'), X[i] -= t1;
				}
				else {
					if( abs(X[i] % t3) + abs((Y[i] + t1) % t3) == t2 )
						putchar('D'), Y[i] += t1;
					else putchar('U'), Y[i] -= t1;
				}
			}
			ll t1 = (1LL << 39), t2 = (1LL << 40), t3 = (1LL << 41);
			if( abs(X[i] % t2) == t1 ) {
				if( abs(Y[i] % t3) + abs((X[i] + t1) % t3) == t2 )
					puts("R"), X[i] -= t1;
				else puts("L"), X[i] += t1;
			}
			else {
				if( abs(X[i] % t3) + abs((Y[i] + t1) % t3) == t2 )
					puts("U"), Y[i] -= t1;
				else puts("D"), Y[i] += t1;
			}
		}
	}
}

bzoj - 4878：我们可以通过取一个点相邻的已被染色的点的颜色集合的 mex 进行图染色，则颜色 i 的点必然连向颜色 0~i-1 的点。假如最大颜色 >= k，则必然存在一条 0~k-1 的路径，直接输出这个路径；否则输出染色方案。

#include <set>
#include <cstdio>
using namespace std;

const int MAXN = 1000;
const int MAXM = 10000;

struct edge{
	edge *nxt; int to;
}edges[2*MAXM + 5], *adj[MAXN + 5], *ecnt;
void addedge(int u, int v) {
	edge *p = (++ecnt);
	p->to = v, p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->nxt = adj[v], adj[v] = p;
}

set<int>st;
int tg[MAXN + 5], pre[MAXN + 5], clr[MAXN + 5];
bool flag; int n, m, k;
void clear() {
	flag = true, ecnt = edges;
	for(int i=1;i<=n;i++)
		clr[i] = -1, adj[i] = NULL;
	st.clear();
	for(int i=0;i<k;i++)
		st.insert(i), tg[i] = -1;
}
void print(int x) {
	if( clr[x] == 0 ) {
		printf("path");
	}
	else print(pre[x]);
	printf(" %d", x);
}
void dfs(int x) {
	for(edge *p=adj[x];p;p=p->nxt)
		if( clr[p->to] != -1 ) st.erase(clr[p->to]), tg[clr[p->to]] = p->to;
	if( !st.size() ) {
		flag = false;
		clr[x] = k, pre[x] = tg[clr[x]-1];
		print(x), puts("");
		return ;
	}
	else clr[x] = *st.begin(), pre[x] = tg[clr[x]-1];
	for(edge *p=adj[x];p;p=p->nxt)
		if( clr[p->to] != -1 ) st.insert(clr[p->to]), tg[clr[p->to]] = -1;
	for(edge *p=adj[x];p;p=p->nxt)
		if( clr[p->to] == -1 ) {
			dfs(p->to);
			if( !flag ) return ;
		}
}
void solve() {
	scanf("%d%d%d", &n, &m, &k), clear();
	for(int i=1;i<=m;i++) {
		int a, b; scanf("%d%d", &a, &b);
		addedge(a, b);
	}
	for(int i=1;i<=n;i++)
		if( clr[i] == -1 ) {
			dfs(i);
			if( !flag ) return ;
		}
	if( flag ) {
		printf("color");
		for(int i=1;i<=n;i++)
			printf(" %d", clr[i] + 1);
		puts("");
	}
}

int main() {
	int T; scanf("%d", &T);
	while( T-- ) solve();
}

atcoder - ARC080F：可以先差分，区间翻转变为两点翻转。两个相距为奇素数的点一起翻转代价为 1，相距为偶数代价为 2，否则代价为 3（哥德巴赫猜想）。因此将点按奇偶分类，相距奇素数的先跑二分图匹配，剩下的奇偶内部匹配，实在不行补一个代价为 3 的匹配。

#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = int(1E7) + 5;
const int MAXM = 100;

bool nprm[MAXN + 5];
int prm[MAXN + 5], pcnt;
void init() {
	nprm[1] = true;
	for(int i=2;i<=MAXN;i++) {
		if( !nprm[i] ) prm[++pcnt] = i;
		for(int j=1;prm[j]<=MAXN/i;j++) {
			nprm[i*prm[j]] = true;
			if( i % prm[j] == 0 ) break;
		}
	}
}

int a[MAXN + 5], b[2][MAXM + 5], cnt[2];

int G[MAXM + 5][MAXM + 5], lnk[MAXM + 5];
bool vis[MAXM + 5];
bool dfs(int x) {
	for(int i=1;i<=cnt[1];i++) {
		if( !vis[i] && G[x][i] ) {
			vis[i] = true;
			if( !lnk[i] || dfs(lnk[i]) ) {
				lnk[i] = x;
				return true;
			}
		}
	}
	return false;
}

int abs(int x) {return x >= 0 ? x : -x;}
int main() {
	init();
	int N; scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int x; scanf("%d", &x);
		a[x] = 1;
	}
	for(int i=1;i<=MAXN;i++)
		if( a[i] != a[i-1] ) b[i%2][++cnt[i%2]] = i;
	int ans = 0;
	for(int i=1;i<=cnt[0];i++)
		for(int j=1;j<=cnt[1];j++)
			G[i][j] = (!nprm[abs(b[0][i] - b[1][j])]);
	for(int i=1;i<=cnt[0];i++) {
		for(int j=1;j<=cnt[1];j++) vis[j] = false;
		if( dfs(i) ) ans++;
	}
	ans += (cnt[0] - ans)/2*2 + (cnt[1] - ans)/2*2;
	if( (cnt[0] - ans) & 1 ) ans += 3;
	printf("%d
", ans);
}

topcoder - SRM553D1L3：考虑如果已知环长 c，可以根据前缀和建出差分约束。对于合法的 c，首先最大前缀和 < c（因此建最长路求最小值），其次不能有正环。因为简单路径/环的长度为 O(n)，所以考虑对于每个 k，求权值形如 k*c + b 的最长路径/环，解不等式得 c 的范围。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

const ll INF = (1LL << 60);

class YamanoteLine{
	private:
		ll G[101][50][50]; int n;
		void init() {
			for(int i=-n;i<=n;i++)
				for(int j=0;j<n;j++)
					for(int k=0;k<n;k++)
						G[i+n][j][k] = (j == k && i == 0 ? 0 : -INF);
		}
		void addedge(int u, int v, ll d, int w) {
			G[w+n][u][v] = max(G[w+n][u][v], d);
//			printf("%d %d : %lld %d
", u, v, d, w);
		}
		void floyd() {
			for(int k=0;k<n;k++)
				for(int p=-n;p<=n;p++)
					for(int q=-n;q<=n;q++) {
						if( -n > p + q || p + q > n ) continue;
						for(int i=0;i<n;i++)
							for(int j=0;j<n;j++)
								G[p+q+n][i][j] = max(G[p+q+n][i][j], G[p+n][i][k] + G[q+n][k][j]);
					}
		}
	public:
		ll howMany(int _n, vi s1, vi t1, vi l1, vi s2, vi t2, vi l2) {
			n = _n; init();
			for(int i=1;i<n;i++)
				addedge(i-1, i, 1, 0);
			for(int i=0;i<(int)s1.size();i++) {
				if( s1[i] < t1[i] )
					addedge(s1[i], t1[i], l1[i], 0);
				else addedge(s1[i], t1[i], l1[i], -1);
			}
			for(int i=0;i<(int)s2.size();i++) {
				if( s2[i] < t2[i] )
					addedge(t2[i], s2[i], -l2[i], 0);
				else addedge(t2[i], s2[i], -l2[i], 1);
			}
			floyd();
			ll lb = -INF, ub = INF;
			for(int k=-n;k<=n;k++) {
				ll b = G[k+n][0][n-1];
				if( k - 1 == 0 ) {
					if( 0 > -b-1 ) return 0;
				}
				else if( k - 1 < 0 )
					lb = max(lb, (ll)ceil(1.0*(-b-1)/(k-1)));
				else if( k - 1 > 0 )
					ub = min(ub, (ll)floor(1.0*(-b-1)/(k-1)));
			}
			for(int p=-n;p<=n;p++)
				for(int q=-n;q<=n;q++)
					for(int i=0;i<n;i++)
						for(int j=0;j<n;j++) {
							int k = p + q; ll b = G[p+n][i][j] + G[q+n][j][i];
							if( k == 0 ) {
								if( 0 > -b )
									return 0;
							}
							else if( k < 0 )
								lb = max(lb, (ll)ceil(-1.0*b/k));
							else if( k > 0 )
								ub = min(ub, (ll)floor(-1.0*b/k));
						}
			if( lb > ub ) return 0;
			else return (ub - lb + 1 >= 1E15) ? -1 : ub - lb + 1;
		}
};

hdu - 5608：杜教筛模板题，不过预处理需要容斥预处理。这个题说明杜教筛对积性函数并非强制要求，积性函数只是方便预处理。

#include <cstdio>

const int MOD = 1E9 + 7;
const int MAXN = 1000000;
const int INV2 = (MOD + 1) / 2;
const int INV6 = (MOD + 1) / 6;

int f[MAXN + 5];

void init() {
	for(int i=1;i<=MAXN;i++)
		f[i] = (1LL*i*i - 3*i + 2) % MOD;
	for(int i=1;i<=MAXN;i++)
		for(int j=2*i;j<=MAXN;j+=i)
			f[j] = (f[j] + MOD - f[i]) % MOD;
	for(int i=1;i<=MAXN;i++)
		f[i] = (f[i-1] + f[i]) % MOD;
}

int get(int n) {
	int ret = 1LL*n*(n+1)%MOD*(2*n%MOD+1)%MOD*INV6%MOD;
	ret = (ret + MOD - 3LL*n*(n+1)/2%MOD) % MOD;
	ret = (ret + 2LL*n%MOD)%MOD;
	return ret;
}

int g[MAXN + 5], N;
int sum(int x) {
	if( x <= MAXN ) return f[x];
	else if( g[N/x] != -1 ) return g[N/x];
	else {
		int ret = get(x);
		for(int i=2;i<=x;i++) {
			int j = x/(x/i);
			ret = (ret + MOD - 1LL*sum(x/i)*(j-i+1)%MOD)%MOD;
			i = j;
		}
		return g[N/x] = ret;
	}
}
void clear() {
	for(int i=1;i<=N;i++) {
		int j = N/(N/i);
		if( j <= MAXN ) g[j] = -1;
		i = j;
	}
}

void solve() {
	scanf("%d", &N), clear();
	printf("%d
", sum(N));
}

int main() {
	init();
	int T; scanf("%d", &T);
	while( T-- ) solve();
}

codeforces - 588F：二分答案 + 2-sat 判定，优化一下建图。

#include <map>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50000;
const int MAXV = 6*MAXN;
const int MAXE = 20*MAXN;

struct Graph{
	struct edge{
		int to; edge *nxt;
	}edges[MAXE + 5], *adj[MAXV + 5], *ecnt;
	Graph() {ecnt = edges;}
	void addedge(int u, int v) {
		edge *p = (++ecnt);
		p->to = v, p->nxt = adj[u], adj[u] = p;
//		printf("! %d %d 	 (%d %d)
", u, v, u/2, v/2);
	}
}G1, G2;

#define ILLEGAL puts("No"), exit(0)
#define rep(G, x) for(Graph::edge *p=G.adj[x];p;p=p->nxt)

int n, m, cnt;
struct edge{
	int u, v, c, t, id; edge() {}
	edge(int _u, int _v, int _c, int _t, int _id) : u(_u), v(_v), c(_c), t(_t), id(_id) {}
}e[MAXN + 5];
bool cmp(const edge &a, const edge &b) {return a.t < b.t;}

int dfn[MAXV + 5], low[MAXV + 5], id[MAXV + 5];
int stk[MAXV + 5], tp, dcnt, tot;
void dfs(int x) {
	dfn[x] = low[x] = (++dcnt), stk[++tp] = x;
	rep(G2, x) {
		if( dfn[p->to] ) {
			if( !id[p->to] ) low[x] = min(low[x], dfn[p->to]);
		}
		else dfs(p->to), low[x] = min(low[x], low[p->to]);
	}
	if( low[x] >= dfn[x] ) {
		tot++;
		do {
			id[stk[tp]] = tot;
		}while( stk[tp--] != x );
	}
}

bool check(int x) {
	G2 = G1;
	for(int i=x+1;i<m;i++)
		G2.addedge(e[i].id<<1|1, e[i].id<<1);
	for(int i=0;i<cnt;i++) dfn[i] = low[i] = id[i] = 0;
	dcnt = tot = 0;
	for(int i=0;i<cnt;i++)
		if( !dfn[i] ) dfs(i);
	for(int i=0;i<m;i++) {
//		printf("%d : %2d %2d
", i, id[i<<1], id[i<<1|1]);
		if( id[i<<1] == id[i<<1|1] ) return false;
	}
	return true;
}

vector<int>v1[MAXV + 5];
void dfs2(int x) {
	dfn[x] = low[x] = (++dcnt), stk[++tp] = x;
	rep(G2, x) {
		if( dfn[p->to] ) {
			if( !id[p->to] ) low[x] = min(low[x], dfn[p->to]);
		}
		else dfs2(p->to), low[x] = min(low[x], low[p->to]);
	}
	if( low[x] >= dfn[x] ) {
		tot++;
		do {
			v1[tot].push_back(stk[tp]);
			id[stk[tp]] = tot;
		}while( stk[tp--] != x );
	}
}

bool tag[MAXV + 5]; vector<int>ans;
void print(int x) {
	G2 = G1;
	for(int i=x+1;i<m;i++)
		G2.addedge(e[i].id<<1|1, e[i].id<<1);
	for(int i=0;i<cnt;i++) dfn[i] = low[i] = id[i] = 0;
	dcnt = tot = 0;
	for(int i=0;i<cnt;i++)
		if( !dfn[i] ) dfs2(i);
	for(int i=1;i<=tot;i++) {
		for(int j=0;j<(int)v1[i].size();j++) {
			int x = v1[i][j];
			rep(G2, x)
				if( tag[id[p->to]] ) tag[i] = true;
		}
		if( !tag[i] ) {
			for(int j=0;j<(int)v1[i].size();j++)
				if( v1[i][j] < 2*m ) tag[id[v1[i][j]^1]] = true;
		}
	}
	for(int i=0;i<m;i++) {
		if( tag[id[i<<1]] ) ans.push_back(i + 1);
//		printf("%d : %d %d
", i, tag[id[i<<1]], tag[id[i<<1|1]]);
	}
	printf("%d
", ans.size());
	for(int i=0;i<(int)ans.size();i++)
		printf("%d ", ans[i]);
}

map<int, int>mp;
vector<edge>vec[MAXN + 5];

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;i++) {
		int u, v, c, t; scanf("%d%d%d%d", &u, &v, &c, &t);
		e[i] = edge(u, v, c, t, i);
		vec[u].push_back(e[i]), vec[v].push_back(e[i]);
	}
	cnt = 2*m;
	for(int i=1;i<=n;i++) {
		bool flag = false; mp.clear();
		for(int j=0;j<(int)vec[i].size();j++) {
			if( mp.count(vec[i][j].c) ) {
				if( flag ) ILLEGAL;
				else flag = true;
				int x = vec[i][j].id, y = mp[vec[i][j].c];
				G1.addedge(x<<1, y<<1|1), G1.addedge(y<<1, x<<1|1);
			}
			else mp[vec[i][j].c] = vec[i][j].id;
		}
		if( vec[i].size() >= 2 ) {
			int lst = (vec[i][0].id<<1);
			for(int j=1;j<(int)vec[i].size();j++) {
				int x = vec[i][j].id;
				G1.addedge(x<<1|1, lst);
				if( j + 1 == (int)vec[i].size() ) break;
				G1.addedge(cnt, x<<1), G1.addedge(cnt, lst);
				lst = cnt, cnt++;
			}
			lst = (vec[i][vec[i].size() - 1].id<<1);
			for(int j=(int)vec[i].size()-2;j>=0;j--) {
				int x = vec[i][j].id;
				G1.addedge(x<<1|1, lst);
				if( j == 0 ) break;
				G1.addedge(cnt, x<<1), G1.addedge(cnt, lst);
				lst = cnt, cnt++;
			}
		}
	}
	sort(e, e + m, cmp);
	if( !check(m - 1) ) ILLEGAL;
	else puts("Yes");
	int le = -1, ri = m - 1;
	while( le < ri ) {
		int mid = (le + ri) >> 1;
		if( check(mid) ) ri = mid;
		else le = mid + 1;
	}
	printf("%d ", le == -1 ? 0 : e[le].t), print(le);
}