牛客多校第二场题解

B Cannon

题意：有一个两行、无限长的棋盘，第一行有 $a$ 个炮，第二行有 $b$ 个炮，求依次发生 $k$ 次吃炮事件的方案总数。

Subtask 1：无限制。

Subtask 2：考虑两行的执行顺序。

解法：考虑有 $n$ 个炮的情况。那么发生一次吃炮事件的方案数为 $2(n-2)$ ，由此可以推出发生 $m$ 次吃炮事件的方案数为 $\displaystyle 2^m \frac{(n-2)!}{(n-2-m)!}$ ，记位 $f_{n,m}$ 。

显然， $n,m$ 均大于 $2$ ，因而令 $x=n-2$ ， $y=m-2$ 。

因而我们可以发现，对于 Subtask 1，答案为 $g(k)=\displaystyle 2^k\sum_{i}{\dbinom{x+y}{i} f_{x,i} f_{y,k-i}}$ 。化简，可以得到原式等于 $\displaystyle g(k)=2^k \sum_{i}{\frac{k!}{i!(k-i)!}}\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}=2^k k! \sum_{i}\frac{n!}{i!(n-i)!}\frac{m!}{(k-i)!(m-(k-i))!}=2^k k! \sum_{i}{\dbinom{n}{i}}\dbinom{m}{k-i}$

考虑 $\displaystyle \sum_{i}{\dbinom{n}{i}}\dbinom{m}{k-i}$ ，其意义为在 $n$ 和 $m$ 件物品***选取 $k$ 件的方案总数，因而等于 $\dbinom{n+m}{k}$ 。因而 Subtask 1 的答案为 $2^k k! \dbinom{n+m}{k}$ 。

Subtask 2 就麻烦一些： $h(k)=\displaystyle \sum_{i}{f_{x,i}f_{y,k-i}}=2^k\frac{n!m!}{(n+m-k)!} \sum_{i}\dbinom{n+m-k}{i}$ 。

考虑 $\displaystyle \sum_{i}\dbinom{n+m-k}{i}$ 。此处需要用到步移算法，构建一个递推式。令 $S(n,m)=\displaystyle \sum_{i=0}^{m}\dbinom{n}{i}$ ， $\displaystyle S(n,m+1)=\sum_{i=0}^{m+1}\dbinom{n}{i}=\sum_{i=0}^{m}\dbinom{n}{i}+\dbinom{n}{m+1}$ ，即 $S(n,m+1)=S(n,m)+\dbinom{n}{m+1}$ 。

$S(n+1,m)=\sum_{i=0}^{m}\dbinom{n+1}{i}$ 。考虑 $\dbinom{n+1}{m}=\dbinom{n}{m}+\dbinom{n}{m-1}$ ，则 $S(n+1,m)=\sum_{i=0}^{m}\dbinom{n}{i}+\dbinom{n}{i-1}=2S(n,m)-\dbinom{n}{m}$ 。

回到我们这个题，我们尝试分析 $h(k)$ 。 $h(k)=2^{k+1}\frac{n!m!}{(n+m-k-1)!}(S(n+m-k,n)-S(n+m-k,n-k-1))$ ， $\displaystyle h(k+1)=2^{k+1}\frac{n!m!}{(n+m-k-1)!} (S(n+m-k-1,n)-S(n+m-k-1,n-k-2))$ 。由我们的递推式 $S(n,m-1)=S(n,m)-\dbinom{n}{m}$ 与 $S(n,m)=2S(n-1,m)-\dbinom{n-1}{m}$ 可知， $S(n+m-k,n)-S(n+m-k,n-k-1)=2S(n+m-k-1,n)-\dbinom{n+m-k-1}{n}-2S(n+m-k,n-k-2)+\dbinom{n+m-k-1}{n-k-1}+\dbinom{n+m-k-2}{n-k-2}$ 。

令 $p(k)=S(n+m-k,n)-S(n+m-k,n-k-1)$ ，边界条件 $p(x+y)=1$ ，则有 $p(k-1)=2p(k)-\dbinom{x+y-k}{x-k}-\dbinom{x+y-i}{x}$ 。

总体复杂度 $O(a+b)$ 。

#include <cstdio>
#include <algorithm>
using namespace std;
const long long mod = 1000000009LL;
int fac[10000005], invfac[10000005];
long long power(long long a,long long x)
{
    long long ans = 1;
    while(x)
    {
        if(x&1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
long long C(int x,int y)
{
    if(x<y || y<0)
        return 0;
    return (long long)fac[x] * (long long)invfac[y] % mod * (long long)invfac[x - y] % mod;
}
int p[10000005];
int f[10000005], g[10000005];
int qpow[10000005];
int main()
{
    fac[0] = 1;
    for (int i = 1; i <= 10000000;i++)
        fac[i] = (long long)fac[i - 1] * (long long)i % mod;
    invfac[10000000] = power(fac[10000000], mod - 2);
    invfac[0] = 1;
    for (int i = 10000000 - 1; i >= 1; i--)
        invfac[i] = (long long)invfac[i + 1] * (long long)(i + 1) % mod;
    qpow[0] = 1;
    for (int i = 1; i <= 10000000;i++)
        qpow[i] = qpow[i - 1] * 2ll % mod;
    int n, m;
    scanf("%d%d", &n, &m);
    int x = n - 2, y = m - 2;
    p[x + y] = 1;
    for (int i = x + y; i >= 1;i--)
        p[i - 1] = ((2ll * p[i] - C(x + y - i, x - i) - C(x + y - i, x)) % mod + mod) % mod;
    for (int i = 0; i <= x + y;i++)
    {
        f[i] = (long long)qpow[i] * fac[x + y] % mod * invfac[x + y - i] % mod;
        g[i] = (long long)qpow[i] * fac[x] % mod * fac[y] % mod * invfac[x + y - i] % mod * p[i] % mod;
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i <= x + y; i++)
    {
        ans1 ^= f[i];
        ans2 ^= g[i];
    }
    printf("%d %d", ans1, ans2);
    return 0;
}

这个题比较卡时间和空间，因而需要大量存储一些值，不能每次都调用逆元或者快速幂去计算。

F Girlfriend

题意：给定四个点 $A,B,C,D$ 与 $k_1,k_2$ ，求满足 $P$ 点在条件 $|PA|>k_1|PB|$ 与 $|PC|>k_2|PD|$ 约束下可行的总体积。

解法：考虑二维平面上的阿波罗尼兹圆，若有两定点 $A,B$ ，并给定常数 $k$ ，则其圆心 $O$ 满足的关系为 $\displaystyle \vec{AO}=\frac{k^2}{k^2-1} \vec{AB}$ ，半径为 $\displaystyle r=\frac{k}{k^2-1}|AB|$ 。在三维空间中，将整个图形绕 $AB$ 直线进行旋转，即可得到所求体积。剩下的就是求球体体积交了。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi = acos(-1);
struct node
{
    double x;
    double y;
    double z;
};
node operator *(double k,node a)
{
    return (node){k * a.x, k * a.y, k * a.z};
}
node operator +(node a,node b)
{
    return (node){b.x + a.x, b.y + a.y, b.z + a.z};
}
node operator -(node a,node b)
{
    return (node){a.x - b.x, a.y - b.y, a.z - b.z};
}
double dis(node a,node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
struct globe
{
    node a;
    double r;
};
globe cal(node a,node b,double k)
{
    globe ans;
    double distance = dis(a, b);
    node ab = b - a;
    ans.r = distance / (k * k - 1) * k;
    ans.a = (k / (k * k - 1) * k) * ab + a;
    return ans;
}
double uni(globe a, globe b)//求体积交模板
{
    //注意边界情况的讨论
    double distance = dis(a.a, b.a);
    if(distance>=a.r+b.r)
        return 0;
    if(distance<=fabs(a.r-b.r))
    {
        double r = min(a.r, b.r);
        return r * r * r * 4 / 3 * pi;
    }
    double t = (distance * distance + a.r * a.r - b.r * b.r) / (2.0 * distance);
    double h = sqrt((a.r * a.r) - (t * t)) * 2;
    double l1 = ((a.r * a.r - b.r * b.r) / distance + distance) / 2;
    double l2 = distance - l1;
    double x1 = a.r - l1, x2 = b.r - l2;
    double v1 = pi * x1 * x1 * (a.r - x1 / 3);
    double v2 = pi * x2 * x2 * (b.r - x2 / 3);
    return v1 + v2;
}
int main()
{
    int t;
    scanf("%d", &t);
    node a, b, c, d;
    double k1, k2;
    while(t--)
    {
        scanf("%lf%lf%lf", &a.x, &a.y, &a.z);
        scanf("%lf%lf%lf", &b.x, &b.y, &b.z);
        scanf("%lf%lf%lf", &c.x, &c.y, &c.z);
        scanf("%lf%lf%lf", &d.x, &d.y, &d.z);
        scanf("%lf%lf", &k1, &k2);
        globe e = cal(a, b, k1);
        globe f = cal(c, d, k2);
        printf("%.10lf\n", uni(e, f));
    }
    return 0;
}

G League of Legends

题意：给定 $n$ 个区间 $[a_i,b_i]$ ，将其分为 $k$ 组，并且要求每组公共区间长度不为 $0$ ，求 $k$ 组最大公共区间长度和。

解法：注意！此处一定要尝试先化简问题再求解！

首先对于有包含关系的区间，那么可以直接无条件并入，并取其较小区间，答案不会受到影响。

此时剩下的区间均为不相互包含的独立区间。

构造 DP 状态为 $f[i][j]$ ，表示前 $i$ 个人分 $j$ 组最大的公共娱乐时间。转移非常好写： $f[i][j]=\max_{k}\{ f[k][j-1]+w[k+1][i]\}$ 。其中， $w[i][j]$ 表示第 $i$ 个人到第 $j$ 个人的公共娱乐时间，该数组可由 $O(n^2)$ 的方法推出。但是如果经过上述排序、去重操作后，完全可以不需要进行这一操作。

考虑转移的条件： $b_k > a_i$ ，并且其公共娱乐时间为 $w[k+1][i]=b_k-a_i$ 。对于这种下界不断变化的 DP，一个常见的方法就是使用单调队列优化。在队首弹出队列时，按照 $a_i \leq b_k$ 的条件判定，相当于满足必须要存在区间；压入队列时，按照 $f_{k,i}+b_i$ 的单调性进行——因为后续的转移是从这里转移而来的，需要满足 $dp$ 值的单调性。

总体时间复杂度 $O(n^2)$ 。

#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
struct interval
{
    long long a;
    long long b;
    bool operator <(const interval &t)const
    {
        if(a==t.a)
            return b < t.b;
        return a < t.a;
    }
};
struct interval t[5005], q[5005];
bool cmp(long long x,long long y)
{
    return x > y;
}
int que[5005];
long long f[5005][5005];
long long len[5005];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++)
    {
        scanf("%lld%lld", &t[i].a, &t[i].b);
        t[i].b--;
    }
    sort(t + 1, t + n + 1);
    int tot = 0, big = 0;
    for (int i = 1; i <= n; i++)
    {
        while (tot && t[i].b <= q[tot].b)
        {
            len[++big] = q[tot].b - q[tot].a + 1;
            tot--;
        }
        q[++tot] = t[i];
    }
    sort(len + 1, len + big + 1, cmp);
    memset(f, 0xcf, sizeof(f));
    f[0][0] = 0;
    for (int j = 1; j <= k; j++)
    {
        int head = 0, tail = 0;
        for (int i = 0; i <= tot; i++)
        {
            while (head < tail && q[i].a > q[que[head] + 1].b)
                head++;
            if (head < tail)
                f[i][j] = f[que[head]][j - 1] + q[que[head] + 1].b - q[i].a + 1;
            while (head < tail && f[i][j - 1] + q[i + 1].b >= f[que[tail - 1]][j - 1] + q[que[tail - 1] + 1].b)
                tail--;
            que[tail++] = i;
        }
    }
    long long ans = f[tot][k];
    long long temp = 0;
    for (int i = 1; i <= big; i++)
    {
        temp += len[i];
        ans = max(temp + f[tot][k - i], ans);
    }
    printf("%lld", max(0ll, ans));
    return 0;
}

注意等号何时取得。

J Product of GCDs

题意：给定一个集合 $S$ ，求集合中全部大小为 $k$ 的子集的最大公约数之积，对给定模数取模。

解法：一个非常常见的方法是通过 $O(n\log n)$ 的复杂度找到全部以 $k$ 为因子的数的数目。

    for (int i = 2; i <= m;i++)
        for (int j = i * 2; j <= m; j += i)
            f[i] += f[j];//初始时，f[i] 为 i 的个数

当然还可以直接在这里进一步使用组合数直接替换：

    for (int i = 1; i <= m;i++)
        f[i] = C[f[i]][k];

但是直接这样算是不正确的：考虑集合 $\{2,4,6,8\}$ ， $k=2$ ，以 $2$ 做因子的数有 $4$ 个，但是并不能说以 $2$ 做最大公约数的集合就有 $\dbinom{4}{2}=6$ 个：因为还有一组是以 $4$ 作为最大公约数。因而我们要进行修正。

考虑对每一个质因子进行修正，进行容斥。首先有一个基础倍数 $\dbinom{f[p]}{k}$ ，但是还有一些更大的倍数，这个时候应该补上一倍的 $\dbinom{f[p^2]}{k}$ ，二倍的 $\dbinom{f[p^3]}{k}$ ，……， $m-1$ 倍的 $\dbinom{f[p^m]}{k}$ 。但是注意到我们在上一步是不分质数合数都进行了合并操作的，因而此时的 $\dbinom{f[p^2]}{k}$ 已经各包含了一份 $\dbinom{f[p^i]}{k}$ 。更严格化的说，是低次方已经是高次方的前缀和了，因而下一步只需要直接将各个次方的数字进行累加即可。

还有一点：因为次方数太大，因而需要取模。由费马小定理 $\displaystyle a^{\varphi(p)} \equiv a \mod p$ ，因而次方数需要对 $\varphi(p)$ 取模。考虑到正式步骤中也需要质数，因而可以预处理出 $\sqrt{p}$ 内的质数，来统计 $\varphi(p)$ 和质数。

轻微卡常。

#include <bits/stdc++.h>
using namespace std;
long long f[80005];
long long C[80005][35];
long long mod;
bool vis[10000005];
long long prime[10000005], tot;
//有点卡常所以用了快读
template<class T>inline void In(T&x)
{
    char c;T y=1;
    while(c=getchar(),!isdigit(c)&&c!=-1){if(c=='-')y=-1;}x=c-'0';
    while(c=getchar(),isdigit(c)){x=10*x+c-'0';}x*=y;
}
void sieves(int x)
{
    for (int i = 2; i <= x; i++)
    {
        if(!vis[i])
            prime[++tot] = i;
        for (int j = 1; j <= tot && i * prime[j] <= x;j++)
        {
            vis[i * prime[j]] = 1;
            if(i%prime[j]==0)
                break;
        }
    }
    return;
}
long long Phi(long long p)
//求欧拉函数
{
    long long x = p;
    for (int i = 1; i <= tot && prime[i] <= x; i++)
        if(x%prime[i]==0)
        {
            while(x%prime[i]==0)
                x /= prime[i];
            p = p / prime[i] * (prime[i] - 1);
        }
    if (x > 1)
        p = p / x * (x - 1);
    return p;
}
__int128 power(__int128 a, __int128 x)
{
    __int128 ans = 1;
    while(x)
    {
        if(x&1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
int main()
{
    sieves(10000000);
    int n, t, k, x;
    scanf("%d", &t);
    while(t--)
    {
        memset(f, 0, sizeof(f));
        In(n);
        In(k);
        In(mod);
        long long phi = Phi(mod);
        for (int i = 0; i <= n;i++)
            C[i][0] = 1;
        for (int i = 1; i <= n;i++)
            for (int j = 1; j <= min(i, k);j++)
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % phi;
        int m = 0;
        for (int i = 1; i <= n; i++)
        {
            In(x);
            f[x]++;
            m = max(m, x);
        }
        for (int i = 2; i <= m;i++)
            for (int j = i * 2; j <= m; j += i)
                f[i] += f[j];
        for (int i = 1; i <= m;i++)
            f[i] = C[f[i]][k];
        __int128 ans = 1;
        for (int i = 1; i <= tot && prime[i] <= m; i++)
        {
            printf("old:%d %lld\n", prime[i], f[prime[i]]);
            for (long long j = prime[i] * prime[i]; j <= m; j *= prime[i])
                f[prime[i]] = (f[prime[i]] + f[j]) % phi;
            printf("%d %lld\n", prime[i], f[prime[i]]);
            ans = (ans * power((__int128)prime[i], f[prime[i]])) % mod;
        }
        printf("%lld\n", (long long)ans);
    }
    return 0;
}

K Stacks

题意：给定一个排列 $\{a\}$ ，执行递增的单调栈操作，每次统计栈中元素个数，得到新的序列 $\{b\}$ 。现给定 $\{b\}$ 中若干个数，问可能的序列 $\{a\}$ 。

解法：考虑恢复 $\{b\}$ 。显然有一种简单的方法：每次认为加入的数单调递增。这样可以尽可能保证栈的大小不至于过小。因而 $b_i=\max\{b_{i+1}-1,1\}$ 。如果中途发现某一个位置上的数太大，即栈过大，可以直接输出 -1。

恢复了 $\{b\}$ 之后操作就比较简单了。从后向前考虑，如果当前位的 $b_i$ 为 $1$ ，显然在它的前面都没有比它小的数了，因而可以填 $1$ 。再向前考虑，除了 $1$ 之外没有更小的（由于 $1$ 被后面占用了），因而填 $2$ ……依次类推。

因而我们可以根据 $b_i$ 从小到大，从后到前依次恢复数列。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct node
{
    int a;
    int b;
    bool operator <(const node &t)const
    {
        return a < t.a;
    }
};
struct node que[1000005];
int b[1000005];
int num[1000005];
vector<int> depth[1000005];
int main()
{
    int k, n;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k;i++)
        scanf("%d%d", &que[i].a, &que[i].b);
    sort(que + 1, que + k + 1);
    int place = 1;
    for (int i = 1; i <= k;i++)
    {
        b[que[i].a] = que[i].b;
        if(b[que[i].a]>que[i].a)
        {
            printf("-1");
            return 0;
        }
        for (int j = que[i].a - 1; j >= place;j--)
            b[j] = max(1, b[j + 1] - 1);
        place = que[i].a + 1;
    }
    int temp = 1;
    for (int i = que[k].a + 1; i <= n;i++)
        b[i] = temp++;
    for (int i = n; i >= 1; i--)
        depth[b[i]].push_back(i);
    int now = 1;
    for (int i = 1; i <= n;i++)
    {
        for (int j = 0; j < depth[i].size();j++)
        {
            num[depth[i][j]] = now;
            now++;
        }
    }
    for (int i = 1; i <= n;i++)
        printf("%d ", num[i]);
    return 0;
}

L Wechat Walk

题意：给定一个由 $n$ 个人和 $m$ 个好友关系组成的一张无向图，有 $q$ 个时刻，每一时刻仅有一个人在走路贡献步数，问每个人成为自己好友列表中步数第一的总时刻数。

解法：考虑分块。根据好友人数的多少将人群分为两类：一类是大点，好友人数超过 $\sqrt{n}$ ；另一类是小点，好友人数不超过这个数值。下面就根据这两类人群进行讨论。

如果当前修改的人是小点：暴力修改其连接的所有点。
如果当前修改的人是大点：相邻大点暴力修改，小点使用哈希表进行修改。

首先是关于答案统计的一个方法：记录一个上次修改的时间戳。如果他在 $t$ 时刻成为了冠军，那么先观察之前有无成为冠军的时间戳，若有则统计上一次成为冠军到这一次成为冠军的时间，最后时间戳记上 $t$ 。如果从冠军上被拽下来了，那么时间戳改成非法时间戳（可用 $0$ ），同时将合法时间戳上时间累计到答案中，非法时间戳不可用于统计总时长。

具体来讲操作如下：

对于暴力修改的部分，记录两个值： $val_i$ 与 $maximum_i$ ，表示自己的步数和周围所有人（不含自己）的最大步数。每次他周围的人的 $maximum$ 用 $val_i$ 去更新，自己的 $maxmum_i$ 用周围人的 $value$ 去更新。如果当前发现 $val_i$ 严格大于 $maximum_i$ ，则证明自己成为冠军。如果发现周围人中有一个人的 $maximum$ 比他自己的 $val$ 大，证明他没冠军了（即使之前没冠军现在也没冠军了）。

然后是对于大点修改时周围小点的操作。注意到总步数不超过 $1\times 10^4$ ，大点个数不超过 $500$ ，因而可以使用一个 vector 存储当前点 $x$ 周围所有的**权值为 $y$ 并且成为冠军的小点编号**，记位 $C_{x,y}$ 。每次更新的时候，步数由 $a$ 变化到 $b$ ，只需要扫过一次 $C_{x,a+1}$ 到 $C(x,b)$ ，将全部因为大点步数增加而导致小点丢失冠军的人清出来更新他们的时间戳即可。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector<int> champion[505][10005];
vector<int> graph[200005], tobig[200005];
int last[200005], sum[200005];
int maximum[200005], val[200005];
int id[200005], cnt;
int main()
{
    int n, m, q, u, v, a, b;
    scanf("%d%d%d", &n, &m, &q);
    int limit = sqrt(n);
    for (int i = 1; i <= m;i++)
    {
        scanf("%d%d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i = 1; i <= n;i++)
        for (auto j : graph[i])
            if (graph[j].size() >= limit)
                tobig[i].push_back(j);
    for (int i = 1; i <= n; i++)
        if (graph[i].size() >= limit)
            id[i] = ++cnt;
    for (int t = 1; t <= q;t++)
    {
        scanf("%d%d", &a, &b);
        val[a] += b;
        if(graph[a].size()<limit)
        {
            maximum[a] = 0;
            for (auto i : graph[a])
            {
                maximum[i] = max(maximum[i], val[a]);
                if(maximum[i]>=val[i])
                    if(last[i])
                    {
                        sum[i] += t - last[i];
                        last[i] = 0;
                    }
                maximum[a] = max(maximum[a], val[i]);
            }
            if(val[a]>maximum[a])
            {
                if(last[a])
                    sum[a] += t - last[a];
                last[a] = t;
                for (auto i : tobig[a])
                    champion[id[i]][val[a]].push_back(a);
            }
        }
        else
        {
            for (auto i : tobig[a])
            {
                maximum[i] = max(maximum[i], val[a]);
                if(maximum[i]>=val[i])
                    if(last[i])
                    {
                        sum[i] += t - last[i];
                        last[i] = 0;
                    }
            }
            for (int i = val[a] - b + 1; i <= val[a];i++)
                while(!champion[id[a]][i].empty())
                {
                    int tp = champion[id[a]][i].back();
                    champion[id[a]][i].pop_back();
                    if(val[tp] > i)
                        continue;
                    if(last[tp])
                    {
                        sum[tp] += t - last[tp];
                        last[tp] = 0;
                    }
                }
            if(val[a]>maximum[a])
            {
                if(last[a])
                    sum[a] += t - last[a];
                last[a] = t;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if(last[i])
            sum[i] += q - last[i];
        printf("%d\n", sum[i]);
    }
    return 0;
}