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

【日常小测】题目1

相关链接

题目传送门:http://paste.ubuntu.com/24087405/
数据生成器:http://paste.ubuntu.com/24087409/
std:http://paste.ubuntu.com/24087412/

题目大意

求$\sum_{i=1}^n{f_i^k}$
其中$f_x$为第$x$项$Fibonacci$数
$n \le 1e18, k \le 1e5$

解题报告

之前鏼爷讲过二次剩余,于是看到这个模数就知道方向了
在暴力求出$\sqrt 5$的二次剩余后,我们可以推出答案长这样
$$\sum_{j=0}^{k}{(-1)^{k-j} \cdot C_k^j \sum_{i-1}^n{(A^jB^{k-j})^i}}$$
于是我们搞一搞组合数,逆元什么的这题就做完啦!

Code

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

const int MOD = 1000000009;
const int A = 691504013;
const int B = 308495997;
const int REV_SQRT_FIVE = 276601605;
const int N = 100009;

int k,vout,PA[N],PB[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, LL 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 Mul(int a, LL b) {
	int ret = 0;
	for (;b;b>>=1,(a<<=1)%=MOD)
		if (b & 1) (ret += a) %= MOD;
	return ret;
}

int main() {
	freopen("A.in","r",stdin); 
	freopen("A.out","w",stdout); 
	LL n; cin>>n; k = read();
	PA[0] = PB[0] = 1;
	for (int i=1;i<=k;i++) {
		PA[i] = (LL)PA[i-1] * A % MOD;
		PB[i] = (LL)PB[i-1] * B % MOD;
	}
	for (int i=0,c=1,v;i<=k;i++) {
		v = (LL)PA[i] * PB[k-i] % MOD; 
		if (v == 1) v = Mul(v, n);
		else v = ((LL)Pow(v, n+1) - v) * Pow(v-1, MOD-2) % MOD;
		if (k-i & 1) (vout -= (LL)c * v % MOD) %= MOD;
		else (vout += (LL)c * v % MOD) %= MOD;
		c = ((LL)c * (k - i) % MOD) * Pow(i+1, MOD-2) % MOD; 
	} 
	printf("%d\n",((LL)vout*Pow(REV_SQRT_FIVE,k)%MOD+MOD)%MOD);
	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;
}

【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:如果不知道上面的那个定理,貌似自己推也是可以推出来的?