JZTXT

2023冲刺国赛模拟 37.1

发布时间 2023-07-18 07:43:57作者: KafuuChinocpp

怎么会有人 UNR Day1 只有 30 分啊！

感觉最近对自己的考试策略产生了很大的怀疑，平时模拟赛都没有太注意时间的分配， UNR 一直在关注考试剩余时间，发现 2 小时内还没有切掉 T1 后直接索性放弃了；然而剩余 3 小时也没有写好应得的暴力。 Day2 T1 比较幸运的在 1 个半小时左右观察出一点性质，前后使用暴力验证、对拍，写正解又用去了 1 个小时，算下来完整的切掉 T1 需要 1 个小时。

今天的模拟赛用 40 分钟左右推好式子，然而暴力验证的时候发现假掉了。然后修改式子并暴力验证用掉了 40 分钟，之后又用 1 个小时左右优化复杂度，看着一个非常邪恶的式子组合意义很长时间才把复杂度做到 \(O(n\sqrt{n})\) ，然而大样例跑的飞快于是没有优化。简而言之就是用掉 \(2\) 个半小时才拿到 T1 的 75 分。

大概发现自己切掉一道自己能力范围内，但并非很水的题需要 2 个小时到 2 个半小时，也就是国赛能留下的思考 T2, T3 的时间可能只有 2 个半小时左右。那么如果一场考试中存在两道本应切掉的题的话，我大约一定会寄掉吧。

然而国赛已经很近了，想要提高思考效率或者写/调代码效率几乎不可能了，所以想要找到一种最为合理的时间安排。发现大家考试几乎也是在 T1 上花去大部分时间，想尽办法切掉 T1 。自己省选之前的策略几乎就是想尽办法取得一道题的部分分，正式比赛的代码几乎全部都是数据点分治，很少能够写出一道题的正解，然而最后的结果实际上不会很差。不过清北营的考试在 Day2 中采取了比较激进的策略，最后几乎保龄。

所以哪种策略会更好一些啊！啊！啊！啊！啊！啊！啊！啊！

T1 数叶子

推销一下自己的诡异做法。

考虑求解数组 \(f(x)\) 表示在树中选择 \(x\) 条边，考虑一个点 \(i\) 对 \(f(x)\) 的贡献，不难发现贡献为 \(deg_i\binom{n-deg_i-1}{x-1}\) ，考虑 \(f(x)\) 对答案贡献的系数，通过枚举区间长度可以得到 \(x!(n-1-x)!\sum_{k=x}^{m}\binom{k}{x}\binom{m-k}{n-1-x}(m-k+1)\) ，思考这个式子后半部分的组合意义，发现这相当于给定长度为 \(m\) 的序列，首先分成两半，在前面选择 \(x\) 个元素，后面选择 \(n-1-x\) 个元素，贡献系数为后面序列长度 \(+1\) ，尝试构造一个长度为 \(m+1\) 的序列，首先分成两半，在前面选择 \(x\) 个元素，后面选择 \(n-x\) 个元素，在 \(n-x\) 个选择一个删去，这个过程的方案数为 \(\binom{m+2}{n+1}(n-x)\) ，因此上述式子等于 \(x!(n-1-x)!\binom{m+2}{n+1}(n-x)\) 。

直接写出答案的计算式：

\[\begin{aligned} ans &=\sum_{i=1}^{n}\sum_{x=1}^{n-1}deg_i\binom{n-deg_i-1}{x-1}x!(n-1-x)!\binom{m+2}{n+1}(n-x)\\ &=\binom{m+2}{n+1}\sum_{i=1}^{n}deg_i\sum_{x=1}^{n-1}(n-deg_i-1)^{\underline{x-1}}x(n-x)!\\ &=\binom{m+2}{n+1}\sum_{i=1}^{n}deg_i\sum_{x=1}^{n-1}\tfrac{(n-deg_i-1)!}{(n-deg_i-x)!}(n-x)!x\\ &=\binom{m+2}{n+1}\sum_{i=1}^{n}deg_i(n-deg_i-1)!\sum_{x=1}^{n-1}(n-x)^{\underline{deg_i}}x \end{aligned} \]

后面部分是关于 \(x\) 的 \(deg_i+2\) 次多项式，可以拉插计算。

复杂度 \(O(n)\) 。

code 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int max1 = 1e6;
const int mod = 1004535809;

int n, m, deg[max1 + 10];

int inv[max1 + 10], fac[max1 + 10], ifac[max1 + 10];

int C ( int n, int m )
{
    if ( n < m || n < 0 || m < 0 )
        return 0;
    return 1LL * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int Map[max1 + 10], y[max1 + 10];

int Down ( int x, int p )
{
    if ( x - p < 0 )
        return 0;
    
    return 1LL * fac[x] * ifac[x - p] % mod;
}

int Lagrange ( int deg )
{
    if ( Map[deg] != -1 )
        return Map[deg];
    
    int ans = 0;
    y[0] = 0;
    for ( int x = 1; x <= deg + 2; x ++ )
        y[x] = (y[x - 1] + 1LL * x * Down(n - x, deg)) % mod;

    if ( deg >= n - 3 )
        ans = y[n - 1];
    else
    {
        for ( int x = 0; x <= deg + 2; x ++ )
        {
            int v = 1LL * Down(n - 1, deg + 3) * inv[n - 1 - x] % mod;

            v = 1LL * v * ifac[x] % mod * ifac[deg + 2 - x] % mod;

            if ( (deg + 2 - x) & 1 )
                v = mod - v;

            ans = (ans + 1LL * v * y[x]) % mod;
        }
    }

    return Map[deg] = ans;
}

int main ()
{
    freopen("leaf.in", "r", stdin);
    freopen("leaf.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for ( int i = 2, u, v; i <= n; i ++ )
    {
        scanf("%d%d", &u, &v);
        ++deg[u];
        ++deg[v];
    }

    inv[1] = 1;
    for ( int i = 2; i <= n + 5; i ++ )
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for ( int i = 1; i <= n + 5; i ++ )
        fac[i] = 1LL * fac[i - 1] * i % mod, 
        ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
    
    memset(Map + 1, -1, sizeof(int) * n);

    int val = ifac[n + 1], ans = 0;

    for ( int i = 1; i <= n + 1; i ++ )
        val = 1LL * val * (m + 3 - i) % mod;

    for ( int i = 1; i <= n; i ++ )
    {
        ans = (ans + 1LL * Lagrange(deg[i]) * deg[i] % mod * fac[n - 1 - deg[i]]) % mod;
    }
    
    ans = 1LL * ans * val % mod;

    printf("%d\n", ans);

    return 0;
}

T2 多边形

二分答案 \(R\) ，如果存在合法的多边形，那么一定存在一个满足其所有边与半径为 \(R\) 的圆相切，考虑如何判断一个点在多边形外，我们从当前点向圆做切线，如果两条切线对应区间内存在一个多边形与圆的切点，那么点在多边形外，此时问题变成了覆盖 \(n\) 个区间需要的最小点数量，直接枚举第一个点的位置，后面的贪心选取即可。

简单进行优化，我们将环倍长连接成链，预处理当前区间右端点被选择后第一个需要处理的区间，容易发现只需要枚举起点在哪个区间，然后向后跳 \(m\) 次，检查经过区间总数是否大于等于 \(n\) 即可，简单倍增可以做到 \(O(n\log n)\) 。

code 
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int max1 = 1e5;
const double pi = acos(-1), eps = 1e-8;

int n, m;

struct Point
{
    int x, y;
    double dis, angle;
}p[max1 + 5];

struct Segment
{
    double L, R;

    Segment () {}
    Segment ( double __L, double __R )
        { L = __L, R = __R; }

    bool operator < ( const Segment &A ) const
        { return R < A.R; }
}seg[max1 * 2 + 5];

int father[max1 * 2 + 5][20];
int cnt;

bool Check ( double R )
{
    cnt = 0;

    for ( int i = 1; i <= n; i ++ )
    {
        double delta = acos(R / p[i].dis);

        seg[++cnt] = Segment(p[i].angle - delta, p[i].angle + delta);
        seg[++cnt] = Segment(p[i].angle - delta + pi + pi, p[i].angle + delta + pi + pi);
    }

    sort(seg + 1, seg + 1 + cnt);

    int now = 1;
    for ( int i = 1; i <= cnt; i ++ )
    {
        while ( now <= cnt && seg[now].L <= seg[i].R )
            ++now;
        
        father[i][0] = now;
    }

    for ( int k = 0; k <= 19; k ++ )
        father[cnt + 1][k] = cnt + 1;

    for ( int k = 1; k <= 19; k ++ )
        for ( int i = 1; i <= cnt; i ++ )
            father[i][k] = father[father[i][k - 1]][k - 1];

    for ( int i = 1; i <= n; i ++ )
    {
        int x = i;
        for ( int j = 19; j >= 0; j -- )
            if ( (m >> j) & 1 )
                x = father[x][j];

        if ( x >= i + n )
            return true;
    }
    return false;
}

int main ()
{
    freopen("polygon.in", "r", stdin);
    freopen("polygon.out", "w", stdout);

    double L = 0, R = 1e10;

    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &p[i].x, &p[i].y);
        p[i].dis = sqrt(1LL * p[i].x * p[i].x + 1LL * p[i].y * p[i].y);
        p[i].angle = atan2(p[i].y, p[i].x);

        R = min(R, p[i].dis);
    }

    while ( R - L > eps )
    {
        double mid = 0.5 * (L + R);

        if ( Check(mid) )
            L = mid;
        else
            R = mid;
    }

    printf("%.8lf\n", L);

    return 0;
}

T3 树论

这里讲解 Delov 的做法。

考虑点分治，假设当前处理的点为 \(x\) ，那么我们需要求解 \(\sum_u\varphi(ux)(deep_u+deep_x)^K\) ，简单二项式展开有： \(\sum_{i=0}^{K}\binom{K}{i}deep_x^i\sum_{u}\varphi(ux)deep_u^{K-i}\) 。

考虑处理 \(\varphi(ux)\) ，设 \(x=p\times q\) ，其中 \(p\) 表示 \(x\) 的质因子集合的乘积，那么 \(\varphi(ux)=q\varphi(pu)\) ，设 \(g=\gcd(p, u)\) ，那么 \(\varphi(ux)=qg\phi(\tfrac{p}{g})\varphi(u)=q\sum_{d|g}\varphi(\tfrac{g}{d})\varphi(\tfrac{p}{q})\varphi(u)=q\sum_{d|g}\varphi(\tfrac{p}{d})\varphi(u)\) 。

那么我们需要求解的实际上为 \(\sum_{i=0}^{K}\binom{K}{i}deep_x^iq\sum_{d|p}\varphi(\tfrac{p}{d})\varphi(u)deep_u^{K-i}[d|u]\) 。

很容易使用点分治维护。

code 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int max1 = 1e5;
const int mod = 998244353;

int n, K;
vector <int> edge[max1 + 5];

bool is_not_prime[max1 + 5], is_prime_set[max1 + 5];
int prime[max1 + 5], total;
int phi[max1 + 5], prime_set[max1 + 5];

vector <int> d[max1 + 5];

bool vis[max1 + 5];
int siz[max1 + 5], root;

int binom[15][15];
int bin[max1 + 5][15], up[15], ans[15];

void Get_Prime ()
{
    phi[1] = 1; is_prime_set[1] = true;
    for ( int i = 2; i <= n; i ++ )
    {
        if ( !is_not_prime[i] )
        {
            prime[++total] = i;
            phi[i] = i - 1;
            is_prime_set[i] = true;
        }

        for ( int j = 1; j <= total && i * prime[j] <= n; j ++ )
        {
            int k = i * prime[j];

            is_not_prime[k] = true;

            if ( !(i % prime[j]) )
            {
                phi[k] = phi[i] * prime[j];
                is_prime_set[k] = false;
                break;
            }

            phi[k] = phi[i] * (prime[j] - 1);
            is_prime_set[k] = is_prime_set[i];
        }
    }

    for ( int i = 1; i <= n; i ++ )
        if ( is_prime_set[i] )
            for ( int k = 1; k * i <= n; k ++ )
                prime_set[k * i] = max(prime_set[k * i], i);

    for ( int i = 1; i <= n; i ++ )
        for ( int k = 1; k * i <= n; k ++ )
            d[k * i].push_back(i);

    return;
}

void Get_Size ( int now, int fa )
{
    siz[now] = 1;

    for ( auto v : edge[now] )
    {
        if ( v == fa || vis[v] )
            continue;
        
        Get_Size(v, now);
        siz[now] += siz[v];
    }
    return;
}

void Get_Root ( int now, int fa, int sum )
{
    bool is_root = true;

    for ( auto v : edge[now] )
    {
        if ( v == fa || vis[v] )
            continue;
        
        Get_Root(v, now, sum);

        if ( siz[v] > (sum >> 1) )
            is_root = false;
    }

    if ( sum - siz[now] > (sum >> 1) )
        is_root = false;
    
    if ( is_root )
        root = now;
    return;
}

void Insert ( int now, int depth, int opt )
{
    int power = 1;
    for ( int i = 0; i <= K; i ++ )
    {
        for ( auto x : d[prime_set[now]] )
            bin[x][i] = (bin[x][i] + 1LL * opt * phi[now] % mod * power) % mod;

        power = 1LL * power * depth % mod;
    }
    return;
}

void Calc ( int now, int depth )
{
    int p = prime_set[now], q = now / prime_set[now];

    memset(up, 0, sizeof(int) * (K + 1));

    for ( int i = 0; i <= K; i ++ )
        for ( auto x : d[p] )
            up[i] = (up[i] + 1LL * q * phi[p / x] % mod * bin[x][i]) % mod;
    
    int power = 1;
    for ( int i = 0; i <= K; i ++ )
    {
        for ( int j = 0; i + j <= K; j ++ )
            ans[i + j] = (ans[i + j] + 1LL * binom[i + j][i] * power % mod * up[j]) % mod;

        power = 1LL * power * depth % mod;
    }
    return;
}

void Update ( int now, int fa, int depth, int opt )
{
    Insert(now, depth, opt);

    for ( auto v : edge[now] )
    {
        if ( v == fa || vis[v] )
            continue;

        Update(v, now, depth + 1, opt);
    }
    return;
}

void Query ( int now, int fa, int depth )
{
    Calc(now, depth);

    for ( auto v : edge[now] )
    {
        if ( v == fa || vis[v] )
            continue;
        
        Query(v, now, depth + 1);
    }
    return;
}

void Dfs ( int now )
{
    vis[now] = true;

    for ( auto v : edge[now] )
    {
        if ( vis[v] )
            continue;
        
        Update(v, now, 1, 1);
    }

    Insert(now, 0, 1);

    Calc(now, 0);

    for ( auto v : edge[now] )
    {
        if ( vis[v] )
            continue;

        Update(v, now, 1, mod - 1);
        Query(v, now, 1);
        Update(v, now, 1, 1);
    }

    for ( auto v : edge[now] )
    {
        if ( vis[v] )
            continue;
        
        Update(v, now, 1, mod - 1);
    }

    Insert(now, 0, mod - 1);

    for ( auto v : edge[now] )
    {
        if ( vis[v] )
            continue;

        Get_Size(v, now); Get_Root(v, now, siz[v]); Dfs(root);
    }
    return;
}

int main ()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);

    scanf("%d%d", &n, &K);
    for ( int i = 2, u, v; i <= n; i ++ )
    {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    Get_Prime();

    binom[0][0] = 1;
    for ( int i = 1; i <= K; i ++ )
    {
        binom[i][0] = 1;
        for ( int j = 1; j <= i; j ++ )
            binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod;
    }

    Get_Size(1, 0); Get_Root(1, 0, siz[1]); Dfs(root);

    for ( int i = 0; i <= K; i ++ )
        printf("%d\n", ans[i]);

    return 0;
}