lhsx 2024

aeiouaoeiu / 2024-03-17 / 原文

省流：除了 D1T1 都是贺的。

D1T1

（直接搬了自己单独写的题解，所以比较长）

首先整理式子，把 $x_i$ 和 $x_i'$ 分开。

$\sum\limits_{i=0}^{m-1}x_i'=x-\sum\limits_{i=0}^{m-1}x_{i \bmod n}$；
$\sum\limits_{i=0}^{m-1}y_i'=y-\sum\limits_{i=0}^{m-1}y_{i \bmod n}$。

看到 $|x_i'|+|y_i'|\le k$，我们不妨将 $x'$ 和 $y'$ 放到一起考虑。

$\sum\limits_{i=0}^{m-1}(x_i'+y_i')=x-\sum\limits_{i=0}^{m-1}x_{i \bmod n}+y-\sum\limits_{i=0}^{m-1}y_{i \bmod n}$。

但是这个式子显然是不能囊括所有情况的。

例如，当 $x-\sum\limits_{i=0}^{m-1}x_{i \bmod n}<0,y-\sum\limits_{i=0}^{m-1}y_{i \bmod n}>0$ 时，两者加在一起反倒会让目标距离更短，不一定合法。

思考我们关注的是什么，距离。坐标可正可负，但是走到目标所需的距离一定是非负整数。

于是我们给上式加上绝对值，变成凑距离的形式。同时，我们贪心地想，对于每个 $i$，$(x_i'+y_i')$ 直接取 $k$ 一定不劣，于是我们可以继续修改式子。

$mk\ge|x-\sum\limits_{i=0}^{m-1}x_{i \bmod n}|+|y-\sum\limits_{i=0}^{m-1}y_{i \bmod n}|$。

但是单这样还不够，$m$ 可能非常大，暴力枚举是无法承受的。

考虑到一个 $x_i$ 在 $m$ 足够大时会重复出现多次，不妨令 $m=qn+p$，再预处理 $x,y$ 数组的前缀和 $sx,sy$，可以化简式子。

$(qn+p)k\ge|x-sx_p-q\cdot sx_{n-1}|+|y-sy_p-q\cdot sy_{n-1}|$。

不妨设 $f_x(q)=|x-sx_p-q\cdot sx_{n-1}|,f_y(q)=|y-sy_p-q\cdot sy_{n-1}|$ 的函数值为 $0$ 时分别有 $\lfloor q\rfloor=xz,yz$。

对 $f_x(q)$ 进行分讨：

$0\le q\le xz$，此时 $q$ 的增长给 $f_x(q)$ 带来了负收益。
$q>xz$，此时 $q$ 的增长给 $f_x(q)$ 带来了正收益。

$f_y(q)$ 同理。

两个函数均呈先单调减后单调增的趋势（由于 $q\ge0$ 所以有可能出现没有单调减的情况）。此时将两个函数组合，形成了三部分，内容是类似的。

我们需要实现一个函数 check(l,r,p,xd,yd) 能够求出在 $l\le q\le r$，$f_x(q)-f_x(q-1)=xd\cdot sx_{n-1},f_y(q)-f_y(q-1)=yd\cdot sy_{n-1}$ 时，$q$ 的最小值。

根据函数传入的参数，我们可以知道当 $q\to q+1$ 时，$f_x(q)+f_y(q)$ 的增/减量为 $\Delta=xd\cdot sx_{n-1}+yd\cdot sy_{n-1}$。

我们设 $sum=(ln+p+1)k,bas=f_x(l)+f_y(l),R=q-l$。则我们要解一个不等式 $sum+nkR\ge bas+R\Delta$，最小的正整数解为 $R=\lceil\dfrac{bas-sum}{nk-\Delta}\rceil$。

最后判断 $l+R$ 是否出界即可。上述过程均是 $\mathcal O(1)$ 的，我们 $\mathcal O(n)$ 地枚举 $p$ 并求出最小的 $q$，最后的答案即为所有 $p$ 中最小的 $q$。

时间复杂度：$\mathcal O(Tn)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 LL;
const ll maxn=1000007,ee=1000000000000000007ll;
ll n,k,xg,yg,X[maxn],Y[maxn],sx[maxn],sy[maxn],val[maxn],ans;
LL myabs(LL x){return (x>0?x:-x);}
ll checkseg(ll l,ll r,ll p,ll xd,ll yd){
    if(l>r) return ee;
    LL sum=((LL)l*n+p+1)*(LL)k,bas=myabs(xg-sx[p+1]-(LL)l*sx[n])+myabs(yg-sy[p+1]-(LL)l*sy[n]),delt=xd*sx[n]+yd*sy[n];
    if(bas<=sum) return l*n+p+1; if(delt>=(LL)n*k) return ee;
    LL res=(bas-sum+(LL)n*(LL)k-delt-1)/((LL)n*(LL)k-delt); if(l+res>r) return ee; return (l+res)*n+p+1;
}
void solve(void){
    for(ll i=0,xz,yz,xt,yt;i<n;i++){
        if(val[i+1]!=ee) continue; xz=-1,yz=-1;
        if(sx[n]) xz=max((xg-sx[i+1])/sx[n],0ll); if(sy[n]) yz=max((yg-sy[i+1])/sy[n],0ll);
        if(xz>yz){
            val[i+1]=checkseg(0,yz,i,(sx[n]>0?-1:1),(sy[n]>0?-1:1)); if(val[i+1]!=ee) continue;
            val[i+1]=checkseg(yz+1,xz,i,(sx[n]>0?-1:1),(sy[n]>0?1:-1)); if(val[i+1]!=ee) continue;
            val[i+1]=checkseg(xz+1,ee,i,(sx[n]>0?1:-1),(sy[n]>0?1:-1));
        }else{
            val[i+1]=checkseg(0,xz,i,(sx[n]>0?-1:1),(sy[n]>0?-1:1)); if(val[i+1]!=ee) continue;
            val[i+1]=checkseg(xz+1,yz,i,(sx[n]>0?1:-1),(sy[n]>0?-1:1)); if(val[i+1]!=ee) continue;
            val[i+1]=checkseg(yz+1,ee,i,(sx[n]>0?1:-1),(sy[n]>0?1:-1));
        }
    }
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll Tccs=1;
    cin>>Tccs;
    for(ll tcs=1;tcs<=Tccs;tcs++){
        cin>>n>>k>>xg>>yg; ans=ee;
        for(int i=1;i<=n;i++) cin>>X[i]>>Y[i],sx[i]=sx[i-1]+X[i],sy[i]=sy[i-1]+Y[i],val[i]=ee;
        if(xg==0&&yg==0){cout<<"0\n"; continue;}
        else solve();
        for(int i=1;i<=n;i++) ans=min(ans,val[i]);
        cout<<(ans>=ee?-1:ans)<<"\n";
    }
    return 0;
}

D1T2

考虑建出 trie 树。

我们从高位到低位考虑 $x$ 的取值，顺便得出 $S$ 的最优取法。

设点 $u$ 的子树中 $a_i$ 最小值为 $mn_u$，$b_i$ 和为 $s_u$。

设 $x=\overline{x_{k-1}x_{k-2}\ldots x_0}$，我们考虑到 $x_d$。考虑当 $x_d=0$ 时我们怎么让答案的对应一位为 $1$。

此时若不在 $S$ 中加入，$u$ 的左子树将会贡献 $0$，考虑将所有在 $u$ 左子树内的数加入 $S$，则此时需要满足两个加入的条件：

$s_\text{lson}$ 小于当前钱数。
在最好情况（$x$ 未确定位均为 $1$）下 $mn_\text{lson}$ 大于等于当前已经确定的答案（未确定部分设为 $0$）。

若上述条件均满足，则答案的对应一位可以取 $1$，此时由于左子树已经全部被取，不需要遍历左子树。

$x_d=1$ 同理。若两种情况都不能让答案对应一位为 $1$，则答案对应一位此时显然为 $0$，我们需要遍历两边子树。

时间复杂度：最坏情况下遍历了整棵树，故为 $\mathcal{O}(nk)$。当然大多数情况下跑不满。

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
typedef __int128 LL;
const ll maxn=12000007,ee=1000000000000000007ll;
void read(LL &x){
    // read a __int128 variable
    char c; bool f = 0;
    while(((c = getchar()) < '0' || c > '9') && c != '-');
    if(c == '-'){f = 1; c = getchar();}
    x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')x = x * 10 + c - '0';
    if(f) x = -x;
}
void write(LL x){
    // print a __int128 variable
    if(x < 0){putchar('-'); x = -x;}
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
ll n,m,k,b[maxn],nxt[maxn][2],sum[maxn],cnt;
LL a[maxn],mn[maxn],ans,cap;
void insert(LL x,ll id){
    ll u=1; mn[1]=min(mn[1],x),sum[1]+=b[id];
    for(int i=k,c;i>=1;i--){
        c=(x>>(i-1))&1;
        if(!nxt[u][c]) nxt[u][c]=++cnt,mn[cnt]=cap;
        u=nxt[u][c],mn[u]=min(mn[u],x),sum[u]+=b[id];
    }
}
LL solve(ll dep,ll u,ll cm,LL cx,LL cmn,LL ans){
    if(dep<0) return ans; LL tp=(LL)1<<dep,ful=tp-1;
    if(u==0) return cmn+(cx|tp|ful); LL res=0;
    if(sum[nxt[u][0]]<=cm&&(ans|tp)<=((cx|ful)+min(cmn,mn[nxt[u][0]]))) res=max(res,solve(dep-1,nxt[u][1],cm-sum[nxt[u][0]],cx,min(cmn,mn[nxt[u][0]]),ans|tp));
    if(sum[nxt[u][1]]<=cm&&(ans|tp)<=((cx|ful|tp)+min(cmn,mn[nxt[u][1]]))) res=max(res,solve(dep-1,nxt[u][0],cm-sum[nxt[u][1]],cx|tp,min(cmn,mn[nxt[u][1]]),ans|tp));
    if(res) return res;
    return max(solve(dep-1,nxt[u][0],cm,cx,cmn,ans),solve(dep-1,nxt[u][1],cm,cx|tp,cmn,ans));
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    //ios::sync_with_stdio(0),cin.tie(0);
    ll Id,Tccs=1;
    cin>>Id>>Tccs;
    for(ll tcs=1;tcs<=Tccs;tcs++){
        for(int i=1;i<=cnt;i++) sum[i]=nxt[i][0]=nxt[i][1]=0;
        cin>>n>>m>>k; mn[0]=mn[1]=cap=(LL)1<<k,cnt=1;
        for(int i=1;i<=n;i++) read(a[i]);
        for(int i=1;i<=n;i++) cin>>b[i];
        for(int i=1;i<=n;i++) insert(a[i],i);
        write(((sum[1]<=m)?(mn[1]+cap-1):solve(k-1,1,m,0,cap,0))),puts("");
    }
    return 0;
}

D1T3

将两个连通块合并时发生了什么？

若两个连通块中分别有边 $(u_1,v_1,x),(u_2,v_2,x)$，且我们已经知道有边 $(u_1,u_2,x+1)$，则必然有边 $(v_1,v_2,x+1)$。

据此可以推出一个结论：

若两个连通块可合并，则两个连通块必然大小相等并且同构。

这里给出同构的定义：

对于两个边编号为 $1\sim m$ 的连通块 $(V_1,E_1),(V_2,E_2)$，两个连通块同构，当且仅当：

$|V_1|=|V_2|\wedge |E_1|=|E_2|$。

存在长度分别为 $V_1,V_2$ 的排列 $p,q$，使得对于任意的 $1\le i\le V_1,1\le x\le m$，同时存在边 $(p_i,p_j,x)$ 与 $(q_i,q_j,x)$。

如何高效判断两个连通块是否同构？我们可以观察到一个性质：

对于一个边编号为 $1\sim m$ 的连通块 $(V,E)$，对于所有 $1\le i\le m$，在留下所有编号为 $i$ 的边后，形成的连通块 $(V_1,E_1),\ldots,(V_t,E_t)$ 两两同构。

可以用归纳法证明。证明出这个性质后我们可以用哈希进行高效判断，从一个点开始分别单独对一个编号的边进行搜索，记录并比较搜索序即可。

每一类同构连通块都是独立的，所以我们只需要分别求出每一类的方案数即可。

求出一类连通块的方案数可以考虑使用 dp。

设 $f_{i,j,l}$ 为有 $i$ 个连通块，大小都为 $l$ ，将所有连通块都用编号为 $1\sim j$ 的边连在一起的方案数。

我们有：

\[f_{i,j,l}=\displaystyle{\sum_{d|i}f_{d,j-1,\frac{il}{d}}\times T(i,d)\times l^{i-d+1}} \]

其中， $d$ 是枚举原先状态的连通块数量，$T(i,d)$ 表示把 $i$ 个物品划分为 $d$ 个大小相同的圆排列的方案数，$l^{i-d+1}$ 表示连边方案数。

\[T(i,d)=\displaystyle{\prod_{x=1}^{d}\binom{\frac{xi}{d}-1}{\frac id-1}(\frac id-1)!} \]

初始状态是 $f_{1,0,l}=1$，考虑化简式子，我们有一个关键结论：

$f_{i,j,l}=f_{i,j,1}\times l^{i+j-1}$。

可以用归纳法证明，这样我们干掉了一维。

\[f_{i,j}=\displaystyle{\sum_{d|i}f_{d,j-1}\times T(i,d)\times (\frac id)^{d+j-2}} \]

然后我们考虑化简 $T(i,d)$。

\[\begin{aligned} T(i,d)&=\displaystyle{\prod_{x=1}^{d}\binom{\frac{xi}{d}-1}{\frac id-1}(\frac id-1)!}\\ &=\displaystyle{\prod_{x=1}^{d}{\frac{(\frac{xi-d}{d})!}{(\frac{xi-i}{d})!}}}\\ &=\frac{(i-1)!}{\prod_{x=1}^{d-1}{\frac{xi}{d}}}\\ &=\frac{(i-1)!}{(d-1)!(\frac id)^{d-1}} \end{aligned} \]

将化简后式子带入 $f$ 的转移方程中，有：

\[\begin{aligned} f_{i,j}&=\displaystyle{\sum_{d|i}f_{d,j-1}\times \frac{(i-1)!}{(d-1)!(\frac id)^{d-1}}\times (\frac id)^{d+j-2}}\\ &=\displaystyle{\sum_{d|i}f_{d,j-1}\times \frac{(i-1)!}{(d-1)!}\times (\frac id)^{j-1}}\\ \end{aligned} \]

这时我们令 $g_{i,j}=\displaystyle{\frac{f_{i,j}}{(i-1)!i^{j-1}}}$，$g_{i,1}=1$。

那么有 $f_{i,j}=g_{i,j}(i-1)!i^{j-1}$，有：

\[\begin{aligned} f_{i,j}&=\displaystyle{\sum_{d|i}f_{d,j-1}\times \frac{(i-1)!}{(d-1)!}\times (\frac id)^{j-1}}\\ &=\displaystyle{\sum_{d|i}g_{d,j-1}(d-1)!d^{j-2}\times \frac{(i-1)!}{(d-1)!}\times (\frac id)^{j-1}}\\ &=\displaystyle{\sum_{d|i}g_{d,j-1}\times (i-1)!\times i^{j-1}}\times \frac 1d\\ g_{i,j}&=\displaystyle{\frac{f_{i,j}}{(i-1)!i^{j-1}}}\\ &=\displaystyle{\sum_{d|i}\frac{g_{d,j-1}}{d}} \end{aligned} \]

考虑此时 $g_{i,j}$ 的组合意义，实际上求的是对于满足 $a_1=1,a_j|i,a_{x-1}|a_x$ 的长度为 $j$ 的序列 $a$，求所有 $F(a)=\prod_{x=1}^{j}\frac{1}{a_x}$ 的和。

考虑将 $g$ 的转移式表示为两个 $j$ 合并的形式，枚举两个序列的连接处，有：

\[g_{i,j_1+j_2}=\sum_{d|i}\frac{g_{i,j_1}g_{\frac{i}{d},j_2}}{d^{j_2}} \]

可以通过倍增 $\mathcal O(n\log n\log k)$ 地求出 $f_{i,k}$ 的值。

总时间复杂度：$\mathcal O(n^2+nm+n\log n\log k)$。