Camp Day7 Div2

Problem G – 抢红包机器人

一个简单的暴力做法。

枚举第 i 个人为机器人,则根据聊天记录查找所有的机器人,例如floyd-warshall算法或者直接拿bitset维护一下,就可以统计出,在他为机器人的时候,有多少人是机器人。

Problem C – 斐波那契数列

首先可以发现,x \& (x-1)=x-lowbit(x),那么

ans = \sum_{i=1}^R F_i-\sum_{i=1}^Rlowbit(F_i)

首先斐波那契数列的求和可以通过矩阵快速幂计算。

\begin{aligned} & F_n = F_{n-1} + F_{n-2} \\ \Leftrightarrow\ & S_n = 2S_{n-1} – S_{n-3} \end{aligned}

\left[\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & 0 & -1\end{matrix}\right]^{n-2}\left[\begin{matrix} S_{0} \\ S_{1} \\ S_{2} \end{matrix}\right] = \left[\begin{matrix} S_{n-1} \\ S_{n} \\ S_{n+1} \end{matrix}\right]

关于 F_n 的lowbit的计算。首先我们可以打表注意到,当 n\not=3k 时,F_n 为奇数。那么考虑 n=3k 时,考虑 F_n 的2的幂次。

\begin{aligned} F_n & = \frac{1}{\sqrt5}\left((\frac{1+\sqrt5}{2})^{3k}+(\frac{1-\sqrt5}{2})^{3k}\right) \\ & = \frac{1}{\sqrt5}\left((2+\sqrt5)^k+(2-\sqrt5)^k\right) \\ & = \frac{1}{\sqrt5}\left(\sum_{i=1}^k C_k^i 2^i \left(\sqrt5^{k-i}-(-\sqrt5)^{k-i}\right)\right) \\ & = \sum_{i=1}^k C_k^i 2^i \left(\sqrt5^{k-i-1}+(-\sqrt5)^{k-i-1}\right) \end{aligned}

k 为奇数,i 为奇数时,显然和式项对2的幂次无贡献。当 k 为奇数,i 为偶数的时候,考虑 i=1 即可得到 F_n 中2的幂次为 1。当 k 为偶数时,考虑 i=2,可以得到 lowbit(4k)|F_n

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int mod = 998244353;
lld SS[64] = { 0, 2 };

struct matrix
{
    lld V[3][3];
    matrix() noexcept { memset(V, 0, sizeof(V)); }
    lld& operator()(int a, int b) { return V[a][b]; }

    matrix& operator*=(const matrix b)
    {
        static lld tmp[3][3];
        memset(tmp, 0, sizeof(tmp));

        for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
                tmp[i][j] += V[i][k] * b.V[k][j] % mod;
            tmp[i][j] %= mod;
        }

        memcpy(V, tmp, sizeof(tmp));
        return *this;
    }
};

lld SumFib(lld n)
{
    if (n < 3) return n;
    matrix A, B;
    A(0,0) = A(1,1) = A(2,2) = 1;
    B(0,1) = B(1,2) = 1;
    B(2,0) = -1; B(2,2) = 2;

    n -= 2;
    while (n)
    {
        if (n & 1) A *= B;
        B *= B;
        n >>= 1;
    }

    return (A(2,1) + 2 * A(2,2)) % mod;
}

lld Sum001002(lld R)
{
    lld r6 = R / 6;
    lld ans = (r6 % mod) * 6 % mod;
    lld m6 = R % 6;
    ans += m6;
    if (m6 > 2) ans += 1;
    return ans % mod;
}

int log2(lld ans)
{
    int a = 0;
    while (ans)
        ans >>= 1, a++;
    return a;
}

lld Sum1213(lld R)
{
    if (R == 0) return 0;
    lld R2 = R;
    while ((R2&(-R2)) != R2)
        R2 ^= R2&(-R2);
    return (SS[log2(R2)] + Sum1213(R-R2)) % mod;
}

void solve()
{
    lld R; scanf("%lld", &R);
    lld s1 = SumFib(R);
    lld s2 = Sum001002(R);
    lld s3 = Sum1213(R/6)*4%mod;
    printf("%lld\n", ((s1-s2-s3) % mod + mod) % mod);
}

int main()
{
    for (int i = 2; i < 64; i++)
        SS[i] = (SS[i-1]*2 + (1LL<<(i-1))) % mod;
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

Problem D – 二次函数

首先可以注意到,将 F(x)=x^2+ax+b 进行水平移动 F(x-\lfloor a/2\rfloor),不改变对应相同处的函数值。在平移后,所有的二次函数都可以被规约为 A(x)=x^2+C_AB(x)=x^2+x+C_B。那么,进行一下分类讨论好了。

  • 当同时存在有 A(x)B(x) 时,令 A(x)=B(x),即有 x=C_A – C_B 处两者相交。

  • 当三者均为 A(x) 型时

    • C_1C_2 不同奇偶性,令 A_1(x+1)=A_2(x),则有 2x+1+C_1-C_2=0
    • C_1C_2 同奇偶性且 C_1 \equiv C_2 \mod 4,令 A_1(x+2)=A_2(x),则有 4x+4+C_1-C_2=0
    • 可以证明,如果三个函数各不相同,根据抽屉原理,必定存在上述两种情况之一
  • 当三者均为 B(x) 型时
    • C_1C_2 同奇偶性,令 B_1(x+1)=B_2(x),则有 2x+2+C_1-C_2=0
    • 可以证明,如果三个函数各不相同,根据抽屉原理,必定是有两个函数同奇偶性

可以证明,所有函数一定可以规约到以上规范形式。

Problem J – 强壮的排列

和前几天的置置置换是很像的,都是 p[2n]>max\lbrace p[2n-1], p[2n+1]\rbrace,但是敦哥哥给了个更适合这题的做法。记 f_n 为长度为 n 的排列符合题目要求的概率,则 n!f_n 就是本题的答案。

考虑到在此序列中,n 为最大数字在 i 的位置,那么我们可以将此序列一切两半,得到这样的一个递推公式。

f_{n} = \frac{1}{n}\sum_{i=1}^{n}f_{n-i}f_{i-1} = \frac{1}{n} \sum_{i+j=n-1} f_i f_j

这个式子可以考虑使用分治FFT来做,复杂度为 O(n \log^2 n)

进一步考虑,令 F(x)=\sum_{n=0}^\infty f_n x^n,那么有

\begin{aligned} nf_n &= \sum_{i=1}^{n}f_{n-i}f_{i-1} \\ \Leftrightarrow\ nf_nx^{n-1} &= \sum_{i+j=n-1}f_i x^i \times f_j x^j \\ \Leftrightarrow\ F'(x) &= F(x)^2 + f_1 \end{aligned}

其中 f_0=1,根据观察(大雾)可以发现 F(x) = \tan x = \frac{\sin x}{\cos x} 是这个微分方程的一个解。

利用麦克劳林展开,得到 \sin x\cos x 的组合型生成函数表示,然后使用NTT来进行多项式求逆和乘法,即可得到我们的答案。预处理阶乘和阶乘逆元 O(n),生成两者多项式 O(n),处理逆元 O(n \log n),多项式乘法 O(n\log n),所以总复杂度是 O(n \log n)

#include <bits/stdc++.h>
typedef long long lld, num_t;
using namespace std;
const int mod = 998244353, G=3;
const size_t max_len = 19;
const int MAXN = 524289;
int fac[MAXN], inv[MAXN], invs[MAXN];

void init_factory()
{
    invs[0] = inv[0] = fac[0] = 1;
    inv[1] = fac[1] = invs[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        fac[i] = 1LL * fac[i-1] * i % mod;
        inv[i] = 1LL * (mod-mod/i) * inv[mod%i] % mod;
        invs[i] = 1LL * inv[i] * invs[i-1] % mod;
    }
}

inline num_t fpow(lld a, lld k)
{
    lld ans = 1;
    while (k)
    {
        if (k & 1) ans = ans * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}

class Fourier
{
public:
    int len, N;

private:
    num_t wmk[1 << max_len];
    int rev[1 << max_len];

    inline num_t create(int m)
    {
        int k = (mod-1)/m;
        if (k < 0) k += mod-1;
        return fpow(G, k);
    }

    void dft(num_t a[], int DFT)
    {
        for (int i = 0; i < N; i++)
            if (i < rev[i])
                swap(a[i], a[rev[i]]);

        for (int m = 2; m <= N; m <<= 1)
        {
            int m2 = m >> 1;
            num_t wm = create(DFT * m);
            wmk[0] = 1;
            for (int j = 1; j < m2; j++)
                wmk[j] = wmk[j-1] * wm % mod;
            num_t t, u;

            for (int k = 0; k < N; k += m)
            {
                for (int j = 0; j < m2; j++)
                {
                    t = wmk[j] * a[k+j+m2] % mod;
                    u = a[k+j];
                    a[k+j] = (u + t) % mod;
                    a[k+j+m2] = ((u - t) % mod + mod) % mod;
                }
            }
        }

        if (DFT == -1)
            for (int i = 0; i < N; i++)
                a[i] = (a[i] * inv[N] % mod + mod) % mod;
    }

public:
    void init(int _len)
    {
        len = _len, N = 1 << _len;
        for (int i = 0; i < N; i++)
            rev[i] = (rev[i>>1]>>1)|((i&1)<<len-1);
    }

    void DFT(num_t a[]) { dft(a, 1); }
    void IDFT(num_t a[]) { dft(a, -1); }

    int log2_ceil2(int len)
    {
        int ans = 0;
        while (len) len >>= 1, ans++;
        return ans;
    }
} trans;

num_t x[MAXN], y[MAXN], dp[MAXN];

void cdqFFT(int L, int R)
{
    if (L == R)
    {
        if (L == 0) dp[L] = 0;
        else if (L == 1) dp[L] = 1;
        else dp[L] = (dp[L] * inv[L] % mod + mod) % mod;
        return;
    }

    int mid = (L + R) >> 1;
    cdqFFT(L, mid);

    int len = R - L + 1;
    trans.init(trans.log2_ceil2(len));

    // x = dp[0], dp[1], dp[2], ..., dp[len], 0, 0, ...
    // y = dp[L], dp[L+1], dp[L+2], ..., dp[mid], 0, 0, ...
    for (int i = 0; i < trans.N; i++)
    {
        x[i] = i < len ? dp[i] : 0;
        y[i] = (i <= mid-L) ? dp[i+L] : 0;
    }

    trans.DFT(x); trans.DFT(y);
    for (int i = 0; i < trans.N; ++i)
        x[i] = x[i] * y[i] % mod;
    trans.IDFT(x);

    for (int i = mid + 1; i <= R; ++i)
        dp[i] = (dp[i] + x[i-L-1] * (L?2:1)) % mod;
    cdqFFT(mid + 1, R);
}

void get_inv(num_t a[], num_t b[], int len)
{
    static num_t A[MAXN], B[MAXN];

    if (len == 1)
    {
        b[0] = fpow(a[0], mod-2);
        return;
    }

    get_inv(a, b, len>>1);
    trans.init(trans.log2_ceil2(len));
    for (int i = 0; i < len; i++)
        A[i] = a[i], B[i] = b[i], A[i+len] = 0, B[i+len] = 0;
    trans.DFT(A); trans.DFT(B);
    for (int i = 0; i < trans.N; i++)
        A[i] = (A[i] * B[i] % mod) * B[i] % mod;
    trans.IDFT(A);

    for (int i = 0; i < len; i++)
        b[i] = (2LL * b[i] % mod - A[i] + mod) % mod;
}

int main()
{
    init_factory();

#ifdef CDQFFT
    // f_n = 1/n * \sum {i+j=n-1} f_i*f_j
    cdqFFT(0, 131071);
#else
    // y for cosx then x for secx
    // then y for sinx then dp for secx+tanx
    for (int i = 0; i < 262144; i++)
        y[i] = (i&1) ? 0 : (i&2) ? mod-invs[i] : invs[i];
    get_inv(y, x, 262144);
    for (int i = 1; i < 262144; i++)
        y[i] = (i&1) ? (i&2) ? mod-invs[i] : invs[i] : 0;
    trans.init(19);
    trans.DFT(x); trans.DFT(y);
    for (int i = 0; i < trans.N; i++)
        dp[i] = x[i] * y[i] % mod;
    trans.IDFT(dp);
#endif

    int T, n; scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &n);
        printf("%lld\n", dp[n] * fac[n] % mod);
    }

    return 0;
}

Camp Day5 Div2

Problem A – Gactus Draw

由于有要求边不能有公共点,那么我们可以让每颗子树都相离较远。如果我们将树的 dfs序 作为横坐标,depth 作为纵坐标,那么构造出来的图形一定是符合要求的。

Problem C – Division

题中的操作相当于将数字进行一次右移,相当于减去了某个某个指定的数值。

如果我们将会被减去的数记录下来,至多 32n 个,那么先把和保存下来,然后减去的数保存下来排个序,把最前面至多 k 个数字加进和即可。

Problem F – Kropki

考虑做一个状压dp,记为 dp[S][n],表示以状态 S 排布的数字以 n 为结尾的方案数,其中 S 中已选上的元素数量为 c(S)。另外点的01串存在 stat[] 中。那么有

dp[S][n] = \begin{cases} \sum_{u=2n,n/2} dp[S-\lbrace n \rbrace][u], & stat[c(S)]=1 \\ \sum_{u\not= 2n,n/2}dp[S-\lbrace n\rbrace][u], & stat[c(S)]=0 \end{cases}

然后计算即可。可以写成搜索的形式,用起bitset,然后记忆化,这样写法似乎会舒服一点(大雾)。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int LEN = 1 << 15;
const int mod = 1e9+7;
lld dp[LEN][16], n, dpt;
char st[20];

lld dfs(int S, int end)
{
    bitset<15> wtf(S);
    size_t len = wtf.count();
    if (!wtf[end-1]) return 0;
    if (len == 1) return 1;
    if (dp[S][end] != -1) return dp[S][end];

    lld ans = 0;
    wtf.flip(end-1);
    dpt++;
    for (int i = 1; i <= n; i++)
    {
        if (!wtf[i-1]) continue;

        if (end == i * 2)
        {
            if (st[len-2] == '1')
                ans += dfs(wtf.to_ulong(), i);
        }
        else if (i == end * 2)
        {
            if (st[len-2] == '1')
                ans += dfs(wtf.to_ulong(), i);
        }
        else
        {
            if (st[len-2] == '0')
                ans += dfs(wtf.to_ulong(), i);
        }
    }

    return dp[S][end] = ans % mod;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%lld %s", &n, st);
    lld ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + dfs((1<<n)-1, i)) % mod;
    printf("%lld\n", ans);
    return 0;
}

很迷啊,不会写最原始的状压dp,所以只能写写这种奇怪的东西了。

Problem H – Nested Tree

考虑一棵树的每对点间距离和的一个性质:对于某个边 e(u,v),在距离和中的贡献是 u 侧的节点数乘以 v 侧节点数。那么,我们可以利用一次dfs,对以某节点为根的子树进行搜索,统计出子树中的节点个数 x,则边另一侧的节点个数为 nm-x,所以答案就可以很轻松的维护出来。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int mod = 1e9+7;
vector<int> G[1000010];
bool vis[1000010];
int n, m;
long long ans;

int dfs(int u)
{
    if (vis[u]) return -1;
    vis[u] = true;

    int cnt = 1;
    for (auto v : G[u])
    {
        int x = dfs(v);
        if (x == -1) continue;
        ans += 1LL * x * (n*m - x) % mod;
        cnt += x;
    }

    return cnt;
}

int main()
{
    int a, b, u, v;
    scanf("%d %d", &n, &m);

    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &u, &v);

        for (int j = 0; j < m; j++)
        {
            G[j*n+u].push_back(j*n+v);
            G[j*n+v].push_back(j*n+u);
        }
    }

    for (int i = 1; i < m; i++)
    {
        scanf("%d %d %d %d", &a, &b, &u, &v);
        G[(a-1)*n+u].push_back((b-1)*n+v);
        G[(b-1)*n+v].push_back((a-1)*n+u);
    }

    assert(dfs(1) == n*m);
    printf("%lld\n", (ans % mod + mod) % mod);
    return 0;
}

Problem J – Special Judge

线段相交的判断。

Camp Day4 Div2

Problem G – 置置置换

满足条件的排列的模样是这样的:

\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\cdots

那么它的对偶排列是这样的

\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\cdots

先证明一个引理:已有一个符合条件的长度为 n 的排列时,对于任意一个 i,将该排列中所有大于等于 i 的元素增一,那么排列的增减性不变。由于排列具有局部性质,那么我们可以只考虑一个局部。如果局部中最小的元素增大了,那么最大的元素同时增大;如果局部中较大的元素增大了,那么不影响大小的偏序关系。

于是想要生成长度为 n 的排列时,可以从长度为 n-1 的排列转移而来。考虑生成以 i 为起始元素的排列,我们可以将所有大于 i 的对偶子串接在后面,并将该子串中大于 i 的元素增一。这样,我们就可以得到排列的构造方式了。

dp[n][s] 为长度为 n 的序列,以 s 为起始元素的排列个数,那么满足这样的一个转移方程:

dp[n][s] = \sum_{i=n-s+1}^{n-1} dp[n-1][i]

由于数据范围 1 \le n \le 1000,那么这样转移是 O(n^3) 的。观察到 dp[n-1][i] 在后期不会被修改,并且这是一个前缀和的形式,那么我们可以令

qzh[n][s] = \sum_{i=1}^{s} dp[n][s]

这样我们可以边转移边求前缀和,并且新的转移方程

dp[n][s] = qzh[n-1][n-1] – qzh[n-1][n-s]

这样的转移是 O(n^2) 的。

Problem A – 夺宝奇兵

观察走的路线可以知道:在路线中,A_{1,0}A_{2,0}+A_{2,1}A_{1,1}A_{1,0}A_{2,1}+A_{2,0}A_{1,1} 这两种组合方式必然二选一,并且 A_{n,0}A_{n,1} 一定是会选入的,那么直接一遍扫描计算答案即可。

Problem F – 小小马

首先会知道,马每次跳会改变目标点的奇偶性。所以,如果起终点的奇偶性相同,那么不同颜色点必然是不同的。所以这时候可以忽略。

然后当宽度为 2 时,马只能左前右后跳,所以简单判断一下。如果 n=3,m=3,那么 (2,2) 和其他点就是孤立的,所以判断一下。当更大时,马可以跳满全场,所以~

Problem I – 咆咆咆哮

显然把所有的魔术性卡牌放在最后,这样魔法加成是最大的。因为不知道答案的攻击性卡牌数量,那么可以来一个枚举。

假设目前枚举的是有 x 张攻击性卡牌,那么有 n-x 张魔术性卡牌。考虑利用一个新的权值 c_i=a_i-b_i,那么

\sum_{x \in X}a_x + \sum_{x \not\in X}b_x = \sum_{x \in X}c_x + \sum_{i=1}^n b_i

所以贪心的选择 c_ix 大的几张卡牌作为攻击性卡牌,就可以得到这样的一个权值。对每种枚举的最大值取最大,就可以得到这道题的答案了。

Camp Day3 Div2

Problem B – 集合

一个计算几何题目,如果两人线段与圆相交,那么作切线然后再绕圆弧走;如果两人线段与圆相离,那么两人汇合点与圆心连线是汇合点与两人之间的角平分线,二分即可。(目前不是AC代码)

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const double eps = 1e-8;
const double PI = acos(-1.0);
inline int sgn(double t) { return fabs(t) < eps ? 0 : t > 0 ? 1 : -1; }

struct point
{
    double x, y;
    point operator+(const point &a) const { return point(x+a.x, y+a.y); }
    point operator-(const point &a) const { return point(x-a.x,y-a.y); }
    double operator^(const point &a) const { return x*a.y-y*a.x; }
    double operator*(const point &a) const { return x*a.x+y*a.y; }
    point operator/(double a) const { return point(x/a, y/a); }
    point operator*(double a) const { return point(x*a, y*a); }
    double length() const { return sqrt(x*x+y*y); }
    point(double _x, double _y) noexcept { x = _x; y = _y; }
    double rad(const point &a, const point &b) { point q(a-*this), r=(b-*this); return acos(q*r/q.length()/r.length()); }
    point regulize(double len) { return *this/(length()/len); }
    double arg() const { return atan2(y, x); }
};

struct line
{
    double A, B, C;
    const point &s, &e;
    line(const point &a, const point &b) noexcept : s(a), e(b) { A = B = C = 0; }
    void load() { A = e.y - s.y; B = s.x - e.x; C = s.y*(e.x-s.x) - (e.y-s.y)*s.x; }
    double dis(const point &a) const { return fabs(A*a.x + B*a.y + C) / sqrt(A*A + B*B); }
    double disP2seg(point p) { if (sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0) return min((p-s).length(),(p-e).length()); else return dis(p); }
};

struct circle : point
{
    double r;
    circle() noexcept : point(0,0) { r = 0; }
    bool seg(line v) { double dst = v.disP2seg(*this); return sgn(dst-r)<0; }
};

point A1(0,0), A2(0,0);
line px(A1, A2);
circle C;

double ans_seg()
{
    // line corrupts circle
    double bigRad = C.rad(A1, A2);
    double d1 = (A1-C).length();
    double d2 = (A2-C).length();
    double sRad1 = acos(C.r / d1);
    double sRad2 = acos(C.r / d2);
    double dd1 = sqrt(d1*d1-C.r*C.r);
    double dd2 = sqrt(d2*d2-C.r*C.r);
    double ans = dd1 + dd2 + C.r*(bigRad-sRad1-sRad2);
    return ans;
}

double f(double alpha)
{
    point A3 = (A1-C)*alpha + (A2-C)*(1-alpha) + C;
    return A3.rad(A1, C) - A3.rad(A2, C);
}

double ans_bs()
{
    double l = 0.0, r = 1.0, m;
    double fl = f(l), fr = f(r), fm;

    while (r - l > eps)
    {
        m = (r+l)/2;
        fm = f(m);
        if (sgn(fl) * sgn(fm) > 0)
            l = m, fl = fm;
        else
            r = m, fr = fm;
    }

    // so now m is the correct alpha percent.
    point A3 = ((A1-C)*m + (A2-C)*(1-m)).regulize(C.r) + C;
    return (A1-A3).length() + (A2-A3).length();
}

void solve()
{
    scanf("%lf %lf %lf %lf", &A1.x, &A1.y, &A2.x, &A2.y);
    scanf("%lf %lf %lf", &C.x, &C.y, &C.r); px.load();
    printf("%.3lf\n", C.seg(px) ? ans_seg() : ans_bs());
}

int main()
{
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

Problem F – 小清新数论

对于 1 \le n \le 10^7 (for div2) 或 1 \le n \le 10^{11}

ans = \sum_{i=1}^n\sum_{j=1}^n\mu(\gcd(i,j))

那么对于div2来说,可以暴力枚举 \gcd(i,j) 的值,也可以进一步继续推算,即

\begin{aligned} ans & = \sum_{d=1}^n\mu(d)\times\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d] \\ & = \sum_{d=1}^n\mu(d)\times\sum_{k=1}^{\lfloor n/d\rfloor}\mu(k)\left\lfloor\frac{n}{dk}\right\rfloor^2 \\ & = \sum_{t=1}^n\left\lfloor\frac{n}{t}\right\rfloor^2\sum_{dk=t}\mu(d)\mu(k) \end{aligned}

那么显然后面那个是 \mu * \mu,也是个积性函数,可以用线性筛来完成。对于div1来说,这时候需要用到 O(n^\frac23) 的杜教筛来完成工作。

f(n)=\sum_{dk=n}\mu(d)\mu(k),现在欲求 F(n)=\sum_{i=1}^nf(i)。考虑 M(n)=\sum_{i=1}^n\mu(i),以及 \mu * \mu * 1 = \mu * e = \mu,那么有

F(n)=M(n)-\sum_{d=2}^nF\left\lfloor\frac{n}{d}\right\rfloor

由于杜教筛主要计算的是 F(n/i)M(n/i) 的值,并且存在记忆化,那么两个函数的计算实际上仍然是原来的复杂度,只要线性筛预处理前 O(n^\frac23) 的前缀和,后面这个函数计算复杂度依然是 O(n^\frac23)

然后在实际写代码的时候遇到了一个坑点:(n/k)*(n/k)神tm会爆long long我没注意到。。

#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const size_t MAXN = 1e7+5;
const int mod = 998244353;
char isnp[MAXN], miu[MAXN];
int pcn, pri[MAXN], mm[MAXN];
int _M1[MAXN], _F1[MAXN];
map<lld,lld> _M2, _F2;

void init_prime()
{
    miu[1] = mm[1] = _M1[1] = _F1[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i])
        {
            miu[i] = -1;
            mm[i] = -2;
            pri[pcn++] = i;
        }

        for (int j = 0; j < pcn; j++)
        {
            int k = i * pri[j];
            if (k >= MAXN) break;
            isnp[k] = 1;
            if (i % pri[j] == 0)
            {
                miu[k] = 0;
                mm[k] = ((i/pri[j])%pri[j]==0) ? 0 : mm[i/pri[j]];
                break;
            }
            else
            {
                miu[k] = -miu[i];
                mm[k] = -2*mm[i];
            }
        }

        _M1[i] = (_M1[i-1] + miu[i]) % mod;
        _F1[i] = (_F1[i-1] + mm[i]) % mod;
    }
}

lld M(lld n)
{
    if (n < MAXN) return _M1[n];
    else if (_M2.count(n)) return _M2[n];

    lld ans = 1;
    for (lld k = 2, fk; k <= n; k = fk+1)
    {
        fk = n / (n/k);
        ans -= (fk-k+1)*M(n/k)%mod;
    }

    ans = (ans % mod + mod) % mod;
    return _M2[n] = ans;
}

lld F(lld n)
{
    if (n < MAXN) return _F1[n];
    else if (_F2.count(n)) return _F2[n];

    lld ans = M(n);
    for (lld k = 2, fk; k <= n; k = fk+1)
    {
        fk = n / (n/k);
        ans -= (fk-k+1)*F(n/k)%mod;
    }

    ans = (ans % mod + mod) % mod;
    return _F2[n] = ans;
}

int main()
{
    init_prime();
    lld n; scanf("%lld", &n);
    lld ans = 0;

    for (lld k = 1, fk; k <= n; k = fk+1)
    {
        fk = n / (n/k);
        ans += (((n/k)%mod)*((n/k)%mod))%mod * (F(fk)-F(k-1)) % mod;
    }

    ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

Problem G – 排列

简单题,过。

Camp Day2 Div2

Problem J – Cosmis Cleaner

这题是个三维的计算几何,需要比较强的微积分知识。不过现场还是推了球缺公式的:

V(h,r) = \int_h^r \pi(r^2-x^2)dx = \frac{2\pi}3r^3-\pi r^2h+\frac\pi3h^3

其中 h 为球心到切割屏幕的距离。另外很容易得到两球交平面解析式与点到平面距离公式:

d_0=\frac{|Ax_0+By_0+Cz_0+D|}{\sqrt{A^2+B^2+C^2}}

然后根据球在空间中的不同位置进行分类讨论即可。

ans_n = \begin{cases}0, & 球在区域外 \\ V(-r_n, r_n), & 球在区域内 \\ V(h_0,r_0)+V(d,r_n), & 球一大半在外 \\ V(h_0,r_0)+V(-d,r_n), & 球一大半在内 \end{cases}

其中 h_0 为清除区域球心到交面距离,d 为被切割的球到交面的距离。

Problem A – Erase Numbers II

即选择两个数字,使得两者以字符串连接的形式得到的数字最大。

为了使数字最大,那么选取的数字必然是长度最长的两个。而且,最大的数字一定会被选到,因为:如果最大的数字在拼接数字的前部,那么没有比前部更大的;如果最大的数字在拼接数字的后部,那么当前部取最大时没有比后部更大的。

那么,我可以忽略另外一个数字的长度第二长条件,假装不知道的给最大的数和另外所有的数来一次拼接,用sprintf和sscanf再带上unsinged long long就可以完成一个 O(n) 的贪心。

比赛时的锅:

  • 队友给出了一个分类讨论的思想,然后写的比较混乱。
  • 后期有了这种贪心的思想的时候却不知20位数字如何比较大小,没有意识到ull和int128的可行性,然后就用strcmp演自己了。

Problem B – Erase Numbers I

利用后缀数组转化为一个字符串匹配问题,将整个大的连接串分割为三个部分。

但是目前还不太会字符串的有关内容QAQ寒假回去一定会恶补!

Camp Day1 Div2

CCPC Wannafly Winter Camp 自闭总结系列

Problem B – 吃豆豆

当时确实有想到将时间 t 作为一维,但是由于不敢确定 t 的范围,所以换了种思路。

dp[c][x][y] 为吃到 c 颗豆豆并且当前坐标在 (x,y) 时的时间。那么它可以由吃到 c-1 颗豆豆时的算法转移过来,大概是这样的一个公式:

dp[c][x][y] = \min\left\lbrace dp[c-1][x’][y’]+|x’-x|+|y’-y|+\Delta t, dp[c-1][x][y]+T[x][y]\right\rbrace

其中 \Delta t(x,y) 处豆豆产生时间的一个取整。当然了,c=1 和最后实际答案需要一个简单的转移。实际上这个吃到正好 c 颗的说法是不准确的,因为可以在前来的路上吃到更多的豆豆,但是,如果可以吃到更多的豆豆,那么这个值会存在吃到实际豆豆数的那个状态里。描述应该改为“吃到至少 c 颗豆豆”。时间复杂度是 O(Cn^2m^2),可以说是很糟糕了。

那么最原始的思路便是处理 dp[t][x][y] 了。可以从问题的实际意义也就是上下左右移动和不移动看出来:

dp[t][x][y] = \min\left\lbrace dp[t-1][x’][y’] + \left[T[x][y]\% t==0\right] \right\rbrace

利用这个公式,可以去做倍增来达到div1的 10^{18} 数量级。这类题我将在之后认真研究,虽然有点咕的欲望但是我会找人监督我的!

在做这道题的过程中,出现了以下的锅:

  • 由于没弄准确delta的意义,加错括号位置了。
  • 没有注意到第一次处理时的公式写法,导致了一个鬼畜错误。

记录下来。

Problem C – 拆拆数

这题一开始简单设置了几个样例,计算了一下,然后猜的结论:互质是 1 组,不互质是 2 组。当时想,如果能够构造出来,那么就相当于证明了这一猜想的正确性。可惜想偏了,在往 \gcd(A,B) 的方向想。

这题的正确证明需要用到一个性质:100 以内的素数有很多个,相乘之后超过 10^{18}。由于 AB 都不超过这个范围,不论有没有超过 100 的素因子,那么必然存在一个 100 以内的素数 p,那么 p \nmid A \wedge p\nmid B

所以,构造的方案是 (a_1, a_2, b_1, b_2)=(p, A – p, B – p, p) 即可。其中证明只需要用到 \gcd(a,b)=\gcd(a-b,b)

那么没做出来的锅:

  • 当时脑子里已经全是最大公约数构造,思路偏了。

Problem F – 爬爬爬山

挖山嘛,由于体力的势能那样的意义,其实只要把山挖到零势能面就可以啦,不需要继续往下挖。这题模型很容易让人联想到最短路,并且是无负权的图。既然是无负权图,那么一定不会走出一个环,即不会走到某个点两次。由无负权最短路联想到 dijkstra,由每个点只能走到一次莫名其妙想到了…网络流拆点。(???什么鬼脑洞)那么,如果有了拆点这个操作,入点与出点之间连接的边的意义就很明显了:dls挖山的花费。如果最短路会经过这座山,也就是经过这座山的入点和出点,那么挖山的费用也就加入了最短路的cost。

其中,拆点的具体做法是这样的:

将所有入边连接到 i 号点,出边的起始点选为 i+n,然后在 ii+n 之间连一条挖山花费的边就好了。是把一个无向图通过拆点变成了一个有向图呢!运行 dijkstra 堆优化版本即可通过。

那么多WA很多发的锅:

  • 自己只有脑洞,却没有认真练习过做图论题,连现成用的熟悉的模板都找不到。
  • 队友拆点连边错误没有看出来。
  • 队友交代码前没有认真审阅,没有注意到爆int的可能,也因为他使用宏定义而没有立刻发现输入的问题。以后拒绝使用任何 #define

寒假的时候要对图论类题目进行专项练习,不能和之前抱学长大腿的时候只会数论组合那样了,要成为一个全面型的选手,不然有组合题也不会dp计算(雾),有图论计数也不知道怎么整一个生成函数(呜呜呜)。