2020-08-07发表2021-08-28更新ICPC/CCPC / Contests / 其他15 分钟读完 (大约2306个字)

2020杭电多校（第六场）

1001 Road To The 3rd Building

显然，

$\text{ANS}=\frac{\sum\limits_{i=1}^n\sum\limits_{j=i}^n\frac{1}{j-i+1}\sum\limits_{k=i}^ja_k}{\sum\limits_{i=1}^n\sum\limits_{j=i}^n1}=\frac{\sum\limits_{i=1}^n\sum\limits_{j=i}^n\frac{1}{j-i+1}\sum\limits_{k=i}^ja_k}{\frac{n(n+1)}{2}}$

其中分子的化简如下：

$\begin{align} \sum_{i=1}^n\sum_{j=i}^n\frac{1}{j-i+1}\sum_{k=i}^ja_k&=\sum_{i=1}^n\sum_{l=1}^{n-i+1}\frac{1}{l}\sum_{k=i}^{i+l-1}a_k&&置\;l=j-i+1\\ &=\sum_{l=1}^n\frac{1}{l}\sum_{i=1}^{n-l+1}\sum_{k=i}^{i+l-1}a_k&&求和号换序\\ &=\sum_{l=1}^n\frac{1}{l}\sum_{k=1}^{n}\sum_{i=\max(1,k+1-l)}^{\min(k,n-l+1)}a_k&&求和号换序\\ &=\sum_{l=1}^n\frac{1}{l}\sum_{k=1}^n\big[\min(k,n-l+1)-\max(1,k+1-l)+1\big]a_k \end{align}$

枚举 $l$，预处理之后分段计算 $k$ 即可。

时间复杂度：$O(n)$

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;
const LL MOD = 1e9+7;

int n;
LL a[N], sum[N], kak[N], inv[N];

int main(){
	inv[1] = 1; for(int i = 2; i <= 200001; i++){
		inv[i] = -(MOD / i) * inv[MOD % i];
		((inv[i] %= MOD) += MOD) %= MOD;
	}
	int T; for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++){
			read(a[i]);
			sum[i] = (sum[i-1] + a[i]) % MOD;
			kak[i] = (kak[i-1] + i * a[i]) % MOD;
		}
		LL ans = 0;
		for(int l = 1; l <= n; l++){
			LL res = 0;
			int k1 = min(l, n - l + 1), k2 = max(l, n - l + 1);
			(res += kak[k1]) %= MOD;
			if(l > n - l + 1)	(res += (n - l + 1ll) * (sum[k2] - sum[k1]) % MOD) %= MOD;
			else if(l < n - l + 1)	(res += l * (sum[k2] - sum[k1]) % MOD) %= MOD;
			(res += (n + 1ll) * (sum[n] - sum[k2]) % MOD - (kak[n] - kak[k2]) % MOD) %= MOD;
			((res %= MOD) += MOD) %= MOD;
			(res *= inv[l]) %= MOD;
			(ans += res) %= MOD;
		}
		ans = ans * inv[n] % MOD * inv[n+1] % MOD * 2ll % MOD;
		printf("%lld\n", ans);
	}
	return 0;
}

1002 Little Rabbit’s Equation

模拟。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int n, f[1005];
char s[105];

inline bool check(LL bs){
	for(int i = 1; i <= n; i++){
		if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '=')	continue;
		if(f[s[i]] >= bs)	return false;
	}
	LL a = 0, b = 0, c = 0;
	LL *t = &a;
	int kind = 0;
	for(int i = 1; i <= n; i++){
		if(s[i] == '+'){ kind = 1; t = &b; continue; }
		else if(s[i] == '-'){ kind = 2; t = &b; continue; }
		else if(s[i] == '*'){ kind = 3; t = &b; continue; }
		else if(s[i] == '/'){ kind = 4; t = &b; continue; }
		else if(s[i] == '='){ t = &c; continue; }
		(*t) = (*t) * bs + f[s[i]];
	}
	if(kind == 1)	return a + b == c;
	else if(kind == 2)	return a - b == c;
	else if(kind == 3)	return a * b == c;
	else if(kind == 4)	return a == b * c;
	return false;
}

int main(){
	for(int i = 0; i <= 9; i++)	f[i+'0'] = i;
	for(int i = 'A'; i <= 'F'; i++)	f[i] = i - 'A' + 10;
	while(scanf("%s", s+1) != EOF){
		n = strlen(s+1);
		bool ok = false;
		for(int b = 2; b <= 16; b++){
			if(check(b)){
				ok = true;
				printf("%d\n", b);
				break;
			}
		}
		if(!ok)	puts("-1");
	}
	return 0;
}

1005 Fragrant numbers

明天再写

1006 A Very Easy Graph Problem

由于边权都是 $2^i$ 且互不相同，依据题目输入顺序，两个点之间的最短路就是它们一旦连通的时候的路径。也就是说，根据加的边做生成树即可。

接下来就是一个 $\text{dp}$ 了，计算以 $i$ 为根的子树中黑白点的数量，据此计算每条边的贡献。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;
const LL MOD = 1e9+7;

LL power[N<<1] = {1};
int n, m, a[N], sum[2];
vector<pii> edge[N];

int fa[N];
int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
void unionn(int x, int y){ fa[findfa(y)] = findfa(x); }

int dp[N][2];
LL ans;
void dfs(int x, int f){
	dp[x][a[x]] = 1;
	for(auto &to : edge[x]){
		if(to.first == f)	continue;
		dfs(to.first, x);
		dp[x][0] += dp[to.first][0];
		dp[x][1] += dp[to.first][1];
		(ans += dp[to.first][0] * (sum[1] - dp[to.first][1]) % MOD * power[to.second] % MOD) %= MOD;
		(ans += dp[to.first][1] * (sum[0] - dp[to.first][0]) % MOD * power[to.second] % MOD) %= MOD;
	}
}

inline void initCASES(){
	sum[0] = sum[1] = ans = 0;
	for(int i = 1; i <= n; i++){
		fa[i] = i;
		edge[i].clear();
		dp[i][0] = dp[i][1] = 0;
	}
}

int main(){
	for(int i = 1; i <= 200000; i++)	power[i] = power[i-1] * 2 % MOD;
	int T; for(read(T); T; T--){
		read(n, m);
		initCASES();
		for(int i = 1; i <= n; i++)	read(a[i]), sum[a[i]]++;
		for(int i = 1; i <= m; i++){
			int u, v; read(u, v);
			if(findfa(u) == findfa(v))	continue;
			unionn(u, v);
			edge[u].pb(mp(v, i)), edge[v].pb(mp(u, i));
		}
		dfs(1, 0);
		printf("%lld\n", ans);
	}
	return 0;
}

1007 A Very Easy Math Problem

$\begin{align} &\sum_{a_1=1}^n\cdots\sum_{a_x=1}^n\left(\prod_{j=1}^xa_j^k\right)f(\gcd(a_1,\cdots,a_x))\gcd(a_1,\cdots,a_x)\\ =&\sum_{a_1=1}^n\cdots\sum_{a_x=1}^n\left(\prod_{j=1}^xa_j^k\right)\mu^2(\gcd(a_1,\cdots,a_x))\gcd(a_1,\cdots,a_x)&&注意到\;f=\mu^2\\ =&\sum_{d=1}^n\sum_{a_1=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\cdots\sum_{a_x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(a_1,\cdots,a_x)=1]{\left(a_1\cdots a_x\right)}^kd^{kx+1}\mu^2(d)&&枚举\;d=\gcd(a_1,\cdots,a_x)\\ =&\sum_{d=1}^nd^{kx+1}\mu^2(d)\sum_{a_1=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\cdots\sum_{a_x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}(a_1\cdots a_x)^k\sum_{r\mid\gcd(a_1,\cdots,a_x)}\mu(r)&&\epsilon=\mu*1\\ =&\sum_{d=1}^nd^{kx+1}\mu^2(d)\sum_{r=1}^{\left\lfloor\frac{n}{d}\right\rfloor}r^{kx}\mu(r)\sum_{a_1=1}^{\left\lfloor\frac{n}{dr}\right\rfloor}\cdots\sum_{a_x=1}^{\left\lfloor\frac{n}{dr}\right\rfloor}(a_1\cdots a_x)^k&&求和号换序\\ =&\sum_{d=1}^nd^{kx+1}\mu^2(d)\sum_{r=1}^{\left\lfloor\frac{n}{d}\right\rfloor}r^{kx}\mu(r)\left(\sum_{i=1}^{\left\lfloor\frac{n}{dr}\right\rfloor}i^k\right)^x&&后面那一坨算出来\\ =&\sum_{T=1}^nT^{kx}\left(\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}i^k\right)^x\sum_{d\mid T}d\mu^2(d)\mu\left(\frac{T}{d}\right)&&令\;T=rd \end{align}$

推不动了，于是把 $\sum\limits_{d\mid T}d\mu^2(d)\mu\left(\frac{T}{d}\right)$ 这玩意儿单独拿出来，$O(nH(n))$预处理（可能可以线性筛预处理吧，但是没必要）。然后数论分块。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const LL MOD = 1e9+7;
const int N = 200005;

int mu[N], pList[N], pID;
bool notP[N];
void Euler(int n){
	notP[0] = notP[1] = 1;
	mu[1] = 1;
	for(int i = 1; i <= n; i++){
		if(notP[i] == 0){
			pList[++pID] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= pID; j++){
			if(1ll * i * pList[j] > n)	break;
			notP[i * pList[j]] = 1;
			if(i % pList[j] == 0){
				mu[i * pList[j]] = 0;
				break;
			}
			else	mu[i * pList[j]] = -mu[i];
		}
	}
}

inline LL fpow(LL bs, LL idx){
	LL res = 1;
	bs %= MOD;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

int T;
LL k, x;
LL f[N], S[N], inv, g[N];

int main(){
	Euler(200000);
	read(T, k, x);
	for(int d = 1; d <= 200000; d++)
		for(int i = d; i <= 200000; i += d)
			(f[i] += d * mu[d] % MOD * mu[d] % MOD * mu[i / d] % MOD) %= MOD;
	for(int i = 1; i <= 200000; i++){
		S[i] = (S[i-1] + fpow(i, k * x % (MOD-1)) * f[i] % MOD) % MOD;
		g[i] = (g[i-1] + fpow(i, k)) % MOD;
	}
	while(T--){
		LL ans = 0;
		LL n; read(n);
		for(LL l = 1, r; l <= n; l = r + 1){
			r = n / (n / l);
			ans += ((S[r] - S[l-1]) % MOD + MOD) * fpow(g[n/l], x) % MOD;
			ans %= MOD;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

1009 Divisibility

真是巧了，前几天才看了这个问题。

根据九余数定理的推广，一个 $b$ 进制数的各个数位相加与它本身模 $x$ 同余的充要条件是：$b\equiv1\pmod x$.

所以这道题只需要判断是否 $b\bmod x=1$ 即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T;
LL b, x;

int main(){
	for(read(T); T; T--){
		read(b, x);
		if(b % x == 1)	puts("T");
		else	puts("F");
	}
	return 0;
}

1010 Expectation

对每一位运用 $\textbf{Matrix-Tree Theorem}$ 计算这一位的生成树数量，这些数量按照二进制乘出来之后除以总的生成树数量即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 105;
const int M = 20005;
const LL MOD = 998244353;

inline LL fpow(LL bs, LL idx){
	bs %= MOD;
	LL res = 1;
	while(idx){
		if(idx & 1)    (res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

namespace LA{
	int n;
	LL a[N][N], b[N];
	
	void init(int nn){
		n = nn;
		for(int i = 1; i <= n; i++){
			b[i] = 0;
			for(int j = 0; j <= n; j++)	a[i][j] = 0;
		}
	}
	LL det(){ // get determinant
		LL res = 1;
		int flag = 1;
		for(int j = 1; j <= n; j++){
			int r = j;
			for(int i = j + 1; i <= n; i++)
				if(a[i][j] > a[j][j])
					r = i;
			if(r != j)	swap(a[r], a[j]), flag = -flag;
			if(a[j][j] == 0)	return 0;
			for(int i = 1; i <= n; i++){
				if(i == j)	continue;
				LL div = a[i][j] * fpow(a[j][j], MOD-2) % MOD;
				for(int k = j; k <= n; k++){
					a[i][k] -= div * a[j][k] % MOD;
					((a[i][k] %= MOD) += MOD) %= MOD;
				}
			}
		}
		for(int i = 1; i <= n; i++)	(res *= a[i][i]) %= MOD;
		return flag > 0 ? res : MOD - res;
	}
}

int T, n, m;
LL u[M], v[M], w[M];

inline LL solve(int b){
	LA::init(n-1);
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			LA::a[i][j] = 0;
	for(int i = 1; i <= m; i++){
		if(b == -1 || ((w[i] >> b) & 1)){
			LA::a[u[i]][v[i]]--, LA::a[v[i]][u[i]]--;
			LA::a[u[i]][u[i]]++, LA::a[v[i]][v[i]]++;
		}
	}
	for(int i = 1; i < n; i++)
		for(int j = 1; j < n; j++)
			((LA::a[i][j] %= MOD) += MOD) %= MOD;
	return LA::det();
}

int main(){
	for(read(T); T; T--){
		read(n, m);
		for(int i = 1; i <= m; i++)    read(u[i], v[i], w[i]);
		LL ans = 0;
		for(int b = 31; b >= 0; b--)    ans = (ans * 2 + solve(b)) % MOD;
		LL tot = solve(-1);
		printf("%lld\n", ans * fpow(tot, MOD-2) % MOD);
	}
	return 0;
}

2020杭电多校（第六场）

http://xyfjason.github.io/blog-xcpc/2020/08/07/2020杭电多校（第六场）/

作者

xyfJASON

发布于

2020-08-07

更新于

2021-08-28

许可协议

#HDU

2020杭电多校（第六场）

1001 Road To The 3rd Building

1002 Little Rabbit’s Equation

1005 Fragrant numbers

1006 A Very Easy Graph Problem

1007 A Very Easy Math Problem

1009 Divisibility

1010 Expectation

作者

发布于

更新于

许可协议

评论

分类

最新文章

标签