「解题报告」洛谷十月月赛 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$

代码：

#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)$ 递推了。

代码，常数不小：

#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} $$

考虑有等式：

$$\sum\limits_{i=1}^n \varphi(i)[i\bmod 2=0]=\sum\limits_{i=1}^{\lfloor n/2\rfloor}\varphi(i)[i\bmod 2=1] + 2\sum\limits_{i=1}^{\lfloor n/2\rfloor}\varphi(i)[i\bmod 2=0]$$

即是考虑新增一个因子 $2$ 的贡献，那么直接杜教筛即可 $O(n^{2/3})$。

大常数辣鸡代码：

#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
const int CN = 1e7 + 10;
ULL read(){
    ULL s = 0; char c = getchar(); for(;c < '0' || c > '9';c = getchar());
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s;
}
int T, pr[CN], mu[CN]; ULL p, p0, p1, phi[CN], phi0[CN], phi1[CN]; bool np[CN];
class PAIR {public: ULL p, p0, p1;};
PAIR mp(ULL a, ULL b, ULL c) {PAIR o; o.p = a, o.p0 = b, o.p1 = c; return o;}
class MAP{
  public: static const int P = 191011109, CN = 5e6 + 10;
    class fs {public: ULL key; int nxt; PAIR val;} E[CN]; int ecnt, hd[CN];
    PAIR& operator [] (const ULL &o){
        ULL A = o >> 25, B = o & ((1 << 25) - 1), u = (A ^ B ^ P) % CN;
        for(int k = hd[u]; k; k = E[k].nxt) if(E[k].key == o) return E[k].val;
        E[++ecnt].key = o, E[ecnt].nxt = hd[u], hd[u] = ecnt; return E[ecnt].val;
    }
    bool count(const ULL &o){
        ULL A = o >> 25, B = o & ((1 << 25) - 1), u = (A ^ B ^ P) % CN;
        for(int k = hd[u]; k; k = E[k].nxt) if(E[k].key == o) return 1;
        return 0;
    }
} vis;
void solve(ULL n, ULL &p, ULL &p0, ULL &p1){
    if(n <= int(1e7)) return (void)(p = phi[n], p0 = phi0[n], p1 = phi1[n]);
    if(vis.count(n)) return (void)(p = vis[n].p, p0 = vis[n].p0, p1 = vis[n].p1);
    p = n & 1 ? ((n + 1) / 2) * n : (n / 2) * (n + 1), p0 = p1 = 0; ULL P, P0, P1;
    for(ULL l = 2; l <= n; l++){
        ULL r = n / (n / l); solve(n / l, P, P0, P1);
        if(l == 2) p0 = (P0 << 1) + P1; p -= (r - l + 1) * P, l = r;
    }
    p1 = p - p0, vis[n] = mp(p, p0, p1);
}
int main(){
    int n = 1e7; np[1] = phi[1] = mu[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!np[i]) pr[++pr[0]] = i, mu[i] = -1, phi[i] = i - 1;
        for(int j = 1; j <= pr[0] && i * pr[j] <= n; j++){
            int x = i * pr[j]; np[x] = 1;
            if(i % pr[j]) mu[x] = -mu[i], phi[x] = phi[i] * (pr[j] - 1);
            else {phi[x] = phi[i] * pr[j]; break;}
        }
    }
    for(int i = 2; i <= n; i++) i & 1 ? phi1[i] = phi[i] : phi0[i] = phi[i];
    for(int i = 1; i <= n; i++) mu[i] += mu[i - 1], phi[i] += phi[i - 1], phi1[i] += phi1[i - 1], phi0[i] += phi0[i - 1];
    T = read(); while(T--) solve(read(), p, p0, p1), printf("%llu\n", (p0 << 1) + p1);
    return 0;
}