数论 – Qizy's Database

一位在退学边缘疯狂试探的学渣为了高代不挂科做出的最终努力

2018年10月24日2018年10月24日 Qizy 46 条评论

## 1. 爪形行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&1& \cdots &1\\
   1&{{x_2}}& \cdots &0\\
    \vdots & \vdots & \ddots &0\\
   1&0&0&{{x_n}}
   \end{array}} \right|$

## 2. 两三角型行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&b& \cdots &b\\
   b&{{x_2}}& \cdots &b\\
    \vdots & \vdots & \ddots &b\\
   b&b&b&{{x_n}}
   \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&b&b& \cdots &b\\
   a&{{x_2}}&b& \cdots &b\\
   a&a&{{x_3}}& \cdots &b\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   a&a&a& \cdots &{{x_n}}
   \end{array}} \right|$
3. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   d&b&b& \cdots &b\\
   c&x&a& \cdots &a\\
   c&a&x& \cdots &a\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   c&a&a& \cdots &x
   \end{array}} \right|$

## 3. 两条线型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {{a_1}}&{{b_1}}&0& \cdots &0\\
  0&{{a_2}}&{{b_2}}& \cdots &0\\
  0&0&{{a_3}}& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  {{b_n}}&0&0& \cdots &{{a_n}}
  \end{array}} \right|$

## 4. 范德蒙德型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n
  \end{array}} \right|$

## 5. Hessenberg型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  1&2&3& \cdots &n\\
  1&{ - 1}&0& \cdots &0\\
  0&2&{ - 2}& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  0&0&0& \cdots &{1 - n}
  \end{array}} \right|$

## 6. 三对角型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  a&b&0& \cdots &0\\
  c&a&b& \cdots &0\\
  0&c&a& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  0&0&0& \cdots &a
  \end{array}} \right|$

## 7. 各行元素和相等型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\
  {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\
  {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}}
  \end{array}} \right|$

## 8. 相邻两行对应元素相差K倍型行列式

1. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   0&1&2& \cdots &{n - 1}\\
   1&0&1& \cdots &{n - 2}\\
   2&1&0& \cdots &{n - 3}\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   {n - 1}&{n - 2}&1& \cdots &0
   \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\
   {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\
   {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   a&{{a^2}}&{{a^3}}& \cdots &1
   \end{array}} \right|$

莫比乌斯反演与容斥原理

2018年2月10日2018年3月16日 Qizy 311 条评论

退役前一直想把莫比乌斯反演与容斥原理统一在一起，奈何自己水平不足，只能作罢。
这次把《组合数学》、《具体数学》、《初等数论》的相关内容读了一遍，总算是完成了这个遗愿：
mobius_and_inclusion_exclusion_principle

Download：https://oi.qizy.tech/wp-content/uploads/2018/03/mobius_and_inclusion_exclusion_principle.pdf
拓展阅读1：http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion
拓展阅读2：http://vfleaking.blog.uoj.ac/blog/87

数论常见结论及其证明

2018年2月9日2018年2月9日 Qizy 12 条评论

conclusion_and_proof_in_number_theory

Download：https://oi.qizy.tech/wp-content/uploads/2018/02/conclusion_and_proof_in_number_theory.pdf

【BZOJ 4589】Hard Nim

2017年7月15日2017年7月21日 Qizy 96 条评论

解题报告

我们考虑用SG函数来暴力DP
显然可以用FWT来优化多项式快速幂
总的时间复杂度：$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009; 
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
	for (int d = 1; d < len; d <<= 1) {
		for (int i = 0; i < len; i += d << 1) {
			for (int j = 0; j < d; j++) {
				int t1 = a[i + j], t2 = a[i + j + d];
				if (opt == 1) {
					a[i + j] = (t1 + t2) % MOD;
					a[i + j + d] = (t1 - t2) % MOD;
				} else {
					a[i + j] = (LL)(t1 + t2) * REV % MOD;
					a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
				}
			}
		}
	}
}

int main() {
	for (int n, m; ~scanf("%d %d", &n, &m); ) {
		memset(arr, 0, sizeof(arr));
		for (int i = 2; i <= m; i++) {
			if (!vis[i]) {
				arr[i] = 1;
				for (int j = i << 1; 0 <= j && j <= m; j += i) {
					vis[j] = 1;
				}
			}
		}
		int len = 1; 
		for (; len <= m; len <<= 1);
		FWT(arr, len);
		for (int i = 0; i < len; i++) {
			arr[i] = Pow(arr[i], n);
		}
		FWT(arr, len, -1);
		printf("%d\n", (arr[0] + MOD) % MOD);
	}
	return 0;
}

仍然是广义容斥原理
可以推出$\alpha(x)={{n-1}\choose{x}} \prod\limits_{i=1}^{m}{{{n-1-x}\choose{R_i-1}}\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}}$
我们发现唯一的瓶颈就是求$f(i)=\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}$
但我们稍加观察不难发现$f(i)$是一个$n$次多项式，于是我们可以用拉格朗日插值来求解
于是总的时间复杂度：$O(mn^2)$

Code

这份代码是$O(mn^2 \log 10^9+7)$的
实现得精细一点就可以把$\log$去掉

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		} 
	}
	return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
	int ret = 0;
	for (int i=1;i<=len;i++) {
		int tmp = ff[i];
		for (int j=1;j<=len;j++) {
			if (i == j) continue;
			tmp = (LL)tmp * (x - xx[j]) % MOD;
			tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
		}
		ret = (ret + tmp) % MOD;
	}
	return (ret + MOD) % MOD;
} 

int main() {
	n = read(); m = read(); K = read();
	for (int i=1;i<=m;i++) {
		u[i] = read();
	}
	for (int i=1;i<=m;i++) {
		r[i] = read();
	}
	//预处理组合数 
	C[0][0] = 1;
	for (int i=1;i<=n;i++) {
		C[i][0] = 1;
		for (int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	//拉格朗日插值
	for (int w=1;w<=m;w++) {
		for (int i=1;i<=n+1;i++) {
			f[i] = 0; h[i] = i;
			for (int j=1;j<=i;j++) {
				f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
			}
		}  
		g[w] = LagrangePolynomial(u[w], n+1, f, h);
	}
	//广义容斥原理 
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		alpha[i] = C[n-1][i];
		for (int j=1;j<=m;j++) {
			alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
		}
		ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【BZOJ 4318】OSU!

2017年7月12日2017年7月12日 Qizy 286 条评论

解题报告

设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾，$($极长$1$的长度$x)^3$的期望
$E_{(i,x^2)}，E_{(i,x)}$分别表示$x^2,x$的期望

那么根据全期望公式，我们有如下结论：

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

不难发现只有第三个式子可以直接算
但我们还知道一个东西叫期望的线性，于是我们可以将前两个式子化为：

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

然后就可以直接维护，然后再根据期望的线性加入答案就可以辣！
时间复杂度：$O(n)$

另外，似乎直接算贡献也可以？
可以参考：http://blog.csdn.net/PoPoQQQ/article/details/49512533

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	int n=read(); 
	double e1=0,e2=0,e3=0,ans=0,p;
	for (int i=1;i<=n;i++) {
		scanf("%lf",&p);
		ans += e3 * (1 - p);
		e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
		e2 = p * (e2 + 2 * e1 + 1);
		e1 = p * (e1 + 1);
	} 
	printf("%.1lf\n",ans+e3);
	return 0;
}

【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

2017年7月3日2017年7月21日 Qizy 34 条评论

解题报告

我们写出使答案最大且值最小的序列，不难发现这是一个斐波那契数列
进一步发现，这条主链的每一个点只会引申出一条支链，且支链不会再分
所以我们可以暴力算出了$\log n$条链，共$\log ^ 2 n$对数，然后暴力算贡献

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int MOD = 1000000007;
const int LOG = 100;
 
vector<pair<LL, LL> > num[LOG];
 
inline LL read() {
	char c = getchar(); LL ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}
 
inline void solve(LL A, LL B) {
	if (A < num[2][0].first || B < num[2][0].second) {
		printf("1 %d\n", A * B % MOD);
		return;
	}
	for (int i = 2; i < LOG; i++) {
		if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
			int cnt = 0;
			for (int j = 0; j < (int)num[i].size(); j++) {
				LL a = num[i][j].first, b = num[i][j].second;
				cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
				cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
			}
			printf("%d %d\n", i, cnt);
			return;
		}
	}
}
 
inline void prework() {
	num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < (int)num[i - 1].size(); ++j) {
			LL a = num[i - 1][j].first, b = num[i - 1][j].second;
			num[i].push_back(make_pair(b, a + b));
		}
		LL a = num[i - 1][0].first, b = num[i - 1][0].second;
		num[i].push_back(make_pair(a + b, 2 * a + b));
	}
}
 
int main() {
	prework();
	for (int T = read(); T; T--) {
		LL A = read(), B = read();
		solve(min(A, B), max(A, B));
	}
	return 0;
}

【日常小测】航海舰队

2017年6月18日2017年7月21日 Qizy 290 条评论

解题报告

之前在BZOJ上看过这道题，然后当时嫌麻烦没有写
今天刚好考到，然后就被细节给搞死了_(:з」∠)_

一句话题解就是：用FFT做矩阵匹配
详细一点的话，大概就是：

先用FFT做一遍0/1矩阵匹配，求出能放阵型的位置
然后BFS出能到达的位置
最后再做一遍FFT求出每个点被覆盖了多少次

Code

#include<bits/stdc++.h>
#define LL long long
#define CP complex<double>
using namespace std;

const int N = 709;
const int M = 5000000;
const double EPS = 0.5;
const double PI = acos(-1);

char mp[N][N];
int n, m, vis[M], sfe[M];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
CP a[M], b[M], c[M];

inline void FFT(CP *arr, int len, int ty) {
	static int pos[M], init = 0;
	if (init != len) {
		for (int i = 1; i < len; ++i) {
			pos[i] = (pos[i >> 1] >> 1) | ((i & 1)? (len >> 1): 0); 
		}
		init = len;
	}
	for (int i = 0; i < len; i++) {
		if (pos[i] < i) {
			swap(arr[i], arr[pos[i]]);
		}
	}
	for (int i = 1; i < len; i <<= 1) {
		CP wn(cos(PI / i), sin(PI / i) * ty);
		for (int j = 0; j < len; j += i + i) {
			CP w(1, 0);
			for (int k = 0; k < i; k++, w *= wn) {
				CP tmp = arr[j + i + k] * w;
				arr[j + i + k] = arr[j + k] - tmp;
				arr[j + k] = arr[j + k] + tmp;
			}
		}
	}
	if (ty == -1) {
		for (int i = 0; i < len; i++) {
			arr[i] /= len;
		}
	}
}

inline void BFS(int sx, int sy, int lx, int ly) {
	vis[sy * n + sx] = 1;
	queue<pair<int, int> > que;
	for (que.push(make_pair(sx, sy)); !que.empty(); que.pop()) {
		int x = que.front().first;
		int y = que.front().second;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx + lx - 1 < n && 0 <= ny && ny + ly - 1 < m && sfe[ny * n + nx] && !vis[ny * n + nx]) {
				que.push(make_pair(nx, ny));
				vis[ny * n + nx] = 1;
			}
		}
	}
} 

int main() {
	freopen("sailing.in", "r", stdin);
	freopen("sailing.out", "w", stdout);
	cin >> m >> n;
	int mnx = n, mny = m, mxx = 0, mxy = 0; 
	for (int j = 0; j < m; j++) {
		scanf("%s", mp[j]);
		for (int i = 0; i < n; i++) {
			if (mp[j][i] == 'o') {
				mnx = min(i, mnx);
				mxx = max(i, mxx);
				mny = min(j, mny);
				mxy = max(j, mxy);
			}
		}
	}
	for (int j = 0; j < m; ++j) {
		for (int i = 0; i < n; ++i) {
			if (mp[j][i] == 'o') {
				b[(j - mny) * n + i - mnx] = CP(1, 0);
			} else if (mp[j][i] == '#') {
				a[j * n + i] = CP(1, 0);
			}
		}
	}
	int cur = n * m, len = 1;
	for (; len < cur * 2; len <<= 1);
	for (int l = 0, r = cur - 1; l < r; ++l, --r) {
		swap(b[l], b[r]);
	}
	FFT(a, len, 1);
	FFT(b, len, 1);
	for (int i = 0; i < len; i++) {
		a[i] *= b[i];
	}
	FFT(a, len, -1);
	for (int i = 0; i < cur; i++) {
		if (a[i + cur - 1].real() < EPS) {
			sfe[i] = 1;
		}
	}
	BFS(mnx, mny, mxx - mnx + 1, mxy - mny + 1); 
	memset(b, 0, sizeof(b));
	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			c[j * n + i] = vis[j * n + i]? CP(1, 0): CP(0, 0);
			b[(j - mny) * n + i - mnx] = mp[j][i] == 'o'? CP(1, 0): CP(0, 0);
		}
	}
	FFT(c, len, 1);
	FFT(b, len, 1);
	for (int i = 0; i < len; i++) {
		c[i] *= b[i];
	}
	FFT(c, len, -1);
	int ans = 0;
	for (int i = 0; i < cur; i++) {
		ans += c[i].real() > EPS; 
	}
	printf("%d\n", ans);
	return 0;
}

—————————— UPD 2017.6.30 ——————————
B站题号：4624

【日常小测】魔术卡

2017年6月14日2017年7月21日 Qizy 214 条评论

题目大意

给你$m(m \le 10^3)$种，第$i$种有$a_i$张，共$n(n = \sum\limits_{i = 1}^{m}{a_i} \le 5000)$张卡
现在把所有卡片排成一排，定义相邻两个卡片颜色相同为一个魔术对
询问恰好有$k$个魔术对的本质不同的排列方式有多少种，对$998244353$取模
定义本质不同为：至少有一位上的颜色不同

解题报告

一看就需要套一个广义容斥原理
于是问题变为求“至少有$x$个魔术对的方案数”

于是我们可以钦定第$i$种卡片组成了$j$个魔术对
然后用一个$O(n^2)$的$DP$来求出至少有$x$个魔术对的方案数

为了方便去重，我们先假设相同颜色的卡片有编号，最后再依次用阶乘除掉
考试的时候就是这里没有处理好，想的是钦定的时候直接去重，但这样块与块之间的重复就搞不了，于是$GG$了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const int MOD = 998244353;

int n, m, K, a[N], pw[N], inv[N], f[N][N], C[N][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

int main() {
	freopen("magic.in", "r", stdin);
	freopen("magic.out", "w", stdout);
	m = read(); n = read(); K = read();
	for (int i = 1; i <= m; i++) {
		a[i] = read();
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
	pw[0] = inv[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		inv[i] = Pow(pw[i], MOD - 2);
	}
	f[0][0] = 1;
	for (int i = 1, pre_sum = 0; i <= m; i++) {
		pre_sum += a[i] - 1;
		for (int j = 0; j <= pre_sum; j++) {
			for (int k = min(a[i] - 1, j); ~k; k--) {
				f[i][j] = (f[i][j] + (LL)f[i - 1][j - k] * C[a[i]][k] % MOD * pw[a[i] - 1] % MOD * inv[a[i] - 1 - k]) % MOD;
			}
		} 
	}
	int ans = 0;
	for (int i = K, ff = 1; i < n; i++, ff *= -1) {
		f[m][i] = (LL)f[m][i] * pw[n - i] % MOD;
		ans = (ans + (LL)ff * C[i][K] * f[m][i]) % MOD;
	}
	for (int i = 1; i <= m; i++) {
		ans = (LL)ans * inv[a[i]] % MOD;
	}
	printf("%d\n", (ans + MOD) % MOD);
	return 0;
}

【BZOJ 3884】上帝与集合的正确用法

2017年6月13日2017年7月21日 Qizy 3 条评论

解题报告

根据欧拉定理有：$a^x \equiv a^{x \% \varphi (p) + \varphi (p)} \mod p$
设$f(p)=2^{2^{2 \cdots }} \mod p$
那么有$f(p) = 2^{f(\varphi(p)) + \varphi(p)} \mod p$

如果$p$是偶数，则$\varphi(p) \le \frac{p}{2}$
如果$p$是奇数，那么$\varphi(p)$一定是偶数
也就是说每进行两次$\varphi$操作，$p$至少除$2$
所以只会递归进行$\log p$次
总时间复杂度：$O(T\sqrt{p} \log p)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline int get_phi(int x) {
	int ret = x;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			ret = ret / i * (i - 1);
			while (x % i == 0) {
				x /= i;
			}
		}
	}
	return x == 1? ret: ret / x * (x - 1);
}

inline int Pow(int w, int t, int MOD) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline int f(int p) {
	if (p == 1) {
		return 0;
	} else {
		int phi = get_phi(p);
		return Pow(2, f(phi) + phi , p);
	}
}

int main() {
	for (int i = read(); i; --i) {
		printf("%d\n", f(read())); 
	}
	return 0;
}

【日常小测】最长路径

2017年6月13日2017年7月21日 Qizy 21 条评论

解题报告

首先我们要熟悉竞赛图的两个结论：

任意一个竞赛图一定存在哈密尔顿路径

一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

现在考虑把强连通分量缩成一个点，并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和

设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$

于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

int main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	n = read(); MOD = read();
	pw[0] = 1;
	for (int i = 1; i < n * n; i++) {
		pw[i] = (pw[i - 1] << 1) % MOD;
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	f[0] = g[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = g[i] = pw[i * (i - 1) >> 1];
		for (int j = 1; j < i; j++) {
			g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
		}
	}
	for (int x = 1; x <= n; x++) {
		int ans = 0;
		for (int i = 1; i <= x; i++) {
			ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
		}
		printf("%d\n", ans > 0? ans: ans + MOD);
	}
	return 0;
}

【Codeforces 749E】Inversions After Shuffle

2017年6月11日2017年7月21日 Qizy 26 条评论

解题报告

考虑从期望的定义下手
就是要求所有区间的逆序对的和
于是我们枚举右端点，然后算贡献
用$BIT$来维护，时间复杂度：$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 100009;

int n, p[N]; 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Fenwick_Tree{
	double sum[N];
	public:
		inline void init() {
			memset(sum, 0, sizeof(sum));
		}
		inline void modify(int p, int d = 1) {
			for (int i = p; i <= n; i += lowbit(i)) {
				sum[i] += d;
			}
		}
		inline double query(int p) {
			double ret = 0;
			for (int i = p; i; i -= lowbit(i)) {
				ret += sum[i];
			}
			return ret;
		}
}BIT;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	double ans = 0, psm = 0;
	for (int i = n; i; i--) {
		ans += BIT.query(p[i]);
		BIT.modify(p[i]);	
	}	
	ans *= n * (n + 1ll);
	BIT.init();
	for (int i = 1; i <= n; i++) {
		LL t1 = BIT.query(p[i]);
		LL t2 = i * (i - 1ll) / 2 - t1;
		ans += (psm += t1 - t2);
		BIT.modify(p[i], i);
	}
	printf("%.15lf\n", ans / n / (n + 1));
	return 0;
}

【Codeforces 812E】Sagheer and Apple Tree

2017年6月2日2017年6月2日 Qizy 15 条评论

解题报告

我们发现，如果操作同叶子结点的深度奇偶性不同的结点
那么对手总可以操作刚刚你操作的那些苹果

所以结果只与深度同叶子结点奇偶性相同的点有关
更进一步观察发现，实质上就是这些点组成的$NIM$游戏
于是乘一乘、加一加就好了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 10000009;

int n, prt, tot, dep[N], v[N], in[N];
int head[N], nxt[N], to[N], cnt[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1; in[v]++; in[u]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

void DFS(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		dep[to[i]] = dep[w] + 1;
		DFS(to[i]);
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i <= n; i++) {
		v[i] = read();
	}
	for (int i = 2; i <= n; i++) {
		AddEdge(read(), i);
	}
	DFS(1);
	for (int i = 2; i <= n; ++i) {
		if (in[i] == 1) {
			prt = (dep[i] & 1);
			break;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			ans ^= v[i];
		}
	}
	LL vout = 0;
	tot = n;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			cnt[v[i]]++;
			--tot;
		}
	}
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) != prt) {
			int tt = ans ^ v[i];
			if (tt < M) {
				vout += cnt[tt];
			}
		}
	}
	if (!ans) {
		vout += tot * (tot - 1ll) / 2;
		vout += (n - tot) * (n - tot - 1ll) / 2;
	}
	cout<<vout<<endl;
	return 0;
}

【Codeforces 802L】Send the Fool Further! (hard)

2017年6月1日2017年7月21日 Qizy 212 条评论

解题报告

这题告诉我们，这类题可以高斯消元做
裸做是$O(n^3)$的，非常不科学
这题我们发掘性质，如果从叶子开始一层一层往上消，高斯消元那一块可以做到$O(n)$
然后再算上逆元的话，总的时间复杂度：$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 200009;
const int MOD = 1000000007;

int n, head[N], nxt[M], to[M], cost[M];
int a[N], b[N], fa[N], d[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v, int c) {
	static int E = 1; 
	d[u]++; d[v]++;
	cost[E + 1] = cost[E + 2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int REV(int x) {
	int ret = 1, t = MOD - 2;
	for (; t; x = (LL)x * x % MOD, t >>= 1) {
		if (t & 1) {
			ret = (LL)ret * x % MOD;
		}
	}
	return ret;
}

void solve(int w, int f) {
	if (d[w] > 1) {
		a[w] = -1;
		for (int i = head[w]; i; i = nxt[i]) {
			b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD;
			if (to[i] != f) {
				solve(to[i], w);
			}
		}
		if (w != f) {
			b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD;
			a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD;
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		AddEdge(u + 1, v + 1, read());
	}
	solve(1, 1);
	int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
	ans = (ans + MOD) % MOD;
	cout<<ans<<endl;
	return 0;
}

【POJ 3922】A simple stone game

2017年5月26日2017年5月26日 Qizy 2 条评论

解题报告

根据$k = 1$的情况，我们发现在二进制下，我们取走最低位的$1$，对手取不走较高位的$1$
所以如果不是二的整次幂，那么先手必胜

再来看看$k = 2$的情况
根据$HINT$我们把每个整数拆成若干个不同、不相邻的斐波那契数之和，表示成二进制状态
之后跟据$k = 1$时的推论，我们取走最低位的$1$，对手不能直接取走较高位的$1$

先在我们看我们依赖拆分数列的哪些性质：

存在一种拆分使得选中的项的任意相邻两项超过$k$倍

于是我们尝试构造拆分数列$a_i$
我们设$b_i$为$a_1 \to a_i$能拼出的极长的前缀长度
不难发现$a_i = b_{i-1}+1, b_i=a_i+b_j$，其中$j$尽可能大，且$a_j k < a_i$

于是这题就做完啦
似乎这个问题还是博弈论里的一个经典问题，叫”$k$倍动态减法问题”
似乎某年国家集训队论文里还提出了另外的算法，对于某些数据会更优

Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int t = 1, T = read(); t <= T; ++t) {
		n = read(); k = read();
		a[0] = b[0] = x = y = 0;
		while (a[x] < n) {
			a[x + 1] = b[x] + 1;
			for (++x; (LL)a[y + 1] * k < a[x]; ++y);
			b[x] = y? b[y] + a[x]: a[x];
		}
		if (a[x] == n) {
			printf("Case %d: lose\n", t);
		} else {
			int ans = 0;
			for (; n && x; --x) {
				if (n >= a[x]) {
					n -= a[x];
					ans = a[x];
				}
			}
			printf("Case %d: %d\n", t, ans);
		}
	}
	return 0;
}

【TopCoder SRM714】ParenthesisRemoval

2017年5月24日2017年5月24日 Qizy 22 条评论

解题报告

不难发现，这就是统计括号匹配的方案数
不会的同学可以先去切BZOJ 3622

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3000;
const int MOD = 1000000007;

int n,ans;
char s[N]; 

class ParenthesisRemoval {
    public:
    	int countWays(string ss) {
			n = ss.size();
    		for (int i=0;i<ss.size();i++) {
				s[i] = ss[i];
			}
			ans = 1;
			for (int i=0,pfx=0;i<n;i++) {
				if (s[i] == '(') {
					++pfx;
				} else {
					ans = (LL)ans * (pfx--) % MOD;
				}
			}
    	    return ans;
   		}
   	private:
};

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

题目大意

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code