2021 CCPC 威海站

发表于 分类于

题目链接

链接

题解

A. Goodbye, Ziyin!

签到题，二叉树必须满足每个点的度数 $\le 3$，且根节点度数 $\le 2$，判断一下即可。

C. Assign or Multiply

题意

给定 $m$ 个操作，每个操作形如给 $x$ 赋值给 $a_i$，或给 $x$ 乘上 $a_i$。

任意安排这些操作的顺序，问有多少个 $i$ 满足 $i\in[0,p-1]$ 使得不存在某种操作顺序，使 $x\bmod p$ 最终值为 $i$。

$x$ 的初始值为 $1$。

$m\le10^6,3\le p\le 2\times 10^5,p\in \mathbb{P}$

题解

因为有赋值操作，那么相当于在赋值操作中选择一个，然后在乘法操作中选择若干个，问最后的值可以是多少。（注意，如果没有赋值操作，那么直接输出 $p-1$。）

由于 $p$ 为奇质数，我们求出它的原根 $g$，将乘法转化为加法。

考场中想到用bitset，但是应该是过不了的。

考虑每次操作，相当于找到所有 $bit_i=1,bit_{(i+x)\bmod p}=0$ 的 $i$，并把 $bit_{(i+x)\bmod p}$ 设为 $1$。

考虑 $i$ 向 $(i+x)\bmod p$ 连边，这样就形成了若干个环，环中 $1->0$ 和 $0->1$ 的个数显然是相等的。也就是说，如果能快速找到所有的 $bit_i\neq bit_{(i+x)\bmod p}$ 就可以了。

从小到大枚举，二分+树状数组找到第一个 $i$ 即可，此处可以用哈希判断一下。

时间复杂度 $O(n\log ^2q)$。

D. Period

周期与border是等价的，枚举原串的border，假设长度为 $i$，那么 $[i+1,n-i]$ 中都可以产生 $1$ 的贡献。

kmp，然后差分一下即可。

E. CHASE!

设 $f_i$ 表示最多选择 $i$ 次的期望。

设当且选出来的和为 $X$，若 $X\geq f_{i-1}$ 时不重新选，否则重新选。

则有：$f_i=E(X>\lfloor f_{i-1}\rfloor)+f_{i-1}P(X\le \lfloor f_{i-1}\rfloor )$

计算 $E,P$ 可用ntt预处理，也可暴力two-pointer计算。

F. Stone

神仙题。

考虑如果出现了奇数，那么先手将 $s$ 取奇数，将所有的奇数变成偶数。这样就赢了，且赢的方案数为(最小的奇数+1)/2。

否则，如果全是偶数，且 $s$ 为奇数，那么先手必败。因此 $s$ 必须为偶数，那么 $a_i$ 全都除去 $2$，就又变回来原来的问题了。

G. Desserts

就因为在这道题上自己的失误错失Au…

给定 $n$ 个数 $a_i$，满足 $\sum_{i=1}^na_i\le 10^5$。记 $f(x)=\prod_{i=1}^n\binom{a_i}{x}$，对于 $i\in [1,m]$，求 $f(i)$。

一开始就直接开始莽多点求值，结果发现旁边的人过了才反应过来。

分块，对于小于等于 $\sqrt{10^5}$ 的记录有多少个，对于大于 $\sqrt{10^5}$ 的直接暴力枚举即可。

时间复杂度 $O(n\sqrt{n})$。

H. city safety

套用最大权闭合子图的套路，先全选，然后建出图求最小割即可。

用前缀和的思想，可以将边数优化到 $O(n^2)$ 级别。

I. Distance

显然可以对每个质数分开来统计：

我们枚举质数 $p$，其贡献为：$2\times p\sum_{p^c\le n}\lfloor \frac{n}{p^c}\rfloor(n-\lfloor \frac{n}{p^c}\rfloor)$。乘 $2$ 是因为不妨假设的 $i$ 中 $p$ 的次数比 $j$ 小。

对于 $c\geq 2$ 的情况，显然有 $p\le \sqrt{n}$，暴力枚举 $\sqrt{n}$ 以内质数即可。

对于 $c=1$，其对答案贡献经过整除分块后，需要计算 $\frac{n}{i}$ 以内的质数的和。这显然是Min25筛的前一部分。

时间复杂度 $O(\frac{n^{\frac{3}{4}}}{\log n})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int N=2e6+5;
ll n;
int sqr;
int m;
int id1[N],id2[N]; ll w[N];
bool vis[N];
int cnt,pri[N];
ll s1[N],s[N];
inline void init_prime(int n)
{
	vis[1]=1;
	fo(i,2,n)
	{
		if(!vis[i]) {pri[++cnt]=i;s1[cnt]=Add(s1[cnt-1],i);}
		for(int j=1;j<=cnt&&(ll)i*pri[j]<=n;j++)
		{
			vis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
inline int id(ll _n)
{
	return (_n<=sqr)?id1[_n]:id2[n/_n];
}
int main()
{
	ll inv2=(mod+1)>>1;
	cin>>n;
	sqr=sqrt(n);
	init_prime(sqr);
	ll l=1,r;
	for(;l<=n;l=r+1)
	{
		r=n/(n/l);
		w[++m]=n/l;
		s[m]=Mul((w[m]+1)%mod,w[m]%mod)*inv2%mod-1;
		if(w[m]<=sqr) id1[w[m]]=m;
		else id2[r]=m;
	}
	fo(i,1,cnt)
	{
		ll k=1ll*pri[i]*pri[i];
		for(int j=1;j<=m&&k<=w[j];j++)
			s[j]=Dec(s[j],Mul(pri[i],Dec(s[id(w[j]/pri[i])],s1[i-1])));
	}
	ll ans=0,now,sum;
	fo(i,1,cnt)
	{
		now=1ll*pri[i]*pri[i]; sum=0;
		for(int j=2;now<=n;j++)
		{
			sum=Add(sum,(n/now)%mod*((n-(n/now))%mod)%mod);
			now=now*pri[i];
		}
		ans=Add(ans,sum*pri[i]%mod);
	}
	for(l=1;l<=n;l=r+1)
	{
		r=n/(n/l);
		sum=(n/l)%mod*((n-(n/l))%mod)%mod;
		ans=Add(ans,Dec(s[id(r)],s[id(l-1)])*sum%mod);
	}
	printf("%lld\n",ans*2%mod);
	return 0;
}

J. Circular Billiard Table

签到题，算一算gcd即可。

K. Tiny Stars

考虑 $i->\frac{a}{i}->i$，但是这样的花费是 $16n$ 的，行不通。

考虑减少一点 $i->\frac{a}{i}$，可以发现：$i->\frac{a}{i}->\frac{1}{i}->ai->i$。

此时的花费为 $4n+\frac{(14+1)n}{2}=11.5n$，可以通过。

那么怎么能在不知道 $a$ 的情况下顺利连成上述情况呢？

考虑原根，将乘除转化为加减，设 $g^t=a$，有 $g^i->g^{t-i}->g^{n-1-i}$。

易知 $i,n-1-i$ 同奇偶，那么只要 $i$ 与 $t-i$ 不同奇偶性就可以了。

即 $t$ 为奇数，显然有 $\frac{1}{2}$ 的概率可以成功。

M. 810975

容斥，考虑算出 $\le k$ 的答案即可。

考虑 $n-m$ 个 $0$ 将线段分成 $n-m+1$ 段，每一段的长度不超过 $k$。总和为 $m$，那么相当于求 $x_1+x_2+\cdots+x_{n-m+1}=m,x_i\in [0,k]$ 的方案数。

两种办法：

  • 考虑生成函数，即求 $x^m^{n-m+1}$。用快速幂或者等比数列求和。
  • 容斥，考虑至少 $i$ 个 $x$ 违反了 $[0,k]$ 的限制即可。