AtCoder Beginner Contest 279

感觉ABC的质量还是很高的啊。

F - BOX

题意

有 $n$ 个盒子，一开始盒子 $i$ 内装有小球 $i$。每次执行以下三种操作之一：

• 将盒子 $y$ 内的所有小球放入盒子 $x$。
• 记当前所有盒子内的小球个数为 $k$，将小球 $k+1$ 放入盒子 $x$。
• 询问小球 $x$ 在哪个盒子中。

题解

一道并查集应用的好题。

由于询问操作和合并操作，很容易能想到并查集。但是直接用并查集是不行的，样例一就是一个例子：先将 $4$ 号盒子内的小球放入 $1$ 号盒子，此时我们对两个盒子进行合并。然后将 $7$ 号球放入 $4$ 号盒子，询问 $7$ 号球。由于 $4$ 号盒子已经被并入了 $1$ 号盒子，所以得到的结果会是 $1$ 号盒子，但实际上它在 $4$ 号盒子内。

为了解决这个问题，我们先回过头来看看并查集在这里的实际意义是什么。我们在初始化时，为每个小球分配了对应的盒子，操作一相当于将一个盒子 $y$ 并入另一个盒子 $x$，操作二相当于为一个小球分配一个新的盒子，并将这个盒子并入 $x$。那么，对于上面提到的问题，可以考虑为盒子 $y$ 新分配一个点，并将后面加入盒子 $y$ 的小球加入这个点。同时，为了查找答案，我们还需要记录下每个点对应的盒子。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=9e5+5;
int f[maxn],id[maxn],ans[maxn];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y) return;
    f[y]=x;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) f[i]=i,id[i]=i,ans[i]=i;
    int m=n+q,k=n;
    while(q--)
    {
        int op;cin>>op;
        if(op==1)
        {
            int x,y;cin>>x>>y;
            merge(id[x],id[y]);
            id[y]=++m;
            f[m]=m,ans[m]=y;
        }
        else if(op==2)
        {
            int x;cin>>x;
            f[++k]=id[x];
        }
        else 
        {
            int x;cin>>x;
            cout<<ans[find(x)]<<'\n';
        }
    }
    return 0;
}

G - At Most 2 Colors

题意

给定一个 $1\times n$ 的网格，用 $c$ 种颜色染色。要求连续 $k$ 个格子至多有两种不同的颜色，求方案数。

题解

比较精巧的计数dp。

设 $f_{i,0/1}$ 表示第 $i$ 个位置，最后 $k-1$ 个中有 $1/2$ 种颜色的方案数。

为什么要用 $k-1$ 个作为状态。因为知道了 $i$ 的颜色和 $i-1$ 的后 $k-1$ 个就能确定 $i$ 的后 $k$ 个，便于转移。

对 $f_{i,0}$，有

$$f_{i,0}=c+\sum_{j=1}^{i-k+1}(f_{j,0}\times(c-1)+f_{j,1})$$

首先全选同一种颜色，有 $c$ 种方案。否则枚举与后 $k-1$ 个格子颜色不同的最后一个格子 $j$，若它的后 $k-1$ 个为一种颜色，那么 $j+1$ 的颜色有 $c-1$ 种；若它的后 $k-1$ 个为两种颜色，那么 $j+1$ 一定是和 $j$ 不同的另一种。

类似地，对于 $f_{i,1}$，有

$$f_{i,1}=\sum_{j=i-k+2}^{i-1}(f_{j,0}\times(c-1)+f_{j,1})$$

最终的答案为 $f_{n,0}+f_{n,1}$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int p=998244353;
ll f[maxn][2],sum[maxn][2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k,c;cin>>n>>k>>c;
    f[1][0]=sum[1][0]=c;
    for(int i=2;i<=n;i++)
    {
        f[i][0]=(c+sum[max(0,i-k+1)][0]*(c-1)+sum[max(0,i-k+1)][1])%p;
        f[i][1]=((sum[i-1][0]-sum[max(0,i-k+1)][0]+p)*(c-1)+(sum[i-1][1]-sum[max(0,i-k+1)][1]+p))%p;
        sum[i][0]=(sum[i-1][0]+f[i][0])%p;
        sum[i][1]=(sum[i-1][1]+f[i][1])%p;
    }
    cout<<(f[n][0]+f[n][1])%p;
    return 0;
}

Ex - Sum of Prod of Min

题意

给出正整数 $n,m$ 满足 $n\leq m\leq 2\times n$， $S=(S_1,S_2,\cdots,S_n)$。求

$$\sum_{\sum\limits_{i=1}^nS_i=m}\prod_{k=1}^n\min(k,S_k)$$

题解

很好的生成函数练习。

（省略了一些计算步骤）

第 $t$ 个位置上填的数的生成函数为

$$F_t(x)=\sum_{i\geq 0}\min(t,i)x^i=\frac{x-x^{t+1}}{(1-x)^2}$$

所以答案为

$$\mathrm{Ans}=[x^m]\prod_{t=1}^n\frac{x-x^{t+1}}{(1-x)^2}=[x^{m-n}](1-x)^{-2n}\prod_{t=1}^n(1-x^t)$$

我们只关心次数小于等于 $m-n$ 的项，所以考虑模 $m-n$ 意义下。由于 $m-n\leq n$，有

$$\prod_{t=1}^n(1-x^t)\equiv\prod_{t\geq 1}(1-x^t)$$

由五边形数定理，

$$\prod_{t\geq 1}(1-x^t)=\sum_{k\geq 0}(-1)^kx^{\frac{k(3k\pm1)}{2}}$$

所以

$$\mathrm{Ans}=\sum_{k\geq 0}(-1)^k\binom{2n-1+m-n-\frac{k(3k\pm1)}{2}}{2n-1}$$

需要枚举的 $k$ 有 $O(\sqrt{n})$ 项，可以直接枚举。计算组合数时，需要使用卢卡斯定理。