「解题报告」洛谷十月月赛 II

又是垫底的一天啊,凉心出题人再次让我感受到了没技术的弱小,不过还是水个题解吧……

A 梦中梦与不再有梦

签到结论题。首先 $n=1$ 时答案为 0,$n=2$ 时答案为 1,然后考虑 $n\ge 3$:

  1. 当 $n$ 是奇数时,由于图上不存在奇点,那么必然有欧拉回路,答案为 $\dbinom{n}{2}$
  2. 当 $n$ 是偶数时,因 $n\ge 3$,则图上存在多于两个奇点。我们只能保留其中两个,那么删掉 $n/2-1$ 个奇点,答案是 $\dbinom{n}{2}-n/2+1$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int s = 0, ne = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') ne = -1; c = getchar();}
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * ne;
}
int T, n;
int work(){
if(n == 1) return puts("0"), 0;
if(n == 2) return puts("1"), 0;
if(n & 1) return printf("%lld\n", n * (n - 1) / 2), 0;
return printf("%lld\n", (n * (n - 1) / 2) - (n / 2) + 1), 0;
}
signed main() {T = read(); while(T--){n = read(), work();}}

B 深海少女与胖头鱼

设 $f(n,m)$ 为当前场面剩余 $n$ 个带盾的和 $m$ 个不带盾的时,剩余操作次数的期望。显然有:
$$ \begin{align} f(n,0) &=2+\dfrac{1}{n}f(n-1,0)+\dfrac{n-1}{n}f(n-1,1)\tag 1 \newline f(n,1)&=1+\dfrac{n}{n+1}f(n,1)+\dfrac{1}{n+1}f(n,0)\tag 2 \newline f(n,m)&=1+\dfrac{m}{n+m}f(n,m-1)+\dfrac{n}{n+m}f(n+m-1,1)\tag 3 | m>1 \end{align} $$ 我们令 $(2)$ 代 $(1)$ 得:
$$ \begin{aligned} f(n,0)&=n+1+f(n-1,0) \newline f(n,1)&=n+1+f(n,0) \end{aligned} $$ 归纳可得:
$$ f(n,0)=\dfrac{n(n+3)}{2},f(n,1)=n+1+\dfrac{n(n+3)}{2} $$ 于是 $m\le 1$ 的情况做完了,对于 $m>1$ 的情况,根据 $(3)$ 式,容易发现此时分成了 $f(·,m-1)$ 和 $f(·,1)$ 两部分,然后就可以愉快的 $O(m)$ 递推了。

代码,常数不小:

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int P = 998244353;
const int i2 = 499122177;
const int CN = 1e6 + 60;
int read(){
int s = 0, ne = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') ne = -1; c = getchar();}
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * ne;
}
int qp(int a, int b){
int r = 1;
while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;}
return r;
}
int add(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int n, nn, nN, m, f[CN];
signed main() {
n = read() % P, m = read(), nn = 1ll * n * i2 % P, nN = add(n, 1);
f[0] = 1ll * nn * (n + 3) % P;
for(int i = 1; i <= m; i++){
int M = add(n, i), t;
t = add(add(M, 1), P - (2ll * qp(M, P - 2) % P));
t = 1ll * t * nn % P;
f[i] = add(t, nN);
t = 1ll * i * qp(add(n, i), P - 2) % P;
t = 1ll * t * f[i - 1] % P;
f[i] = add(f[i], t);
}
printf("%d", f[m]);
}

C 蝴蝶与花

不会/kk

D 象棋与马

首先考虑 $p(a,b)$ 什么时候能等于 1。

显然有一个必要条件是 $(a,b)=1$,但是样例就已经说明了这不是充分的;这时候打个表就会发现第二个条件是 $|a-b| \text{ mod } 2 = 1$。

于是就变成了求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n [(i,j)=1][|i-j|\text{ mod }2=1]$,显然原式等于 $2\sum\limits_{i=1}^n\sum\limits_{j=1}^i [(i,j)=1][|i-j|\text{ mod }2=1]$,我们考虑求后面这个和式。

考虑对于偶数 $i$,因为偶数不可能和偶数互质,那么其贡献应当是 $\varphi(i)$。对于奇数 $i$,因为与其互质的数有一半是奇数,一半是偶数,所以其贡献应当是 $\dfrac{\varphi(i)}{2}$。所以我们在求:
$$ \sum\limits_{i=1}^n [i\text{ mod }2=0]\varphi(i)+\sum\limits_{i=1}^n [i\text{ mod }2=1]\dfrac{\varphi(i)}{2} $$ 剩下的就是杜教筛和常数的事了。可是我不会杜教筛啊/kk 流下没技术的泪水……

50 分辣鸡代码:

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
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int CN = 1e7 + 7;
int read(){
int s = 0; char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s;
}
int phi[CN], p[CN]; bool np[CN];
void sieve(int n){
np[1] = 1, phi[1] = 1;
for(int i = 2; i <= n; i++){
if(!np[i]) p[++p[0]] = i, phi[i] = i - 1;
for(int j = 1; j <= p[0] && i * p[j] <= n; j++){
int x = i * p[j]; np[x] = 1;
if(i % p[j]) phi[x] = (p[j] - 1) * phi[i];
else {phi[x] = p[j] * phi[i]; break;}
}
}
}
int T, n;
signed main()
{
sieve(1e7), T = read();
while(T--){
n = read(); int ans = 0;
for(int i = 2; i <= n; i++){
if(i & 1) ans += phi[i] >> 1ull;
else ans += phi[i];
}
printf("%llu", ans << 1ull), puts("");
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×