【Codeforces 800C】Vulnerable Kerbals

相关链接

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

解题报告

写一写发现前缀积与$m$的$\gcd$是一个递增的关系,依次为倍数
于是我们将$0 \sim m-1$按照与$m$的$\gcd$分类
然后就是在拓扑图上搞一搞$DP$,输出的时候用拓展欧几里得求一发逆元
总的时间复杂度:$O(n \log n)$

Code

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

const int N = 5000000;
const int M = 10000;

int n,m,tot,ans,vis[N],id[N],in[M],num[M];
int head[M],nxt[N],to[N],f[M],itr[M];
vector<int> que[M],vout;

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 gcd(int a, int b) {
	return b? gcd(b, a%b): a;
}

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

void solve(int w) { 
	f[w] = que[w].size() + (itr[w]?f[itr[w]]:0);
	ans = max(ans, f[w]); 
	for (int i=head[w];i;i=nxt[i]) {
		if (f[w] > f[itr[to[i]]]) itr[to[i]] = w;
		if (--in[to[i]] == 0) solve(to[i]);
	}
}

void exgcd(int a, int b, LL &x, LL &y) {
	if (b) {exgcd(b, a%b, y, x); y -= a / b * x;}
	else {x = 1; y = 0;}
}

inline int REV(int a, int z) {
	int tmp = gcd(a, m), b; LL x, y; 
	a /= tmp; z /= tmp; b = m / tmp;
	exgcd(a, b, x, y);
	return x * z % m;
}

void print(int w, int v) {
	for (int i=0;i<=que[w].size()-1;i++) {
		int nv = que[w][i], rev = REV(v, nv);
		vout.push_back((rev+m)%m); v = nv;
	}
	if (itr[w]) print(itr[w], v);
}

int main() {
	n = read(); m = read();
	for (int i=1;i<=n;i++) vis[read()] = 1;
	for (int i=1;i<m;i++) if (!vis[i]) {
		int tmp = gcd(m, i); 
		if (!id[tmp]) id[tmp] = ++tot, num[tot] = tmp;
		que[id[tmp]].push_back(i);
	}
	for (int i=1;i<=tot;i++) {
		for (int j=1;j<=tot;j++) {
			if (num[j] > num[i] && num[j] % num[i] == 0) {
				AddEdge(i, j); 
			}
		}
	}
	for (int i=1;i<=tot;i++) if (!in[i]) solve(i);
	for (int i=1;i<=tot;i++) if (f[i] == ans) {print(i, 1); break;}
	if (!vis[0]) vout.push_back(0); cout<<vout.size()<<endl;
	for (int i=0;i<=vout.size()-1;i++) printf("%d ",vout[i]); 
	return 0;
}

【Codeforces 715C】Digit Tree

相关链接

题目传送门:http://codeforces.com/problemset/problem/715/C
官方题解:http://codeforces.com/blog/entry/47169

解题报告

要求统计树上路径,那么基本上确定是DP或者树分治了
想一想,好像DP的状态不好表示的样子,于是就直接点分治啦!

考虑对于每一个中心,统计经过该点符合要求的路径数
很明显需要将路径剖成两半,一半扔到map里,另一半直接查

但这题还有需要注意的就是如何去掉两段都在同一子树的非法情况
似乎直接像之前一样在子树的根部调用cal()直接剪掉的方法不管用了
于是可以先DFS一遍,统计所有信息
然后再处理每一个子树的时候,先DFS一遍,把该子树的信息给去掉
查询完成之后,再DFS一遍把信息给加回去

Code

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

const int N = 200000 + 9;

int head[N],nxt[N],cost[N],to[N],REV[N];
int n,MOD; LL vout;

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 Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w; 
}

void gcd(int a, LL &x, int b, LL &y) {
	if (!b) {x = 1, y = 0;}
	else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
	static LL x,y;
	gcd(a,x,b,y);
	return (x % MOD + MOD) % MOD;
} 

namespace Node_Decomposition{
	#define ND Node_Decomposition
	const int INF = 1e9;
	int tot,node_sz,root,cur;
	int sum[N],dep[N],vis[N];
	map<int,int> cnt;
	
	void Get_Root(int w, int f) {
		sum[w] = 1; int mx = 0;
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				Get_Root(to[i], w);
				sum[w] += sum[to[i]];
				mx = max(mx, sum[to[i]]);
			}
		}
		mx = max(mx, node_sz - sum[w]);
		if (mx < cur) cur = mx, root = w;
	}
	
	void DFS(int w, int f, int delta, LL p, int val) {
		cnt[val] += delta; 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
			}
		}
	}
	
	void cal(int w, int f, int t, LL val) {
		vout += cnt[(-val*REV[t]%MOD+MOD)%MOD]; 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
			}
		}
	}
	
	void solve(int w, int sz) {
		vis[w] = 1; cnt.clear(); 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
			}
		}
		vout += cnt[0]; cnt[0]++;
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
				cal(to[i], w, 1, cost[i] % MOD);
				DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
			}
		}
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
				cur = INF; Get_Root(to[i], w);
				solve(root, node_sz);
			}
		}
	}
	
	inline void solve() {
		cur = INF; node_sz = n;
		Get_Root(1,1);
		solve(root,n);
	}
};

int main() {
	n = read(); MOD = read();
	for (int i=1,u,v,w;i<n;i++) {
		u = read(); v = read(); w = read();
		Add_Edge(u + 1, v + 1, w);
	}
	REV[0] = 1; REV[1] = gcd(10, MOD);
	for (int i=2;i<=n;i++)
		REV[i] = (LL)REV[i-1] * REV[1] % MOD;
	ND::solve();
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 4522】[Cqoi2016] 密钥破解

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4522
数据生成器:http://paste.ubuntu.com/23140343/

这题,我觉得唯一的难点在分解因数
因为忘了棒棒糖怎么写,于是考试的时候只能写了50分的暴力
话说CQOI怎么能考模板呢?YLUL)A7V{OMTL8]~RL2VL$8

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

LL e,N,c,r,d,n; 

void EX_GCD(LL &x, LL a, LL &y, LL b) {
	if (!b) {x = 1; y = 0;}
	else {EX_GCD(y,b,x,a%b); y -= a/b*x;}
}

inline LL EX_GCD(LL a, LL b) {
	LL t1, t2;
	EX_GCD(t1,a,t2,b);
	return (t1%r + r) % r;
}

inline LL Mul(LL a, LL b) {
	LL ret = 0;
	while (b) {
		if (b&1) ret  = (ret + a) % N;
		a = a*2 % N; b >>= 1;
	}
	return ret;
}

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

inline LL GCD(LL a, LL b){
	while (b) a = a % b, swap(a, b);
	return a;
}

inline void Decompose(){
	for (int seed=(rand()&32767)%(N-1)+1;!r;seed=(rand()&32767)%(N-1)+1) {
		LL w = rand() % (N-1) + 1, seg=2, tmp = -1, cnt = 0, gcd;
		while (w != tmp && !r) {
			gcd = GCD(abs(w-tmp), N);
			if (1 < gcd && gcd < N) r = Mul(N/gcd-1,gcd-1); 
			if (++cnt == seg) seg <<= 1, tmp = w;
			w = (Mul(w,w) + seed) % (N-1) + 1;
		}
	}		
}

int main(){
	srand(999971); 
	cin>>e>>N>>c; Decompose(); 
	d = EX_GCD(e,r); n = pow(c,d);
	cout<<d<<' '<<n;
	return 0;
}

【BZOJ 2242】[SDOI2011] 计算器

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2242
数据生成器:http://paste.ubuntu.com/22875643/
数据传送门:http://pan.baidu.com/s/1dE71QHr

这个题,做了一个下午+一个晚上,最后才发现是把”cannot”中间多加了一个‘a’
MD,老子好想杀人! (╯‵□′)╯︵┻━┻

题目本身很简单,就是快速幂+拓展欧几里得+BSGS
但网上的程序,多少有问题,反正我能搜出来的,我都可以叉掉
我这份代码问题应该比较少吧:

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

const int MAXN = 100000;
const double EPS = 1e-5;

namespace Hash{
	const int MOD = 99971;
	int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
	
	inline void init(){
		T = 0;
		memset(head,0,sizeof(head));
	}
	
	inline void insert(int w, int d){
		nxt[++T] = head[w%MOD];
		val[T] = w; data[T] = d;
		head[w%MOD] = T;
	}	
	
	inline int find(int w){
		for (int i=head[w%MOD];i;i=nxt[i])
			if (val[i] == w) return data[i];
		return -1;
	}
};

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 int quick_pow(int a,int b,int c){
	int ret = 1; while (b) {
		if (b & 1) ret = ((LL)ret * a) % c;
		a = (LL)a*a%c; b >>= 1;
	} return ret;
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, int &x, int &y){
	if (!b) x=1, y=0;
	else EX_GCD(b,a%b,y,x), y-=a/b*x;
}

inline int EX_GCD(int a, int b, int c) {
	int ret,tmp,gcd=GCD(a,b); 
	if (c%gcd) return -1;
	else {
		EX_GCD(a/gcd,b/gcd,ret,tmp);
		ret = (((LL)c/gcd*ret) % b + b) % b;
		return ret;
	}
}

inline void solve(int a, int b, int c) {
	int ret = EX_GCD(a,c,b); 
	if (~ret) printf("%d\n",ret);
	else printf("Orz, I cannot find x!\n");
}

inline void BSGS(int a, int b, int c) {
	Hash::init(); a %= c; b %= c;
	if (!a && b > 1) {printf("Orz, I cannot find x!\n"); return;}
	
	int lim = int(ceil(sqrt(c))+EPS);
	for (int i=0,w=1;i<=lim;i++) {
		if (w == b) {printf("%d\n",i); return;}
		Hash::insert(w,i);
		w = ((LL)w*a) % c;
	}
	
	int w_ori = quick_pow(a,lim,c), rev_ori = quick_pow(w_ori,c-2,c);
	for (int i=1,w=w_ori,rev=rev_ori;i<=lim;i++) {
		int tmp = Hash::find(((LL)rev*b) % c);
		if (tmp > -1) {printf("%d\n",i*lim+tmp); return;}
		w = ((LL)w*w_ori) % c;
		rev = ((LL)rev*rev_ori) % c;
	}
	printf("Orz, I cannot find x!\n");
}

int main(){
	int T=read(),ty=read(); while (T--) {
		int a=read(), b=read(), c=read();
		if (ty == 1) printf("%d\n",quick_pow(a,b,c));
		else if (ty == 2) solve(a,b,c);
		else BSGS(a,b,c);
	}
	return 0;
}