专栏文章

AWTF2025E 漫画派对怪商一克拉 Snooze SHIKI 爆炸猎弓 一克拉 深夜时分 二米一 全力配合荣荣了 班主任说的日子不好过 冬之花毛线店即事花屏，G3 Logo 题解

隔隔壁泞2的如心
AT_awtf2025_e题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minwrf4l
此快照首次捕获于
2025/12/02 09:37
3 个月前
此快照最后确认于
2025/12/02 09:37
3 个月前
查看原文
确实是很难的题，但是完全能做！原本我想说这题的大多数步骤都顺理成章，结果我被一个神秘的关键点卡成 2121 了……
（由于是大组合意义做法，“钦定”这个词有点多，这里用颜色区分一下）
首先，最为直接的思路就是先 钦定\color{ff0080}钦定 有多少个 xi<i\color{ff0080}x_i< i，这样这些 钦定\color{ff0080}钦定 的边会连成数个连通块。那么，一个连通块内的结构有多少种？由于这里强制小于的限制，每个连通块内都是一个子节点比父节点编号大的树，设这个连通块大小为 ss，这样的树当然有 (s−1)!(s-1)! 种。
现在每个连通块里还有一个出度位置未知，我们要把它们连成置换环数已经确定的基环树。这当然很难，不然这道题就不会在这么阴间的位置了。那么这个问题有哪些弱化版是能做的呢？
  1. 如果我们 钦定\color{8000ff}钦定 一个连通块为根，要求其他连通块连成一棵树，那么这类似于有标号树计数问题，可以用 prufer 序列来解决。如果共有 cc 个连通块，作为根的连通块大小为 ss，那么答案为 Nc−2sN^{c-2}s。当然，你也可以先确定每个连通块的入度，然后拉反也能得到相同的结果。
  2. 如果我们要求每个连通块的入度和出度均为 11，那么我们可以提前在每个连通块中选出入度所在的位置，每个连通块的结构变为了 s!s! 种。我们发现这个结构数和一条有向的链是一样的！既然连通块间的连接只和连通块大小有关，那我们可以把每个连通块都直接替换为有向的链，这样我们就遗弃了所有编号大小关系，最后的图也只剩下了环，我们完全可以先 钦定\color{ff8000}钦定 环集然后再 钦定\color{8080ff}钦定 边了。（被 钦定\color{8080ff}钦定 的边不再需要满足 xi<ix_i < i 了，它可以和 钦定\color{ff0080}钦定 了相同数量的边的情况一一对应）
这时形势已经相当明朗了，因为基环树就是环和树拼起来，而环和树的性质都很好，所以可以直接做！我们可以得到，共 钦定\color{ff0080}钦定 了 KK 条 xi<ix_i<i 的边情况总数为下列问题的答案：
  1. 先从 NN 个数中选出 ii 个，钦定\color{ff8000}钦定 这 ii 个数构成 CC 个环，在这 ii 个边中任意 钦定\color{8080ff}钦定 k1k_1 条边，但是不允许同时 钦定\color{8080ff}钦定 一整个连通块的所有边。
  2. 将剩余的 N−iN-i 个点连成 c′c' 个环，这时把前面那 CC 个环组成的整体视为被 钦定\color{8000ff}钦定 的根，套用树的 prufer 方法，所有方案中 iNc′−1CN−i−c′K′−k1i\color{00bbee}N^{c'-1}C_{N-i-c'}^{K'-k1} 的和即为答案。
不过为了方便，可以把 2. 中的蓝色式子改写成下列组合意义形式：
  • 每个连通块内编号最小的点的出边对答案有 NN 的贡献，然后再 钦定\color{8080ff}钦定 N−i−c′N-i-c' 条其他的边中的 K′−k1K'-k_1 条。当然最后算完要除以 NN。
现在我们想把 钦定\color{ff0080}钦定 K′K' 条边换成恰好 KK 条边，在组合意义上就是在被 钦定\color{8080ff}钦定 的 K′K' 条边中再 钦定\color{00dd00}钦定 KK 条，让剩下的 K′−KK'-K 条边有 −1-1 的贡献。这时我们发现 1. 中 但是不允许同时钦定一整个连通块的所有边 的限制非常碍事！如果没有这个限制，那么 1. 中只有所有边都被 钦定\color{00dd00}钦定 的情况才有贡献。这个限制是因为一个大小为 ss 的连通块中最多只有 s−1s-1 条被 钦定\color{ff0080}钦定 xi<i\color{ff0080}x_i< i 的边。
这个限制似乎很难处理，它会让 1. 和 2. 的相性变得非常差！如果你强行处理它很可能会两头堵——当然也可能是你直接把它处理出来了（
不过有个很简单的方法可以绕过这个限制，就是把 钦定\color{ff0080}钦定 xi<i\color{ff0080}x_i< i 改成 钦定\color{ff0080}钦定 xi≤i\color{ff0080}x_i\le i，这样做没有其他的影响，但是被 钦定\color{ff8000}钦定 的环集中每条边都被 钦定\color{8080ff}钦定 了的环就可以和 钦定\color{ff0080}钦定 结构为有一个自环的树的连通块一一对应了。
——换句话说，直接无视这个限制再反转一下 kk 就是对的……
现在问题就变成了：
  1. 先从 NN 个数中选出 ii 个，钦定\color{ff8000}钦定 这 ii 个数构成 CC 个环，将这 ii 个边全部 钦定\color{00dd00}钦定。
  2. 将剩余的 N−iN-i 个点连成 c′c' 个环，每个环内编号最小的点的出边对答案有 NN 的贡献，然后再 钦定\color{00dd00}钦定 N−i−c′N-i-c' 条其他的边中的 K−iK-i 条，再剩下的边每个有 −1-1 的贡献。
这样，我们不妨枚举 ii，那么 钦定\color{ff8000}钦定 的方案数就是一列第一类斯特林数，接下来考虑 2. 的贡献，由于它和“环内编号最小的点”有关，这很适合用求一行斯特林数时“从小到大加入点”的方法。
具体地，设一个变元 yy 表示未被 钦定\color{00dd00}钦定 的边的数量，之后对于编号为 h=1∼N−ih=1\sim N-i 的点，它有三种选择：
  • 让这个点自成一个环，那么它就是这个环内编号最小的，这时它的出边不能被 钦定\color{00dd00}钦定，贡献为 NyNy；
  • 把这个点加到已有的某个点后面且不 钦定\color{00dd00}钦定 它的出边，贡献为 −(h−1)y-(h-1)y；
  • 把这个点加到已有的某个点后面且 钦定\color{00dd00}钦定 它的出边，贡献为 (h−1)(h-1)。
因此，我们要做的就是对于任意 0≤h≤N−10\le h \le N-1，算出 [yN−K]∏i=0h((N−h)y+h)[y^{N-K}]\prod^h_{i=0}((N-h)y+h)。被这么多道分治 NTT 题创完之后我确实也长记性了，发现直接分治 NTT 就可以算出来这个东西，只要保证每个分治区间的复杂度关于区间长是 polylog 的就可以，这题终于做完啦！
这个分治 NTT 有一些细节，所以代码还是有必要放的（
CPP
//省略多项式板子
poly de0[305416];
mi ans[305416];
void divsolve(poly *des,poly serv,int l,int r){
    //cout<<l<<' '<<r<<endl;
    //serv.print_shrink('\n');
    if(l==r){
        ans[l+1]=serv[0]*de0[l][1]+serv[1]*de0[l][0];
        return;
    }
    int mid=(l+r)>>1,len=r-l+1,lenl=mid-l+1,lenr=r-mid;
    poly se0(lenl+1);
    for(int i=0;i<=lenl;i++)se0[i]=serv[len-lenl+i];
    divsolve(des,se0,l,mid);
    vector<poly> pv;for(int i=l;i<=mid;i++)pv.push_back(de0[i]);
    poly pp=prod(pv);pp.set_shrink(len+1);serv=serv*pp;
    poly se1(lenr+1);
    for(int i=0;i<=lenr;i++)se1[i]=serv[len-lenr+i];
    divsolve(des,se1,mid+1,r);
}
int main(){
    default_shrink=-1;
    int n,c,k;cin>>n>>c>>k;
    poly p0(n+3);
    for(int i=1;i<=n+2;i++)p0[i]=inv(i);
    p0=gpow(p0,c)*rfac[c];
    //p0.print_shrink('\n');
    poly p1;p1[n-k]=1;p1.set_shrink(n+1);
    for(int i=0;i<=n-1;i++){
        de0[i][0]=i;de0[i][1]=n-i;
    }
    divsolve(de0,p1,0,n-1);ans[0]=(k==0);
    //for(int i=0;i<=n;i++)cout<<ans[i]<<' ';cout<<endl;
    mi tans;
    for(int i=1;i<=n;i++){
        if(i<n)tans=tans+p0[i]*ans[n-i]*rfac[n-i]*fac[n-1]*i;
        else tans=tans+p0[i]*ans[n-i]*rfac[n-i]*fac[n];
    }
    cout<<tans;
}
可能是从 22 年某天我突然发现我会做树上的数开始，我就开始越级做很难的题。这也许是因为难的题会更加有趣，也许是因为这样会显得自己比较强，从而在正赛怎么也打不好的时候找回一些自信。
这实在不能说是什么好习惯……就算不谈花费的大把时光，有时我甚至会因为做出来题太过激动从而干一些很 2121 的事，比如给题目投莫名其妙的翻译、在题解里加上莫名其妙的闲话——就像这里一样（
我想起来我高一的时候特别喜欢做平面几何，从哈尔滨中考一直做到高联。当时我也是越级做题，也是花费了很多时间，可现在我简直是要忘了做平几题是什么样的感觉了……
“做题”可以是很美好的事，好的题目真的可以带给人很多。和当时做平几的时候相比，现在我有了更多交流的机会，写的题解真的会有人看，出的题真的会有人做！这其实很不容易，所以我很希望我可以走得更远一些，从而在这里留下更多有趣的东西。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...