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

33281378432849
## 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|$

莫比乌斯反演与容斥原理

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

【BZOJ 4589】Hard Nim

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4589

解题报告

我们考虑用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;
}

【BZOJ 4599】[JLOI2016] 成绩比较

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4559
神犇题解:http://blog.lightning34.cn/?p=286

解题报告

仍然是广义容斥原理
可以推出$\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!

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/

解题报告

设$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

相关链接

题目传送门:http://agc015.contest.atcoder.jp/tasks/agc015_f

解题报告

我们写出使答案最大且值最小的序列,不难发现这是一个斐波那契数列
进一步发现,这条主链的每一个点只会引申出一条支链,且支链不会再分
所以我们可以暴力算出了$\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;
}

【日常小测】航海舰队

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_day1-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_day1-solutions.pdf

解题报告

之前在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

【日常小测】魔术卡

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/20170614-statement.pdf

题目大意

给你$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】上帝与集合的正确用法

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3884
官方题解:http://blog.csdn.net/popoqqq/article/details/43951401

解题报告

根据欧拉定理有:$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;
}

【日常小测】最长路径

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

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

  1. 任意一个竞赛图一定存在哈密尔顿路径
  2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$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

相关链接

题目传送门:http://codeforces.com/contest/749/problem/E
官方题解:http://codeforces.com/blog/entry/49186

解题报告

考虑从期望的定义下手
就是要求所有区间的逆序对的和
于是我们枚举右端点,然后算贡献
用$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

相关链接

题目传送门:http://codeforces.com/contest/812/problem/E
官方题解:http://codeforces.com/blog/entry/52318

解题报告

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

所以结果只与深度同叶子结点奇偶性相同的点有关
更进一步观察发现,实质上就是这些点组成的$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)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf

解题报告

这题告诉我们,这类题可以高斯消元做
裸做是$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

相关链接

题目传送门:http://poj.org/problem?id=3922
神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2012/12/19/2825539.html

解题报告

根据$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

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14595&rd=16883

解题报告

不难发现,这就是统计括号匹配的方案数
不会的同学可以先去切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:
};