2.20 JLU 寒假模拟赛

Problem A – 写文案

与此题相似的还有最近 CodeForces Round #540 (Div, 3) – D2Educational Codeforces Round 60 (Div. 2) – C

二分解法

本题需要求 v 的最小值,并且要求 f(v) \ge n

f(v) = \sum_{i=0}^\infty \left\lfloor\frac{v}{k^i}\right\rfloor

考虑这个函数的单调性,非常容易发现,f(v) 随着 v 的增大而增大。直接二分第一个 f(v) \ge n时的 v 即可。可以尝试用这种思路去做上面两题。

#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
int n, k;

int check(int i)
{
    lld sa = 0, sb = i;
    while (sb)
        sa += sb, sb /= k;
    return sa >= n ? 1 : -1;
}

int solve()
{
    if (check(1)==1) return 1;
    int l = 1, r = 1e9+7, m;

    while (r-l>1)
    {
        m = (l+r)>>1;
        if (check(m)==1)
            r = m;
        else
            l = m;
    }

    return r;
}

int main()
{
    scanf("%d %d", &n, &k);
    printf("%d\n", solve());
    return 0;
}

小范围暴力做法

可以发现,答案一定大于等于 n – \lfloor n / k\rfloor – 1,剩余答案大约在 O(\log n) 的范围内,暴力判断即可。但是此做法似乎无法通过提到的两题。

Problem B – 摆石子

动态规划解法

dp[n][m] 表示加入前 n 种颜色后,长度为 m 的排列有多少种方案。那么有

dp[i][j] = \sum_{k=0}^{j} C_j^k dp[i-1][j-k]

其中 1 \le i \le n, 0 \le j \le \sum_{p=1}^ia_p,如果预处理了组合数,那么总的时间复杂度为 O(\prod_{1 \le i \lt j \le n}a_i a_j) \le 10^8,并且是多组测试样例,15秒,是可以做的。

生成函数解法

由于所求的是排列型生成函数,所以考虑排列型生成函数。对于第 i 种颜色,对于长度为 k 的排列,方案数总为 1,其生成函数为 C_i(x),总生成函数为 B(x),即有。

B(x) = \prod_{i=1}^n C_i(x) = \prod_{i=1}^n \sum_{k=0}^{a_i} \frac{x^k}{k!} = \sum_{k=0}^m b_k \frac{x^k}{k!}

那么最后答案就是 \sum_{i=1}^k b_k。如果采用直接暴力多项式乘法,复杂度同上,但是常数好像小一点,维护起来也比较简单;另外如果遇到这种1e9+7的取模多项式乘法,可以考虑用拆系数FFT来做。

#include <vector>
#include <cstdio>
#include <algorithm>
typedef long long lld;
using namespace std;
const int MOD = 1e9+7;
int a[110];
const int MAXN = 1e4+5;
int inv[MAXN], invs[MAXN], fac[MAXN];

void init()
{
    inv[0] = invs[0] = fac[0] = 1;
    inv[1] = invs[1] = fac[1] = 1;

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

vector<int> conv(vector<int> &a, vector<int> &b)
{
    vector<int> ans(a.size()+b.size()-1, 0);

    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < b.size(); j++)
        {
            ans[i+j] = int((ans[i+j] + 1LL * a[i] * b[j]) % MOD);
        }
    }

    return ans;
}

int main()
{
    int n, cas = 0; init();

    while (scanf("%d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        sort(a, a+n);
        vector<int> fx(1,1), gx(1,1);

        for (int i = 0; i < n; i++)
        {
            while (gx.size() <= a[i])
                gx.push_back(invs[gx.size()]);
            vector<int> fgx = conv(fx, gx);
            fx = fgx;
        }

        int ans = 0;
        for (int i = 1; i < fx.size(); i++)
            ans = (ans + 1LL * fx[i] * fac[i]) % MOD;
        printf("Case %d: %d\n", ++cas, ans);
    }

    return 0;
}

Problem C – 算数字

简单筛选出2~10000的素数,保存到一个连续数组中。暴力求解;或者维护一个长度为10000的数组,表示对应标号的方案数,然后枚举连续数组的开头 i 和结尾 j 以计数。

#include <cstdio>
typedef long long lld;
using namespace std;
const int MAXN = 1e4+5;
int pri[MAXN], pcn, qzh[MAXN];
int cnt[MAXN];
bool isnp[MAXN];

void init_prime()
{
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i]) pri[pcn++] = i;
        for (int j = 0; j < pcn; j++)
        {
            if (i*pri[j] >= MAXN) break;
            isnp[i*pri[j]] = 1;
            if (i%pri[j]==0) break;
        }
    }

    for (int i = 1; i <= pcn; i++)
        qzh[i] = qzh[i-1] + pri[i-1];
    for (int i = 0; i < pcn; i++)
        for (int j = i+1; j <= pcn; j++)
            if (qzh[j]-qzh[i] < MAXN)
                cnt[qzh[j]-qzh[i]]++;
            else break;
}

int main()
{
    init_prime();
    int n;
    while (scanf("%d", &n) == 1 && n)
        printf("%d\n", cnt[n]);
    return 0;
}

Problem D – 复制玩具

可以发现,y-1 就是原始玩具投入机器的次数。那么再简单判断一下克隆玩具的情况即可。

#include <bits/stdc++.h>
typedef long long lld;
using namespace std;

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);
    bool checked = true;
    if (y<1) checked = false;
    if ((x-y+1)%2) checked = false;
    if (x < y-1) checked = false;
    if (y == 1 && x != 0) checked = false;
    printf(checked ? "Yes\n" : "No\n");
    return 0;
}

Problem E – 蛙跳

k 的奇偶,计算左跳右跳次数即可。

#include <cstdio>
typedef long long lld;
using namespace std;

int main()
{
    int t; lld a, b, k, ans;
    scanf("%d", &t);

    while (t--)
    {
        scanf("%lld %lld %lld", &a, &b, &k);
        ans = (a-b)*(k/2) + a*(k%2);
        printf("%lld\n", ans);
    }

    return 0;
}

Problem F – 地铁

这是一个图论题啦,感兴趣的同学可以去学一下图论中的最短路和最小生成树。

两点之间线段最短,然后再把同一条地铁线上地铁站之间的距离除以4加入图中,跑一遍最短路,最后将路程的米转换为分钟。

由于这是非负权完全图,直接使用最原始的 dijkstra 算法,复杂度为 O(V^2)。输入的时候要注意技巧,利用scanf的返回值。

#include <map>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
typedef long long lld;
using namespace std;
const int MAXV = 220;
double c[MAXV][MAXV];
double dis[MAXV];
bool vis[MAXV];
int n;

struct point
{
    int x, y;
    point(int _x = 0, int _y = 0) { x = _x, y = _y; }
    bool operator==(const point &b) const { return x==b.x && y==b.y; }
    bool operator<(const point &b) const { return (x==b.x && y<b.y) || (x<b.x); }

    double operator-(const point &b)
    {
        int xx = x - b.x;
        int yy = y - b.y;
        return sqrt(1.0*xx*xx + 1.0*yy*yy);
    }
};

map<point,int> V;
map<int,point> V2;

int get_id(const point &wtf)
{
    if (V.count(wtf)) return V[wtf];
    V[wtf] = ++n; V2[n] = wtf; return n;
}

bool input_station()
{
    int x1, y1, x2, y2;
    if (scanf("%d %d", &x1, &y1) != 2) return false;

    while (scanf("%d %d", &x2, &y2) == 2 && ~x2 && ~y2)
    {
        point p1(x1,y1), p2(x2,y2);
        int i1 = get_id(p1), i2 = get_id(p2);
        double dis = min((p1-p2)/4, c[i1][i2]);
        c[i1][i2] = c[i2][i1] = dis;
        x1 = x2, y1 = y2;
    }

    return true;
}

void dijkstra()
{
    dis[1] = 0;

    for (int i = 1; i <= n; i++)
    {
        double minc = c[0][0];
        int p = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && minc > dis[j])
                minc = dis[j], p = j;
        vis[p] = true;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] > dis[p] + c[p][j])
                dis[j] = dis[p] + c[p][j];
    }
}

int main()
{
    int xh, yh, xs, ys;
    scanf("%d %d %d %d", &xh, &yh, &xs, &ys);
    memset(c, 0x55, sizeof(c));
    memset(dis, 0x55, sizeof(dis)); // double INF in memory
    point h(xh,yh), s(xs,ys);
    V[h] = ++n; V2[n] = h;
    V[s] = ++n; V2[n] = s;
    while (input_station());

    for (int i = 1; i <= n; i++)
    {
        for (int j = i+1; j <= n; j++)
        {
            double dis = min(c[i][j], V2[i]-V2[j]);
            c[i][j] = c[j][i] = dis;
        }
    }

    dijkstra();
    printf("%.0f\n", dis[2]*6/1000+1e-8);
    return 0;
}

Problem G – 半素数

先筛选出1-3000的所有素数,保存到一个连续数组中,然后对1-3000的每个数字,将每个素数进行试除,如果满足素因子个数仅为2的条件,那么记录下来,最后统计一下,结束。

#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const int MAXN = 1e4+5;
int pri[MAXN], pcn, qzh[MAXN];
int cnts[MAXN];
bool isnp[MAXN];

void init_prime()
{
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i]) pri[pcn++] = i;
        for (int j = 0; j < pcn; j++)
        {
            if (i*pri[j] >= MAXN) break;
            isnp[i*pri[j]] = 1;
            if (i%pri[j]==0) break;
        }
    }

    for (int i = 1; i <= 3000; i++)
    {
        int cnt = 0;
        for (int j = 0; j < pcn; j++)
            if (i % pri[j] == 0)
                cnt++;
        if (cnt == 2)
             cnts[i]++;
    }

    for (int i = 1; i <= 3000; i++)
        cnts[i] = cnts[i]+cnts[i-1];
}


int main()
{
    init_prime();
    int t;
    scanf("%d", &t);
    printf("%d\n", cnts[t]);
    return 0;
}

Problem H – 骨牌摆放

一个长度为 n 的排列,可以由长度为 n-1 的排列后面添加一个 |,或者由长度为 n-2 的排列后面添加 = 得到。那么 F_n = 2F_{n-2} + F_{n-1},递推计算就好了。

由于没有取模,而且 long long 也存不下,所以考虑手动写个十进制加法算法或者使用 JAVA 的大数类即可。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        BigInteger[] f = new BigInteger[251];
        f[0] = f[1] = BigInteger.ONE;
        for (int i = 2; i < 251; i++)
            f[i] = f[i-1].add(f[i-2]).add(f[i-2]);
        Scanner cin = new Scanner(System.in);
        while (cin.hasNextInt())
            System.out.println(f[cin.nextInt()]);
    }

}

Problem I – 几点了

根据每个字符自己的特点,进行超级大的分类讨论好了。(大雾)

#include <cstdio>
typedef long long lld;
using namespace std;
char screen[22][22];

int check(int x)
{
    if (screen[1][x+3] == '.' && screen[4][x] == '.')
        return 5;
    if (screen[1][x+3] == '.' && screen[4][x] == 'X')
        return 6;
    if (screen[0][x+1] == '.' && screen[3][x+1] == '.')
        return 1;
    if (screen[0][x+1] == '.' && screen[3][x+1] == 'X')
        return 4;
    if (screen[0][x+1] == 'X' && screen[3][x+1] == '.' && screen[6][x+1] == '.')
        return 7;
    if (screen[3][x+1] == '.')
        return 0;
    if (screen[4][x+3] == '.')
        return 2;
    if (screen[1][x] == '.')
        return 3;
    if (screen[4][x] == '.')
        return 9;
    return 8;
}

void solve()
{
    for (int i = 0; i < 7; i++)
        scanf("%s", screen[i]);
    printf("%d", check(0));
    printf("%d", check(5));
    printf(":");
    printf("%d", check(12));
    printf("%d", check(17));
    printf("\n");
}

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

Problem J – 匹配字

这题是询问,有多个模板字符串,他们中有多少个在目标字符串中出现。

这个算法叫做 Aho-Corasick automaton,中文名叫做 AC自动机,推荐阅读 这篇文章 来了解它的算法内容。

Sparse Table

稀疏表,又称ST表,预处理 O(n \log n),查询 O(1)

st[i][j] 表示在数组中,[i,i+2^j-1] 区间的最值。

当我们需要查询 [L,R] 的最值时,由于 R-L+1 可能不是正好 2^j 形式,那么我们可以考虑用某个 j,查询 [L,L+2^j-1][R-2^j+1,R],并使这两个区间交叠。

int a[1010];
int st[1010][12];

void init(int n)
{
    for (int i = 0; i < n; i++)
        st[i][0] = a[i];
    for (int j = 1; (1<<j) <= n; j++)
        for (int i = 0; i+(1<<j)-1 < n; i++)
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}

int search(int l, int r)
{
    int k = int(log2(r-l+1.0));
    return min(st[l][k], st[r-(1<<k)+1][k]);
}

并且由代码可以看出,它还可以处理区间最大值/最值坐标等。

Sub-cycle Graph

是时候回顾一波青岛站打铁时没想出来的题了QAQ。

题目传送门:ZOJ4069

求由 n 个点组成 k 条链,形成的所有图的方案数,对 1e9+7 取模。

首先,我们先考虑由 m 个点形成 1 条链的不同方案个数。显然对任意排列,去除倒过来的那个就行了。将方案数记为 l_m,则可以得到

l_m = \begin{cases} 1, & m=1 \\ \frac{m!}{2}, & m>1 \end{cases}

那么似乎接下来就是求它的生成函数了。在这里我们选择它的指数型生成函数。

L(x) = \sum_{m=1}^\infty l_m \frac{x^m}{m!} = \frac{1}{2}\left(2x+x^2+x^3+\cdots\right) = x\left(1-\frac{x}{2}\right)\frac{1}{1-x}

那么现在取 k 条链,我们可以计算出

A_k(x) = \sum_{n=1}^\infty a_{n,k} \frac{x^n}{n!} = \left[L(x)\right]^k = x^k \left(1-\frac{x}{2}\right)^k \left(\frac{1}{1-x}\right)^k

由于这 k 条链之间是不考虑先后关系的,所以

b_{n,k} = \frac{a_{n,k}}{k!}

就是最终的答案。

考虑一下题目是多测的,而且测试样例数高达 T = 2 \times 10^4,是不能进行FFT的。

我们可以发现

\left(1-\frac{x}{2}\right)^k = \sum_{s=0}^k C_k^s \left(-\frac{1}{2}\right)^s x^s

是可以用二项式定理做出来的。

然后考虑一下,后面的 1/(1-x)^k 与前面这项进行卷积,其实就相当于对前面的数列进行了 k 次前缀和。

emmmmm,看到网上有个dalao说

求k次前缀和的第m项,想必现在是个人都应该会了

突然自闭.jpg。然后推了推。假设这个数列原来是

\lbrace x_0, x_1, x_2, \cdots \rbrace

对它进行 k+1 次前缀和,它会变成

\lbrace C_k^k x_0, C_{k+1}^k x_0 + C_k^k x_1, C_{k+2}^k x_0 + C_{k+1}^k x_1 + C_k^k x_2, \cdots \rbrace

即第 n 项为

\sum_{i=0}^n C_{k+i}^k x_{n-i}

单次询问复杂度是 O(m) 的,那么现在可以开始写代码啦!

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
lld fac[MAXN], inv[MAXN], invs[MAXN];

inline void init()
{
    fac[0] = invs[0] = 1;
    fac[1] = inv[1] = invs[1] = 1;

    for (int i = 2; i < MAXN; i++)
    {
        fac[i] = i * fac[i-1] % MOD;
        inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD;
        invs[i] = inv[i] * invs[i-1] % MOD;
    }
}

inline lld C(int n, int k)
{
    if (n < k) return 0;
    return fac[n] * invs[k] % MOD * invs[n-k] % MOD;
}

void solve()
{
    int n, m, k;
    scanf("%d %d", &n, &m);

    if (m > n)
    {
        printf("0\n");
    }
    else if (m == n)
    {
        printf("%lld\n", fac[n-1]*inv[2]%MOD);
    }
    else
    {
        k = n - m;
        lld ans = 0, inv2s = 1;

        for (int i = m; i >= 0; i--)
        {
            ans += C(k-1+i,i) * C(k, m-i) % MOD * inv2s % MOD;
            inv2s = inv2s * (MOD-inv[2]) % MOD;
        }

        ans = (ans % MOD + MOD) % MOD;
        ans = ans * fac[n] % MOD * invs[k] % MOD;
        printf("%lld\n", ans);
    }
}

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

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计算(雾),有图论计数也不知道怎么整一个生成函数(呜呜呜)。

数论筛小结

简单的整理了一下目前自己会的鬼畜东西QAQ

埃拉托斯特尼筛 / 普通筛

这个可能是小学课本就讲过的素数筛法吧。

每一个数(非1)的倍数一定是合数,那么把这些数字打上标记就可以了。

T(n) = O\left(\sum_{i=2}^{n}\left\lfloor\frac{n}{i}\right\rfloor\right) \approx O\left(\int_1^n\frac{n}{x}dx\right) = O(n \log n)

最大的问题是,一个数如果之前被枚举到了,那么对它的倍数进行枚举是无用的操作。如果我们对已经打过标记的数不再枚举它的倍数,那么我们的复杂度约为 O(n \log \log n)

那么为什么今天我要提它呢?因为。我们可以来大区间素数筛选啊!

考虑这样的一个问题:求出 [a,b] 内的所有素数,其中 a \le 10^9, b-a \le 10^6。显然不能用线性筛。

我们可以发现这样的一个性质:[a,b] 中的每个合数,最大质因子一定不会超过 \sqrt{b}

那么,这个筛就可以拿去用啦~

欧拉筛 / 线性筛

考虑某个数出现平方项后不再筛选它,就有了欧拉筛法。

对于任意一个整数 n,如果它有一些的质数幂次超过1,那么它会被最小的那个质数筛选到。

如果没有,那么它会被最大的质因子筛选到。

另外介绍一下积性函数的概念:

f 是定义在 Z^+ 上的函数,如果满足 gcd(n,m)=1 则有 f(n)f(m) = f(nm),那么称为它是积性函数。

常见的积性函数有:

  • 欧拉函数 \varphi(n) = \sum_{i=1}^n [gcd(i,n)=1]

  • 莫比乌斯函数 \mu(n) = (-1)^k\ or\ 0

  • 元函数 e(n) = [n=1]

  • 恒等函数 1(n) = 1

  • 单位函数 id(n) = n

  • 幂函数 id^k(n) = n^k

  • 除数函数 \sigma_k(n) = \sum_{d|n} d^k

  • 约数个数函数 d(n) = \sum_{d|n}1

  • 约数和函数 \sigma(n) = \sum_{d|n}d

我们在做素数筛选的时候,由于我们的分界条件很明显,以两个数是否互质为标准,于是我们可以顺便求出可乘函数的所有值。

欧拉筛法代码如下。并且,由于每个数只会被访问一次,所以我们认为它的时间复杂度是 O(n)​ 的。

char miu[MAXN], c[MAXN], isnp[MAXN];
int phi[MAXN], d[MAXN], pri[MAXN], pcn;

void init_prime()
{
    isnp[0] = isnp[1] = 1;
    miu[1] = phi[1] = d[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i])
        {
            pri[pcn++] = i;
            c[i] = 1;
            d[i] = 2;
            miu[i] = -1;
            phi[i] = i-1;
        }

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

狄利克雷卷积

f(n), g(n) 是积性函数,我们称
(f*g)(n)=\sum_{i\times j=n}f(i)g(j)
是这两个函数的狄利克雷卷积。很容易证明,f * g 依然是个积性函数。

那么,设 G=\lbrace f\ |\ f\ is\ multiplicative\ function\rbrace * 是按上述规则构成的运算,那么 (G, *) 构成了一个阿贝尔群,我们称这个群为积性函数的狄利克雷卷积群,其单位元就是 e(n)=[n=1]

列举群中的几个常见运算吧。

\mu * 1 = e

\varphi * 1=id

id * \mu = \varphi

1*1=d

\mu * d = 1

id * 1 = \sigma

id^k * 1 = \sigma_k

没错。其实在这个群中,\mu1 互为逆元。

杜教筛

显然对于积性函数 f(n) 和较大的 n \ge 10^{12},我们很难线性计算 S(n) = \sum_{i=1}^n f(n)

我们希望能找到一个 g(n),使得它们的狄利克雷卷积的求和尽可能方便地计算。
\sum_{k=1}^n \sum_{ij=k} g(i)f(j) = \sum_{i=1}^n\sum_{j=1}^{\lfloor n/i \rfloor}g(i)f(j) = \sum_{i=1}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

所以有
g(1)S(n) = \sum_{i=1}^n(f*g)(i) – \sum_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
显然后面那个东西是可以进行分块计算的。

假设我们对 g(n)(f*g)(n) 求和是线性的,那么计算的时间复杂度为

T(n) = O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{i}\right) + O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\right) \approx O\left(\int_0^{\sqrt{n}}\sqrt{\frac{n}{x}}dx\right) = O\left(n^\frac{3}{4}\right)

如果我们可以先用线性筛预处理出 S(n) 的前 n^\frac23 项,那么

T(n) = O\left(\sum_{i=1}^{n/k}\sqrt{\frac{n}{i}}\right) = O\left(\frac{n}{\sqrt{k}}\right) = O\left(n^\frac{2}{3}\right)

我们就可以 O(n^\frac23) 计算了。

例如对于莫比乌斯函数的前缀和与欧拉函数的前缀和,我们有

\begin{aligned} & M(n) = \sum_{d=1}^n\mu(d) = 1-\sum_{d=2}^nM\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\\\ & \phi(n) = \sum_{d=1}^n\varphi(d) = \frac{n(n+1)}2-\sum_{d=2}^n\phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\\\ & B(n) = \sum_{d=1}^nd\varphi(d) = \frac{n(n+1)(2n+1)}6-\sum_{d=2}^ndB\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{aligned}

洲阁筛

占坑

min_25筛

占坑