蜜月日记 Part8

littlez_meow · 2024-12-10 15:37:22 · 休闲·娱乐

前言

继续蜜月日记。

Day 71

给模拟赛准备的。

2024/12/12 自由（Freedom）

题意

给定一个 n 个点 m 条边的有向图，定义路径的点权为经过点的点权的和，边权为经过边的边权的积。求点权和为 V 的所有路径的边权和。提交答案。

思路

Case 1

发现 n,m,V 都很小，设 dp(i,j) 表示点权为 i 结尾为 j 的路径边权和，转移枚举 j 的出边。时间复杂度 O(V(n+m))。

Case 2,3

都是 \texttt{K} 开头，数据里 m=n^2，是完全图。不仅如此，每条边的边权还是一样的。

那就不用考虑边不边的了。题意转化成求所有值域在 [1,n] 和为 V 的序列的权值和，若序列长为 t 则序列的权值为 c^{t-1}。在测试点 2,3 里 c=3,7。

看着就很可以 dp 啊！设 dp(i) 表示点权和为 i 的答案乘 c，转移为 dp(t)=\sum\limits_{i=1}^nc\times dp(t-a_i)。这是一个常系数线性齐次递推，用普通方法做是 O(W\log W\log V) 的，其中 W 是 a_i 的最大值。可以通过这两个点。

Case 4

还是边权相同的完全图，但这次 W 很大，普通的常系数线性齐次递推跑不过。这里 c=7。

但是观察点权，你发现只有两个值，因此转移形如 dp(t)=r\times dp(t-1)+s\times dp(t-x)，其中 r=42c=294,s=38c=266,x=537653823。

考虑组合意义，把 i 向 i+x 连边权为 s 的边，向 i+1 连边权为 r 的边，则要求从 0 到 v 所有路径边权积的和，最后乘上 \dfrac 1 c，因为我们把第一个点也当连边算了，但其实它没连。

发现路径边权积只取决于经过了多少条 i\to i+x 的边。我们枚举经过的边数 t，由于 xt\le V，有 t=O(\dfrac V x)。

对于一个 t，我们可以求出经过 i\to i+1 的边数为 V-tx，则路径个数为 \dbinom{V-tx+t}{t}，权值为 r^{V-tx}s^t。

所以答案为 \dfrac 1 c\sum\limits_{t=0}^{\lfloor\frac V x\rfloor}\dbinom{V-tx+t}{t}r^{V-tx}s^t。暴力计算组合数，复杂度为 O\left(\left(\dfrac V x\right)^2\right)，大概是 20000^2，能过。

Case 5

进入 \texttt{MP} 开头的点。发现点权全部都是 1，于是询问的其实是经过 V 个点的路径权值和。

这是一个非常经典的模型。设 dp(i,j) 表示经过 i 个点目前到 j 的路径权值和，转移形如乘一个矩阵，可以矩阵快速幂。

值得注意的是，这个矩阵是邻接矩阵，记为 A。

最后答案为所有 dp(V,*) 的和，初始 dp(1,*)=1。故答案为 A^{V-1} 所有元素的和。

这个点 n 很小，直接暴力矩阵乘法 O(n^3\log V) 可过。

Case 6

观察图的性质，发现前 n 条边是 1 连出去的，后 n-1 条边从 i 连向 i+1 且边权为 1。

所以说邻接矩阵形如（没写出的元素均为 0）：

其中 w_i 是 1\to i 的边权。这是一个常系数线性齐次递推的矩阵，也就是说问题变成求 x_t=\left\{\begin{matrix} 1 & (t<n)\\ \sum\limits_{i=1}^n w_ix_{t-i}& (t\ge n) \end{matrix}\right. 的第 V-1 项到 n+V-2 项的和。

为了求区间和，我们想求出前缀和。不妨设 x 的生成函数是 F(z)，我们来研究前缀和数列的生成函数 G(z)。因为这里有 x 所以形式幂级数用 z。

考虑 [z^i]F(z) 的贡献，它会累加到所有 \ge i 的项，相当于这项乘了 1+z+z^2+\cdots=\dfrac 1{1-z}。

因此我们有 G(z)=\dfrac{F(z)}{1-z}。由于 F(z) 是有理函数，G(z) 也是有理函数，分子分母次数还是 O(n)。问题转化为求一个有理函数的高次项系数，这可以用 FFT 优化的 Bostan-Mori 算法解决，时间复杂度 O(n\log n\log V)。

当然也可以把 G(z) 重新转回常系数线性齐次递推，虽然稍微有些麻烦，不如直接 Bostan-Mori，而且因为 n 很大你是不能 O(n^2) 的 BM 求递推式的。

Case 7

这次的 V 超级大，而且 A^{V-1} 是不能用欧拉定理降幂的。

发现输入中每个点连出去的边很少，再仔细看看发现点 i 只会连向 \ge i 的点，而且必然有一条边权为 i+1 的边连向 i。

于是得出这是一个主对角线互不相同的上三角矩阵，而且很稀疏。

再结合我们要把指数从矩阵上变到数上来使用欧拉定理，这启发我们相似对角化。

设 A=P^{-1}\Lambda P，其中 \Lambda 是把特征值排在主对角线上的对角矩阵，则 A^{V}=P^{-1}\Lambda^V P。发现 P 和 P^{-1} 是不随 V 而改变的，因此答案形如 \sum\limits_{i=1}^n c_i\lambda_i^V，其中 c_i 是常数。根据欧拉定理，V 可以对 998244352 取模。

写出答案的生成函数为 F(x)=\sum\limits_{j=0}^{\infty}x^j\sum\limits_{i=1}^n c_i\lambda_i^j，简单化简得到 F(x)=\sum\limits_{i=1}^n\dfrac{c_i}{1-\lambda_i x}。

答案是有理函数，但是带 c，还是不好处理。通分一下，分子变成次数小于 n 的多项式 G(x)，那么有 F(x)=\dfrac{G(x)}{\prod\limits_{i=1}^n1-\lambda_i x}。

由于 A 稀疏，在不带自环的情况下图的路径数很少，可以暴力求出 F(x) 的前 n 项，然后递推出 G(x)。这样就可以 Bostan-Mori 了。

Case 8

给出的图包括 2i\to 2i-1,2i-1\to 2i,2i-1\to 2i-1，2i-1\to 2i+1 这些边，也就是相邻奇数偶数连双向边，相邻奇数从小向大连，奇数连自环。所有边边权为 1。

好像没有什么很好直接算的方法，这个图又很规整，那就递推吧。

设 [x^V]F_i(x) 表示从 2i-1 出发长为 V 路径个数（即边权和，因为边权为 1）的生成函数，[x^V]G_i(x) 表示从 2i 出发长为 V 路径个数。为了求和，设 H_i(x)=F_i(x)+G_i(x)，再设 t=\dfrac n 2。

最终答案为 [x^V]\sum\limits_{i=1}^t H_i(x)。

先来列递推方程。考虑每个点向外走到哪个点，可以列出：

解得 F_i(x)=\dfrac{x(F_{i-1}(x)+1+x)}{1-x-x^2}。

代入到 H_i(x)，得到 H_i(x)=\dfrac{xH_{i-1}(x)+2x}{1-x-x^2}，其中 H_0(x)=x。

把 x 看作常数，H 看成数列，则这个递推式是形如 a_i=pa_{i-1}+q 的经典形式，可以化成等比数列求通项。算出来得到：

接下来要求 \sum\limits_{i=1}^t H_i(x)。把分子拆开，每一项都是等比数列，使用等比数列求和得到：

是环。设 s 是点权和，那么肯定是先绕环走 \lfloor\dfrac V s\rfloor 圈，然后再走几步。走的步数可以用双指针求，顺便统计贡献。

要用高精除算圈数，时间复杂度 O(n+\log V\log n)。注意圈数在指数上，所以是对 998244352 取模。

Case 10

这个图只有自环。对于点 i，如果 a_i|V，则会做出 w_i^{\frac V{a_i}-1} 的贡献，其中 w_i 是 i\to i 的边权。直接计算复杂度 O(n\log V)。

代码

提交答案就不给了。

Day 72

补题。

2024/12/13 [省选联考 2024] 重塑时光

题意

给定 m 个形如“x 在 y 之前”的限制，求有多少种把一个长为 n 的排列分成 k+1 个可空的段的方案，使得存在一种这 k+1 段的排列满足这 m 条限制，以及总方案数。

思路

首先总方案数是 (n+k)!。把 m 条限制建图，肯定是 DAG。

由于排列任意，分割方式也任意，顺序就没那么重要了。可以为空看起来比较烦人，题意转化成把 \{1,2,\cdots,n\} 分成至多 k+1 个不可空的集合。

设 f'_i 为分割成 i 个集合的方案。它对合法方案数的贡献应该是这 i 个集合重排的 i!、空集合插入的 \dbinom{k+1}{i} 和切 k 刀的顺序 k!。总的贡献是 f'_i i!k!\dbinom{k+1}{i}。

问题转化为求 f'_i。发现这个和拓扑序计数很像，而且数据范围不大，考虑状压。设 f(S,i) 表示把集合 S 分成 i 个序列的方案数，注意这里序列内部有序，序列间无序。

首先，由于序列内部有序，可以先预处理出 g(S) 表示把集合 S 重排满足拓扑序的方案数。可以 O(2^n n) 处理。

然后根据 DAG 计数经典技巧，加入一些入度为 0 的点。设 h(S,i) 表示将集合 S 分成 i 个序列的方案数，注意这里序列内部有序，序列间也有序。这是为了方便转移。

设 \operatorname{len}(S)=n+L，S 中区间左端点分别为 l_0<l_1<\cdots<l_k，不难发现 l_k=l_0+L，则排列的方案数有以下几部分：

• 依此类推，[l_{k-1}+n,l_k+n) 是区间 [l_{k-1},l_k) 的排列，方案数 (l_k-l_{k-1})!。

• 不被任何区间包含的 2n-L 个元素，方案数 \rho(2n-L)=\dfrac{(2n-L)!}{2^{\max(n-L,0)}}。这是因为总共有 (2n-L)! 种方案，其中有 \max(n-L,0) 对相同元素会算重。

全部乘起来，把容斥系数拆到求积号里面，有 f(S)=-n!\rho(2n-L)\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。

枚举 L 求和得到 \sum\limits_{S\in P}f(S)=-n!\sum\limits_{L=0}^{2n}\rho(2n-L)\sum\limits_{S\in P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。

问题转化为求 \sum\limits_{S\in P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。

观察发现 l_i-l_{i-1} 是一组 L 的拆分，可以用生成函数描述。但是生成函数只是无脑加起来，并不能满足 S\in P 的限制。所以我们考虑放宽限制。

设 P' 表示连通的 S 的集合。容易得到 P\subseteq P'。因此要求 \sum\limits_{S\in P',\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)-\sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。

先来解决式子的第一项。正如刚刚说的，求积号里是一个拆分，可以用生成函数描述。

设 w(L)=[x^L]\dfrac{1}{1+\sum\limits_{i=1}^n i!x^i}，则 \sum\limits_{S\in P',\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)=(2n-L+1)w(L)。这里 2n-L+1 是 l_0 的选法。

求 w(1)\sim w(2n) 可以用多项式求逆 O(n\log n) 求出来。

接下来就是本题最难的部分，求 \sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。

我们先考虑 S\in P'\setminus P 长什么样子。设 S 最左边的区间是 [u,u+n)，最右边是 [v,v+n)。你发现，由于每个区间长为 n，因此任意一个 S 中区间都会和 [u,u+n),[v,v+n) 中恰好一个相交。这是因为如果和两个相交就属于 P 了，和两个都不相交长度就不可能到达 n。

于是，设和 [u,u+n) 相交的区间的集合是 U，和 [v,v+n) 相交的区间的集合是 V。显然，U,V 都是连通的。U 的长度是 n+x，区间左端点是 u=u_0<u_1<\cdots<u_p=u+x；V 的长度是 n+y，区间左端点是 v=v_0<v_1<\cdots<v_q=v+x；z 是 U,V 的交的长度，即 z=(u_p+n)-v_0。则，x+y-z+n=L,x\in[0,n),y\in[0,n),z\in(0,\min\{x,y\})。不妨令 (x,y,z) 的三元组的集合是 A，即 A=\{(x,y,z)\in\mathbb{Z}^3|x\in[0,n),y\in[0,n),z\in[0,\min\{x,y\})\}。三元组中 z 是最小的。

所以有 \sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)=\sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}(v_0-u_p)!\prod\limits_{i=1}^p(-(u_i-u_{i-1})!)\prod\limits_{i=1}^q(-(v_i-v_{i-1})!)。这里前面没有负号是因为 U,V 的负号消掉了。

类似于上面的讨论，我们有该式等于 \sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}(n-z)!w(x)w(y)。

枚举 S 变为枚举 (x,y,z)，得到该式等于 (2n-L+1)\sum\limits_{(x,y,z)\in A,x+y-z+n=L}(n-z)!w(x)w(y)。2n-L+1 是 l_0 的选法。

不妨设 B_L=-\sum\limits_{(x,y,z)\in A,x+y-z=L-n}(n-z)!w(x)w(y)。我们需要快速求出 B_0\sim B_{n}。这里前面的负号是为了把之前的式子前面的减变成加。

考虑分治。设 solve(l,r) 表示将满足 x,y,z\in[l,r) 的所有 (x,y,z)\in A 的贡献加进 B_{x+y-z}，再设 m=\lfloor\dfrac{l+r}{2}\rfloor。一共有三种贡献：

时间复杂度 O(n\log^2 n)。

计算 \sum\limits_{S\in Q}f(S)

类似于上面的讨论，设 S 最左边的区间是 [u,u+n)，最右边是 [v,v+n)，任意一个 S 中区间都会和 [u,u+n),[v,v+n) 中恰好一个相交。设和 [u,u+n) 相交的区间的集合是 U，和 [v,v+n) 相交的区间的集合是 V。显然，U,V 都是连通的。U 的长度是 n+x，区间左端点是 u=u_0<u_1<\cdots<u_p=u+x；V 的长度是 n+y，区间左端点是 v=v_0<v_1<\cdots<v_q=v+x；z 是 U,V 的距离，即 z=v-u-n。

排列的方案数有以下几部分：

• 不被 [u,u+n),[v,v+n) 包含的部分，一共 n! 种方案。

• * $[u_p,u+n)$ 是不在 $[u+n,u+n+x)$ 元素的排列，方案数 $(n-x)!$。 * $[u_{p-1},u_p)$ 是 $[u_{p-1}+n,u_p+n)$ 元素的排列，方案数 $(u_p-u_{p-1})!$。 * 依此类推，$[u_0,u_1)$ 是区间 $[u_0+n,u_1+n)$ 的排列，方案数 $(u_1-u_0)!$。

拆一下容斥系数，有 f(S)=n!(n-x)!(n-y)!\prod\limits_{i=1}^p(-(u_i-u_{i-1})!)\prod\limits_{j=1}^q(-(v_j-v_{j-1})!)。

枚举 S 变成枚举 (x,y,z)，结合 Q 的定义，我们有 \sum\limits_{S\in Q}f(S)=n!\sum\limits_{z=1}^n(n-z+1)\sum\limits_{x=0}^{z-1}\sum\limits_{y=0}^{z-1}w(x)w(y)(n-x)!(n-y)!。

化简即为 \sum\limits_{S\in Q}f(S)=n!\sum\limits_{z=1}^n(n-z+1)\left(\sum\limits_{i=0}^{z-1}w(i)(n-i)!\right)^2。n-z+1 是选择 u_0。

可以前缀和优化做到 O(n) 计算。

综上，我们以 O(n\log^2 n) 的时间复杂度解决了这个问题。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define vi vector<int>
using namespace std;
const int MAXN=1<<20,MOD=998244353,INV2=499122177,INV6=166374059,G=3;
inline ll qpow(ll base,int expo){
    ll res(1);
    while(expo){
        (expo&1)&&(res=res*base%MOD);
        base=base*base%MOD,expo>>=1;
    }
    return res;
}
const int INVG=qpow(G,MOD-2);
int gpow[21],invgpow[21];
inline void calc(){
    F(i,1,20) gpow[i]=qpow(G,(MOD-1)>>i),invgpow[i]=qpow(INVG,(MOD-1)>>i);
    return;
}
inline void meow(int&t){
    t<0&&(t+=MOD);
    t>=MOD&&(t-=MOD);
    return;
}
int rev[MAXN];
inline void NTT(int*poly,int len,bool inv){
    F(i,0,len-1) (i<rev[i])&&(swap(poly[i],poly[rev[i]]),1);
    static ll g[MAXN];
    g[0]=1;
    for(int i(1),expo(1);i<len;i<<=1,++expo){
        ll omega=inv?invgpow[expo]:gpow[expo];
        F(j,1,i-1) g[j]=g[j-1]*omega%MOD;
        for(int j(0);j<len;j+=(i<<1)) F(k,0,i-1){
            int&x(poly[j|k]),&y(poly[i|j|k]);
            ll qwq(g[k]*y%MOD);
            y=x-qwq;
            y<0&&(y+=MOD);
            x+=qwq;
            x>=MOD&&(x-=MOD);
        }
    }
    if(inv){
        ll invl=qpow(len,MOD-2);
        F(i,0,len-1) poly[i]=poly[i]*invl%MOD;
    }
    return;
}
inline void build_rev(int n){
    F(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
    return;
}
struct poly{
    int num[MAXN]={};
    int len=0;

    inline void resize(const int a){
        for(;len>a;--len) num[len]=0;
        len=a;
        if(len<0) len=0;
        return;
    }
    inline poly operator+(const poly a)const{
        poly res;
        res.len=max(a.len,len);
        F(i,0,res.len) res.num[i]=num[i]+a.num[i],meow(res.num[i]);
        return res;
    }
    inline poly operator+(const int a)const{
        poly res=*this;
        int&qwq(res.num[0]);
        qwq+=a;
        meow(qwq);
        return res;
    }
    inline poly operator-(const poly a)const{
        return a*(-1)+*this;
    }
    inline poly operator-(const int a)const{
        return *this+(-a);
    }
    inline poly operator*(const poly a)const{
        poly x,y=*this;
        if(a.len*1ll*len<=1e5){
            x.len=a.len+len;
            F(i,0,len) F(j,0,a.len){
                int&qwq(x.num[i+j]);
                qwq=(qwq+a.num[j]*1ll*num[i])%MOD;
            }
            return x;
        }
        x=a;
        int expo=max(__lg(((len+a.len+1)<<1)+1)+1,1),l=1<<expo;
        build_rev(l);
        NTT(x.num,l,0);
        NTT(y.num,l,0);
        F(i,0,l-1) x.num[i]=1ll*x.num[i]*y.num[i]%MOD;
        NTT(x.num,l,1);
        x.resize(len+a.len);
        return x;
    }
    inline poly operator*(const int a)const{
        poly res=*this;
        F(i,0,len){
            int&qwq(res.num[i]);
            qwq=a*1ll*qwq%MOD;
            meow(qwq);
        }
        return res;
    }
    inline poly inv(){
        poly res;
        res.num[0]=qpow(num[0],MOD-2);
        for(int l(2),expo(1);l<(len<<1);l<<=1,++expo){
            int tmp[MAXN]={};
            F(i,0,(l<<1)-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<expo);
            memcpy(tmp,num,sizeof(int)*l);
            NTT(tmp,l<<1,0);
            NTT(res.num,l<<1,0);
            F(i,0,(l<<1)-1){
                int&qwq(res.num[i]),t(2-1ll*qwq*tmp[i]%MOD);
                meow(t);
                qwq=1ll*qwq*t%MOD;
            }
            NTT(res.num,l<<1,1);
            F(i,l,(l<<1)-1) res.num[i]=0;
        }
        res.resize(len);
        return res;
    }
};
int px[MAXN],py[MAXN];
inline vi mul(const vi&x,const vi&y){
    int n=x.size()+y.size()-1;
    n=1<<(__lg(n)+1);
    build_rev(n);
    F(i,0,x.size()-1) px[i]=x[i];
    F(i,x.size(),n-1) px[i]=0;
    F(i,0,y.size()-1) py[i]=y[i];
    F(i,y.size(),n-1) py[i]=0;
    NTT(px,n,0),NTT(py,n,0);
    F(i,0,n-1) px[i]=px[i]*1ll*py[i]%MOD;
    NTT(px,n,1);
    vi res(x.size()+y.size()-1);
    F(i,0,res.size()-1) res[i]=px[i];
    return res;
}
int n;
ll fact[MAXN],B[MAXN];
poly w;
inline ll rho(int L){
    return fact[2*n-L]*qpow(INV2,max(n-L,0))%MOD;
}
inline void m_le_xy(int l,int m,int r){
    vector<int>x(r-l+1),y(r-l+1);
    F(i,m,r-1) (x[i-l]+=w.num[i])>=MOD&&(x[i-l]-=MOD);
    F(i,l,m-1) y[r-i]=fact[n-i];
    x=mul(x,x);
    x=mul(x,y);
    F(i,max(r-2*l,0),x.size()-1){
        int qwq=i-r+l*2;
        if(qwq>n) break;
        (B[qwq]+=x[i])>=MOD&&(B[qwq]-=MOD);
    }
    return;
}
inline void x_le_m_le_y(int l,int m,int r){
    vector<int>x(r-l+1),y(r-l+1);
    F(i,l,m-1) (x[i-l]+=w.num[i])>=MOD&&(x[i-l]-=MOD);
    F(i,l,m-1) y[r-i]=fact[n-i];
    x=mul(x,y);
    F(i,0,min(int(x.size()-1),r-l)) x[i]=0;
    F(i,0,r-l) y[i]=0;
    F(i,m,r-1) y[i-l]=w.num[i];
    x=mul(x,y);
    F(i,max(r-2*l,0),x.size()-1){
        int qwq=i-r+l*2;
        if(qwq>n) break;
        (B[qwq]+=x[i])>=MOD&&(B[qwq]-=MOD);
        (B[qwq]+=x[i])>=MOD&&(B[qwq]-=MOD);
    }
    return;
}
void solve(int l,int r){
    if(r-l<=1) return;
    int m=(l+r)>>1;
    solve(l,m),solve(m,r);
    m_le_xy(l,m,r);
    x_le_m_le_y(l,m,r);
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    calc();
    cin>>n;
    fact[0]=1;
    F(i,1,3*n) fact[i]=fact[i-1]*i%MOD;
    F(i,0,n) w.num[i]=fact[i];
    w.len=2*n+1;
    w=w.inv();
    int ans=fact[3*n]*qpow(INV6,n)%MOD;
    F(L,0,2*n) ans=(ans+rho(L)*(MOD-fact[n])%MOD*(2*n-L+1)%MOD*w.num[L])%MOD;//S in P'
    solve(0,n);
    F(L,n,2*n) ans=(ans+rho(L)*(MOD-fact[n])%MOD*(2*n-L+1)%MOD*B[L-n])%MOD;//S in P'\P
    ll sum=0;
    F(z,1,n){//S in Q
        sum=(sum+w.num[z-1]*fact[n-z+1])%MOD;
        ans=(ans+fact[n]*(n-z+1)%MOD*sum%MOD*sum)%MOD;
    }
    cout<<ans;
    return 0;
}

Day 74

感觉自己非古典概型的部分都很烂。

2024/12/27 [ZJOI2015] 地震后的幻想乡

题意

给定一张 n 个点 m 条边的图，边权是 [0,1] 中均匀随机的实数，求最小生成树最大边边权的期望。

思路

原问题等价于每条边出现的时间是边权，求图第一次连通的期望时间。

设第一次联通的期望时间为随机变量 X，所求为 E(X)。

根据经典的拆贡献结论， E(x)=\int_0^1P(X\ge t)\mathrm{d}t，就是把离散情况的求和改成了连续情况的积分。

虽然这里带等号，但其实 P(x\ge t)=P(x>t)，也就是要求 t 时刻仍然不连通的概率之和。

由于 n 很小，考虑状压。设 P_S(t) 表示点集 S 在 t 时刻不连通的概率，其中 1\in S。由于一个点始终连通，初值为 P_{\{1\}}(t)=0。

设 e(S,T) 表示点集 S,T 之间的边数。转移比较简单，枚举 S 中包含 1 的极大连通块 T，钦定 T 和 S\setminus T 没有连边。其中 T 连通的概率是 1-P_T(t)，没有连边的概率是 (1-t)^{e(T,S\setminus T)}。于是有：

设 U=\{1,2,\cdots,n\}，答案为 \int_0^1 P_U(t)\mathrm d t。这个式子里带积分，所以上面的转移最好也要有积分。

转移式两边同时求 0\sim 1 的定积分，得到：

根据积分的线性性拆一下得到：

第一项定积分直接积出来：

第二项积分没法化简了，我们继续 dp。设 f(S,k)=\int_0^1 P_S(t)(1-t)^k\mathrm d t。

代入上面的递推式得：

即 f(S,k)=\sum_{T\subsetneq S,1\in T}(\dfrac{1}{1+e(T,S\setminus T)+k}-f(T,k+e(T,S\setminus T)))。

然后就可以转移了，时间复杂度 O(3^nm)。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=11,MAXS=(1<<10)+10;
int n,m,U,con[MAXN],Con[MAXS];
double f[MAXS][MAXN*MAXN];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    U=(1<<n)-1;
    F(i,1,m){
        int u,v;
        cin>>u>>v;
        con[u]|=(1<<(v-1));
        con[v]|=(1<<(u-1));
    }
    F(S,3,U) if(S&1) for(int T=S&(S-1);T;T=(T-1)&S) if(T&1){
        int e=0;
        F(i,0,n-1) if((S>>i&1)&&!(T>>i&1)) e+=__builtin_popcount(con[i+1]&T);
        F(i,0,m-e) f[S][i]+=1/(i+e+1.0)-f[T][i+e];
    }
    cout<<fixed<<setprecision(6)<<f[U][0];
    return 0;
}

Day 75

感觉是一个很典的过程。

2024/12/28 [BJOI2018] 双人猜数游戏

题意

Alice 知道 mn，Bob 知道 m+n，两人都知道 s\le m\le n。从某个人开始，两人轮流说了一共 t 次不知道后均猜出 m,n 的值。求一组合法的 m,n。

思路

这种题都是用“不知道”来缩小解的集合，直到只存在一组解。

这种东西看着就很可以递推。毕竟肯定是从“如果 (x,y) 是解，那对方应该早就知道了”推理出“(x,y) 不是解”，再推出“(p,q) 是解”。这种人的推理过程中本身就蕴含了递推。

所以设 dp(i,j,k) 表示如果答案是 (j,k)，先知道答案的人在第 i 次回答时是否知道。下面来研究转移。

首先，如果在上一次回答就知道了，那么这一次也肯定知道。即，若 dp(i-2,j,k)=1，则 dp(i,j,k)=1。

然后，就是看对方是否只有一组解是不确定的。具体地，若第 i-1 轮是 Alice 回答，满足 dp(i-1,j,k)=0，且对于任意 x,y\ge s,xy=jk,(x,y)\neq(j,k)，都有 dp(i-1,x,y)=1，则 dp(i,j,k)=1；若第 i-1 轮是 Bob 回答，满足 dp(i-1,j,k)=0，且对于任意 x,y\ge s,x+y=j+k,(x,y)\neq(j,k)，都有 dp(i-1,x,y)=1，则 dp(i,j,k)=1。

如此便能确定先知道答案的人的解了。接下来需要注意，一个人知道了，另一个人必须在下一回合也知道，否则就再也无法知道了。根据和上面类似的方式判一下就可以得到答案了。

感觉一下，t 很小，答案大概不会很大。

时间复杂度 O(s^3t)，常数小，甚至不需要提交答案。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=501;
bool dp[16][MAXN][MAXN];
int s,t;
char na[10];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s>>na>>t;
    bool now=(na[0]=='A');
    F(i,0,t){
        F(j,s,MAXN-1) F(k,j,MAXN-1){
            if(i>=2&&dp[i-2][j][k]) dp[i][j][k]=1;
            else{
                bool qwq=(i==0||!dp[i-1][j][k]);
                if(now) for(int x=s;qwq&&x*x<=j*k;++x) qwq&=((j*k%x)||x==j||(i&&dp[i-1][x][j*k/x]));
                else for(int x=s;qwq&&x+x<=j+k;++x) qwq&=(x==j||(i&&dp[i-1][x][j+k-x]));
                dp[i][j][k]=qwq;
            }
        }
        now^=1;
    }
    F(sum,s+s,MAXN*2) F(m,s,sum-s){
        int n=sum-m;
        if(m>n) break;
        if(!dp[t][m][n]||dp[t-1][m][n]||dp[t-2][m][n]) continue;
        bool qwq=1;
        if(now) for(int x=s;qwq&&x*x<=m*n;++x) qwq&=((m*n%x)||x==m||!dp[t][x][m*n/x]||dp[t-2][x][m*n/x]);
        else for(int x=s;qwq&&x*x<=m*n;++x) qwq&=(x==m||!dp[t][x][m+n-x]||dp[t-2][x][m+n-x]);
        if(qwq) return cout<<m<<" "<<n,0;
    }
    return 0;
}

Day 76

新年第一天，祭祀保平安。

2025/01/01 [CTSC2008] 祭祀

题意

给定一个 n 个点 m 条边的 DAG，求其最长反链大小，构造方案，并求出所有可能在最长反链中的点。

最长反链定义为一个点集满足任意两个点 u,v 都不能从 u 到达 v。

思路

问题转化为求最小链覆盖。

可重比较麻烦，所以先用传递闭包求出两点之间的可达性，然后建 n 个点的新图，i,j 连有向边当且仅当 i 可以到达 j。

然后新图上的最小不可重路径覆盖就是原图上的最小链覆盖了。

最小不可重路径覆盖是一个经典问题。建二分图，左部 i 向右部 j 连边当且仅当新图中 i 向 j 连边。这个二分图的点数减最大匹配就是答案。

感性理解，初始时每个点都有一条路径，匹配中的一条边就是把两个路径首尾相接变成一个。

然后回答第三问，判断一个点是否能够在最长反链中。这个也简单，删掉能到达这个点的点、这个点本身和这个点能到达的点，强制让这个点在最长反链中，然后求剩下的点构成的图的最长反链大小，如果是第一问的答案减一就可以。

第二问可以用第三问搞。每次选择一个剩下的能够在最长反链中的点，然后把能到达这个点的点、这个点本身和这个点能到达的点删掉，重复这个操作就行。

使用匈牙利算法，时间复杂度 O(n^4)，根本跑不满。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=101;
int n,m,match[MAXN];
bool reach[MAXN][MAXN];
vector<int>g[MAXN],gt[MAXN];
bool vis[MAXN],del[MAXN];
inline void bfs(int bg,bool type=1){
    if(type) memset(del,0,sizeof(bool)*(n+1));
    queue<int>q;
    q.push(bg),del[bg]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i:g[now]) if(!del[i]) del[i]=1,q.push(i);
    }
    q.push(bg);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i:gt[now]) if(!del[i]) del[i]=1,q.push(i);
    }
    return;
}
bool xyl(int now){
    if(vis[now]) return 0;
    vis[now]=1;
    for(int i:gt[now]) if(!del[i]&&(!match[i]||xyl(match[i]))){
        match[i]=now;
        return 1;
    }
    return 0;
}
int ans;
bool q2[MAXN],q3[MAXN];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    F(i,1,m){
        int u,v;
        cin>>u>>v;
        reach[u][v]=1;
    }
    F(k,1,n) F(i,1,n) F(j,1,n) reach[i][j]|=reach[i][k]&reach[k][j];
    F(i,1,n) F(j,1,n) if(reach[i][j]) g[i].push_back(j),gt[j].push_back(i);
    F(i,1,n){
        memset(vis,0,sizeof(bool)*(n+1));
        ans+=xyl(i);
    }
    cout<<n-ans<<"\n";
    F(i,1,n){
        int all=0,qwq=0;
        bfs(i);
        memset(match,0,sizeof(int)*(n+1));
        F(j,1,n) if(!del[j]){
            memset(vis,0,sizeof(bool)*(n+1));
            ++all,qwq+=xyl(j);
        }
        if(all-qwq==n-ans-1) q3[i]=1;
    }
    memset(del,0,sizeof(bool)*(n+1));
    F(i,1,n) if(q3[i]&&!del[i]) q2[i]=1,bfs(i,0);
    F(i,1,n) cout<<q2[i];
    cout<<"\n";
    F(i,1,n) cout<<q3[i];
    return 0;
}

Day 77

神秘乱搞题。

2024/01/04 [BJOI2014] 想法

题意

初始有 m 个集合，第 i 个包含元素 i。进行 n-m 次操作，每次合并两个集合成第 i+m 个集合并允许一定误差地查询集合大小。

思路

允许误差考虑乱搞。

给第 i 个元素赋随机 [0,1] 实数权，维护每个集合的最小值。

这个最小值的期望是集合大小加 1 分之 1，多跑几次求平均值。

好简洁啊。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=1e6+1,CNT=200;
const ll RANGE=1e18;
int n,m,u[MAXN],v[MAXN];
double val[MAXN],ans[MAXN];
mt19937 gen(time(0)^*new int);
uniform_real_distribution<double>rnd(0,1);
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    F(i,m+1,n) cin>>u[i]>>v[i];
    F(T,1,CNT){
        F(i,1,m) val[i]=rnd(gen);
        F(i,m+1,n) val[i]=min(val[u[i]],val[v[i]]),ans[i]+=val[i];
    }
    F(i,m+1,n) ans[i]/=CNT;
    F(i,m+1,n) cout<<int(1/ans[i]-0.5)<<"\n";
    return 0;
}

Day 78

AT 的图论计数题都好厉害。

2025/01/06 [AGC065F] Always Perfect

题意

求出点数为 N 且所有生成树都存在完美匹配的有标号无向连通图的数量,对大质数 M 取模。

思路

这种条件非常复杂的题目，先研究如何判定。

对一个合法的图的每个点双考虑。设 S_u 表示 u 和点双外部挂在 u 上的点的个数。

容易发现，对于所有点双中的点 u，我们有 S_u 的奇偶性相同。否则，我们必然可以找到两个点 u,v，其中 2|S_u,2\nmid S_v，满足 u,v 相邻。此时 u 已经和外面某个挂的点匹配了，v 没有。让生成树里保留边 (u,v)，v 就永远匹配不了。

如果所有 S_u 都是偶数，所有点都和外面挂着的某个点匹配，没有限制。

否则，所有点都在点双内匹配。首先点数是偶数，这是容易的。然后每个点度数 \le2，下面使用反证证明。假设 u 连了 v_1,v_2,v_3，考虑这样两棵生成树：连 (u,v_1)，v_1,v_2 用不经过 u 的路径与 v_3 连通；然后断开 (u,v_1)，连 (u,v_2)。如果这两个都有完美匹配，代表以 v_3 为根时 v_1,v_2 都在自己的子树内部匹配。于是断开 v_1,v_2 连向父亲的边，连 (u,v_1),(u,v_2),(u,v_3)，这个生成树没法把 u,v_1,v_2 都匹配掉，矛盾。

综上所述，如果 S_u 都是奇数，这个点双一定是偶环或者两点一边。称这两个结构是一个新点。

根据上面的讨论，可以使用如下方式不重不漏构造出所有合法的图：初始时是若干新点；每次选择 \ge2 个连通块，每个连通块中选出一个点，连成点双；连通时停止。

这个图在新点的意义下是一个有若干点双的有标号连通图。

终于可以开始计数了。先计算 n 个点 m 个点双的连通图数量 f(n,m) 和 n 个点连通图数量 g(n)。注意区分 n,N。

先是 g(n) 的转移。可以写暴力多项式求 \ln，也可以容斥。具体地，枚举包含节点 1 的极大连通块，剩下的随意连边，有：

其中 i 是极大连通块大小，\dbinom{n-1}{i-1} 是给连通块里的点分配标号，2 的幂是内部随意连边的方案数。

• b_i-c_i\le y
• c_i-a_i\le z

思路

首先是一个我不知道怎么想到的转化。设 m=x+y+z+3，原题意等价于有一个长为 m 的环，点顺时针编号 0,1,\cdots,m，初始时有三个人分别在 0,x+1,x+y+2 号点，每一时刻可以选择一个人顺时针走一步，要求任意两个人走的过程中都不重合，求到 n 时刻的合法移动方式的方案数，不同定义为存在一个时刻走的人不同。

还是不好做，那就容斥，总方案数 3^n，计算有重合的方案数。那么容斥系数是什么？

这个容斥系数感觉重合次数感觉有关系，但这样看来更麻烦了。答案模 2 还没有用上，怎么用？

发现第一次两个人重合后，接下来无论方案是什么，我总能交换两个人走的时刻得到另一种方案，除非接下来这两个人不走。也就是说，只要这两个人走了，答案就是偶数，不必（注意不是不能）计算。

因此，只有两个人第一次重合后不走的方案才有贡献。“第一次”有点麻烦，放宽到第 n 时刻重合，反正多出来的方案是偶数不会产生贡献。

减掉两两重合的情况，你发现三个重合的情况被多减了 2，但是模 2 把这一项模没了，所以答案是两两重合的方案数的奇偶性异或起来再异或 1，因为 3^n 是奇数。

接下来就是要计算两两重合的方案了。不妨讨论是第一个人和第二个人，其他情况把讨论的 x 换成 y,z 即可。

这两个人具体在哪个点我们不关心，我们只关心差。发现每一时刻差都可以 +1,-1 或不变，初始差为 x+1，最终差为 0，能用生成函数描述，即方案数为 [t^{x+1}]((t^{-1}+1+t)^n\bmod (t^m-1))。由于用过 x,z 了所以形式幂级数用 t 表示，模 (t^m-1) 是因为这是个环所以是循环卷积。

接下来是第二个我不会的转化。我们有经典结论（真的经典吗我没见过啊）：(t^{-1}+1+t)^{2^k}\equiv t^{-2^k}+1+t^{2^k}\pmod 2。

使用归纳证明。k=0 时显然满足，假设 k=K 满足，则 (t^{-1}+1+t)^{2^{K+1}}=\left((t^{-1}+1+t)^{2^K}\right)^2\equiv(t^{-2^K}+1+t^{2^K})^2\pmod2。根据三项式定理 (a+b+c)^2=a^2+b^2+c^2+2(ab+ac+bc)，后面的交叉项全部被模 2 消掉了，只剩下平方项，因此有 (t^{-1}+1+t)^{2^{K+1}}\equiv t^{-2^{K+1}}+1+t^{2^{K+1}}\pmod2，即 k=K+1 时也成立。

把 n 二进制下第 i 位是 1 记为 i\in n，则答案为 [t^{x+1}](\prod\limits_{i\in n}(t^{-2^i}+1+t^{2^i})\bmod (t^m-1))。这是 O(\log n) 个 O(1) 项的多项式循环卷积，直接暴力复杂度是 O(m\log n) 的。

发现把循环卷积去掉，对答案有贡献的项只有 O(\dfrac n m) 个。我们希望能 O(\log n) 求出第 e\equiv x+1\pmod m 项的系数。

为了去掉负指数，把多项式乘上 t^n，则每个多项式形如 1+x^{2^i}+x^{2^{i+1}}。这相当于背包问题。所以把 e 二进制拆分做数位 dp，设 dp(i,0/1) 表示考虑选取物品大小之和从小往大第 i 位，第 i 位选择/没有选择大小为 2^{i+1} 的物品。转移就是看第 i 位选什么能凑到和 e 的第 i 位相同。这样的时间复杂度是 O(\dfrac n m\log n)。

根号分治，m\le \sqrt n 时跑 O(m\log n) 的做法，否则跑 O(\dfrac n m\log n) 的做法，总的时间复杂度为 O(T\sqrt n\log n)。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=31,MAXM=50000;
ll n,m;
bool ans;
namespace Small{
    bool poly[MAXM],qwq[MAXM];
    inline void main(ll x){
        memset(poly,0,sizeof(bool)*m);
        poly[0]=1;
        F(i,0,MAXN-1) if(n>>i&1){
            ll e=(1<<i)%m;
            memcpy(qwq,poly,sizeof(bool)*m);
            F(j,0,m-1) if(poly[j]) qwq[(j+m-e)%m]^=1,qwq[(j+e)%m]^=1;
            swap(qwq,poly);
        } 
        ans^=poly[(x+1)%m];
        return;
    }
}
namespace Large{
    bool dp[MAXN][2]={};
    inline void getdp(ll e){
        if(n&1){
            if(e&1) dp[0][0]=1,dp[0][1]=0;
            else dp[0][0]=1,dp[0][1]=1;
        }else{
            if(e&1) dp[0][0]=0;
            else dp[0][0]=1;
            dp[0][1]=0;
        }
        F(i,1,MAXN-1){
            if(n>>i&1){
                if(e>>i&1){
                    dp[i][0]=dp[i-1][0]^dp[i-1][1];
                    dp[i][1]=dp[i-1][1];
                }else{
                    dp[i][0]=dp[i-1][0];
                    dp[i][1]=dp[i-1][0]^dp[i-1][1];
                }
            }else{
                if(e>>i&1) dp[i][0]=dp[i-1][1];
                else dp[i][0]=dp[i-1][0];
                dp[i][1]=0;
            }
        }
        ans^=dp[MAXN-1][0];
        return;
    }
    inline void main(ll x){
        ll rem=(x+1+n)%m;
        for(ll e=rem;e<=2*n;e+=m) getdp(e);
        return;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    for(cin>>T;T;--T){
        ll x,y,z;
        cin>>n>>x>>y>>z;
        m=x+y+z+3;
        ans=1;
        if(m*m<=n) Small::main(x),Small::main(y),Small::main(z);
        else Large::main(x),Large::main(y),Large::main(z);
        cout<<ans<<"\n";
    }
    return 0;
}

后记

在集训快走的时候完成了蜜月日记 Part8。我还挺希望写到 Day 100 的，希望自己能坚持到那个时候。