寒鸽儿のBlog

Rnk3 T1、T2连续翻车丢人
60 + 20 + 100

T1 简单问题

给定 $a,k$，请你求出 $a^1+a^2+a^3+...+a^k$ 对 $998244353$ 取模后的结果。
由高中数学知识, 当$a \not = 1$时结果等于 $a \dot \frac{a^k-1}{a-1}$, $a = 1$时结果等于 $k$.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 998244353;

ll qp(ll a, ll b) {
   ll res = 1 % mod;
   for(; b; b >>= 1) {
   	if(b & 1) res = res * a % mod;
   	a = a * a % mod;
   }
   return res;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   ll a, k;
   cin >> a >> k;
   a %= mod;
   if(a == 1) cout << (k % mod) << '\n';
   else { 
   	ll res = a * (qp(a, k) - 1) % mod;
   	res = res * qp(a - 1, mod - 2) % mod;
   	cout << res << '\n';
   }
   return 0;
}

T2 权值覆盖问题

并查集写法挂掉了，题解给的是差分约束。
等弄明白想法对不对再补上罢，咕咕咕。。。

T3 删边问题

套路化的离线解法，把删边看作是加边，然后对加边的情况进行讨论和更新(和BFS一致)即可。

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

struct edge {
	int u, v;
	edge() {}
	edge(int U, int V) : u(U), v(V) {}
};
vector<edge> edges;
vector< vector<int> > e, e_raw;
vector<int> del, ans, dis, dis_raw;
vector<bool> isdel;

queue<int> que;
void bfs_raw() {
	dis_raw[1] = 0;
	que.push(1);
	while(!que.empty()) {
		int cur = que.front(); que.pop();
		for(int ver : e_raw[cur]) {
			if(inf == dis_raw[ver]) {
				dis_raw[ver] = dis_raw[cur] + 1;
				que.push(ver); 
			}
		}
	}

}

void bfs_end() {
	dis[1] = 0;
	que.push(1);
	while(!que.empty()) {
		int cur = que.front(); que.pop();
		for(int ver : e[cur]) {
			if(inf == dis[ver]) {
				dis[ver] = dis[cur] + 1;
				que.push(ver);	
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, q, tmp, u, v;
	cin >> n >> m >> q;
	isdel.assign(m, false);
	edges.resize(m);
	e_raw.resize(n + 1);
	e.resize(n + 1);
	dis.assign(n + 1, inf);
	dis_raw.resize(n + 1, inf);
	ans.resize(q + 1);
	for(int i = 0; i < m; ++i) {
		cin >> u >> v;
		edges[i] = edge(u, v);
		e_raw[u].push_back(v);
		e_raw[v].push_back(u);
	}
	for(int i = 0; i < q; ++i) {
		cin >> tmp;
		--tmp;
		if(!isdel[tmp]) {
			isdel[tmp] = true;
			del.push_back(tmp);
		} else {
			del.push_back(-1);
		}
	}
	bfs_raw();
	for(int i = 0; i < m; ++i)
		if(!isdel[i]) {
			e[edges[i].u].push_back(edges[i].v);
			e[edges[i].v].push_back(edges[i].u);
		}
	bfs_end();
	for(int i = 1; i <= n; ++i)
		if(dis[i] != dis_raw[i])
			++ans[q];
	for(int i = q - 1; ~i; --i) {
		ans[i] = ans[i + 1];
		if(!~del[i]) continue;
		u = edges[del[i]].u, v = edges[del[i]].v;
		e[u].push_back(v);
		e[v].push_back(u);
		if(abs(dis[u] - dis[v]) <= 1)
			continue;
		if(dis[u] < dis[v]) swap(u, v);
		dis[u] = dis[v] + 1;
		if(dis[u] == dis_raw[u]) --ans[i];
		que.push(u);
		while(!que.empty()) {
			int cur = que.front(); que.pop();
			for(int ver : e[cur]) {
				if(dis[ver] > dis[cur] + 1) {
					dis[ver] = dis[cur] + 1;
					if(dis[ver] == dis_raw[ver]) --ans[i];
					que.push(ver);
				}
			}
		}
	}
	for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
	return 0;
}