【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;
}

【Codeforces 176E】Wizards and Bets

相关链接

题目传送门:http://codeforces.com/problemset/problem/167/E
神犇题解:http://blog.csdn.net/popoqqq/article/details/45046545

吐槽

神™套路题,考试考这个也是简直了
出题人你能不能良心一点 (╯‵□′)╯︵┻━┻

还有一个高一神犇各种瞎搞给做出来了……
牛逼!我就服你!

解题报告

我们可以把给的出发点到目标点配对之后重新标号
于是我们可以看成是一个置换
然后我们考虑在每一个交叉的位置交换那两条路径的目标点
于是这个方案的置换奇偶性一定改变

然后我们考虑如果一套路径方案交叉了奇数次,那么这是一个奇置换,算行列式时系数为$-1$
如果一套路径的方案交叉了偶数次,那么这是一个偶置换,算行列式的时候系数为$1$
这刚好和容斥的系数对上!于是我们算出行列式就相当于用容斥算出了答案

现在回到行列式的定义:$|A|= \sum\limits_{\sigma\in Sn}{{\mathop{\rm sgn}}(\sigma)\prod\limits_{i= 1}^n{{a_{i,\sigma(i)}}}}$
系数已经没有问题了,那么看方案数的统计,我们发现设$f_{i,j}$为$i \to j$的方案数
放到矩阵的对应位置上,刚好又能对上方案数,于是什么都对上了,这题算个行列式就完了

【Codeforces 757E】Bash Plays with Functions

相关链接

题目传送门:http://codeforces.com/problemset/problem/757/E
官方题解:http://codeforces.com/blog/entry/49743

解题报告

这题窝萌需要打很多的表来发现以下规律:

Ⅰ. 设$x$的素因子种类数为$g(x)$那么$f_0(x)$等于$2^{g(x)}$
Ⅱ. 由规律Ⅰ可得,$f_0(x)$为积性函数,又$f_i(x)=f_{i-1} * 1(x)$,于是我们可用归纳证明得$f_i(x)$均为积性函数
Ⅲ. 设$p$为素数,$f_r(p^k)$与$p$无关,且满足递推式:$f_r(p^k)=\sum\limits_{i=0}^{k}{f_{r-1}(p^i)}$

于是我们预处理出$f_r(p^k)$
对于每次询问,使用积性函数的性质,拆成很多质因数的幂次来做可以辣!
时间复杂度:$O((q+r) \log n)$

Code

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

const int N = 1000009;
const int MOD = 1000000007;

int tot,vis[N],pri[N],sur[N],g[N][21];

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;
}

inline void prework() {
	for (int i=2;i<N;i++) {
		if (!vis[i]) pri[++tot] = i, sur[i] = i;
		for (int j=1;j<=tot&&i*pri[j]<N;j++) {
			vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
			if (i % pri[j] == 0) break;
		}
	}	
	g[0][0] = 1;
	for (int i=1;i<=20;i++) g[0][i] = 2;
	for (int i=1;i<N;i++) {
		for (int j=0;j<=20;j++) {
			g[i][j] = ((j? g[i][j-1]: 0) + g[i-1][j]) % MOD;
		}
	}
}	

inline int solve(int a, int b) {
	int ret = 1;
	for (int cnt=0,p=sur[b];b>1;cnt=0,p=sur[b]) {
		while (b % p == 0) b /= p, cnt++;
		ret = (LL)ret * g[a][cnt] % MOD;
	}
	return ret;
}

int main() { 
	prework();
	for (int T=read(),a,b;T;T--) {
		a = read(); b = read();
		printf("%d\n",solve(a,b));
	}
	return 0;
}

【51NOD 1135】原根

相关链接

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
神犇题解Ⅰ:http://blog.csdn.net/u013486414/article/details/47781857
神犇题解Ⅱ:http://littleclown.github.io/2016/05/16/Study-Math-Mod-Root/

解题报告

就是一个求原根的模板题
相关的证明在这里:http://blog.csdn.net/zhang20072844/article/details/11541133

值得注意的是,验证原根现在可以做到$O(logn)$了
不过找原根的复杂度似乎没有比较紧的上界?
wiki上给出了这样一个上界:$O(n^{0.499})$,但$n$要大于$e^{e^{24}}$,所以对于OI题没什么用QwQ
不过一般来讲,质数的原根都比较小,就直接枚举加验证啦!

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;
}
 
inline int Get_Primitive_Root(int w) {
    vector<int> pri;
    for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
        if (cur % i == 0) {
            pri.push_back(i);
            while (cur % i == 0) 
                cur /= i;
        }
        if (cur > 1 && i == lim - 1) 
            pri.push_back(cur);
    }
    static auto 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;
    };
    if (!pri.size()) return 2;
    for (int i=2;i<=w;i++) {
        for (int j=pri.size()-1;~j;j--) {
            if (Pow(i,w/pri[j],w) == 1) break;
            if (!j) return i;
        }
    }
}
 
int main() {
    printf("%d\n",Get_Primitive_Root(read())); 
    return 0;
}

【POJ 1737】Connected Graph

题目传送门:http://poj.org/problem?id=1737
中文题面:《算法竞赛·入门经典·训练指南》P112

想一想,貌似直接容斥之类的都上不了
于是就不会做了 QAQ
mvr5zj9l7yp

设f(n)为连通图个数,g(n)为不联通的个数,h(n)为总方案数
首先h(n)可以直接算:\(h(n) = {2^{\frac{{n(n – 1)}}{{\rm{2}}}}}\)
又f(n)+g(n)=h(n),所以我们只需要求解g(n)即可

考虑1所在的联通块,假设有i个点,则这部分的方案数就是f(i)
又考虑剩余点对于答案的贡献,因为不一定联通,所以为h(n-i)
所以\(g(n) = \sum\limits_{i = 1}^{n – 1} {f(i) \cdot h(n – i)} \)
于是f(n)用h(n)-g(n)就可以辣!

因为原题要上高精度
所以代码什么的还是算了吧?
_(:з」∠)_

【COGS 741】[网络流24题] 负载平衡

题目传送门:http://cojs.tk/cogs/problem/problem.php?pid=741

虽然是“网络流24题”之一,然而可以O(n)搞
来来来,我们一起来推式子!
6541324587

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

const int N = 100+9;

int n,arr[N],sum,vout,sta;

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;
}

int main(){
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	n = read(); 
	for (int i=1;i<=n;i++) sum += (arr[i] = read()); sum /= n;
	for (int i=1;i<=n;i++) arr[i] -= sum - arr[i-1];
	nth_element(arr+1,arr+n/2,arr+n); sta=arr[n/2];
	for (int i=1;i<=n;i++) vout += abs(arr[i]-sta);
	cout<<vout<<endl;  
	return 0;
} 

感觉真的是好神奇啊!

【Codeforces 711E】ZS and The Birthday Paradox

题目传送门:http://codeforces.com/problemset/problem/711/E
官方题解:http://codeforces.com/blog/entry/46830
中文题面及题解:https://blog.sengxian.com/solutions/cf-711e

这个题重点不在推概率,而在Legendre’s formula
其实难点就是要求在取MOD之前就约分,这个就很麻烦了,只有用上面那个定理

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define pow POW
using namespace std;

const LL MOD = 1000003;

inline LL read(){
	char c=getchar(); LL 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;
}

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

inline bool judge(LL n, LL k) {
	LL w = 1;
	for (int i=1;i<=n;i++) {
		w *= 2;
		if (w >= k) return false;
	} return true;
}

int main(){
	LL n = read(), k = read(), tn = pow(2,n);
	if (judge(n,k)) cout<<1<<' '<<1;
	else {
		LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
		if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
		t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
		cout<<t1<<' '<<t2;
	} 
	return 0;
}

ps:如果不知道上面的那个定理,貌似自己推也是可以推出来的?

【Codeforces 707C】Pythagorean Triples

相关链接

题目传送门:http://codeforces.com/contest/707/problem/C

解题报告

这个题目第一眼看到,一脸懵逼,觉得这个东西一定是爆搜
后来想不出来弃疗了

今天再来看,也是没有思路,但看到了第三组样例,便一下子又了思路
假设我们读入a,考虑a^2+b^2=c^2,移相得a^2=(c+b)*(c-b)
如果a^2为奇数,让c-b=1即可
如果a^2为偶数,让c-b=2即可

Code

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

LL a,b,c;

int main(){
	cin>>a; a *= a;
	if (a <= 4) cout<<-1;
	else if (a & 1) cout<<a/2<<' '<<a/2+1;
	else cout<<a/4+1<<' '<<a/4-1;
	return 0;
} 

【POJ 1284】Primitive Roots

题目传送门:http://poj.org/problem?id=1284

题目大意:给一个素数(>3),求原根的个数。
相关定理:如果一个数a有原根,则个数为\(\varphi (\varphi (a))\\)
定理证明:我不会QAQ,可以参考:wiki中的性质一栏

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

const int MAXN = 100000+9;
const int MX = 70000;

int pri[MAXN],tot,phi[MAXN];
bool tag[MAXN];

inline void Get_Phi(){
	phi[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
		for (int j=1;j<=tot && pri[j]*i <= MX;j++) {
			tag[pri[j]*i] = 1;
			if (i % pri[j]) phi[pri[j]*i] = phi[i]*(pri[j]-1);
			else {phi[pri[j]*i] = phi[i]*pri[j]; break;}
		}
	}
}

int main(){
	Get_Phi(); int a;
	while (~scanf("%d",&a))	printf("%d\n",phi[a-1]);	
	return 0;
} 

我一定不会告诉你:其实我只是来水线性递推欧拉函数的QAQ