时间戳

首页 > 技术文章 > WC2019

WC2019

cjoierShiina-Mashiro 2020-01-04 22:49 原文

数树

Luogu
LOJ
UOJ
不管怎样先特判\(y=1\)的情况。
先考虑固定一棵树的情况。
设固定的树的边集为\(E_1\)，枚举的树的边集为\(E_2\)。
设\(f(T)=y^{n-|T|}\)，那么\(ans=\sum\limits_{E_2}f(E_1\cap E_2)\)。
考虑经典子集反演

\[f(T)=\sum\limits_{S\subseteq T}\sum\limits_{R\subseteq S}(-1)^{|S|-|R|}f(R) \]

因此我们有

\[ans=\sum\limits_{E_2}\sum\limits_{S\subseteq E_1\wedge S\subseteq E_2}\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}y^{n-|T|}=\sum\limits_{S\subseteq E_1}(\sum\limits_{S\subseteq E_2}1)\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}y^{n-|T|} \]

设\(g(S)=\sum\limits_{S\subseteq E_2}1\)即包含\(S\)的树的个数，则有

\[ans=\sum\limits_{S\subseteq E_1}g(S)\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}y^{n-|T|}=\sum\limits_{S\subseteq E_1}g(S)y^{n-|S|}\sum\limits_{T\subseteq S}(-y)^{|S|-|T|}=\sum\limits_{S\subseteq E_1}g(S)y^{n-|S|}(1-y)^{|S|} \]

推到这里差不多到底了，我们考虑一下\(g(S)\)。
假设\(S\)把\(n\)个点分成了\(m\)个连通块，每个连通块有\(a_i\)个点。
有点经验的话应该能够看出这是个Ex-Cayley定理的形式。
即\(g(S)=n^{m-2}\prod\limits_{i=1}^ma_i\)
我们把这个代进去，注意到\(n=|S|+m\)，同时为了方便我们记\(k=\frac{yn}{1-y}\)

\[ans=\sum\limits_{S\subseteq E_1}y^m(1-y)^{n-m}n^{m-2}\prod\limits_{i=1}^ma_i=\frac{(1-y)^n}{n^2}\sum\limits_{S\subseteq E_1}k^m\prod\limits_{i=1}^ma_i=\frac{(1-y)^n}{n^2}\sum\limits_{S\subseteq E_1}\prod\limits_{i=1}^mka_i \]

这告诉我们每个大小为\(a_i\)连通块会产生\(ka_i\)的贡献，而一个边集的贡献为它划分的连通块的贡献之积，我们要求的是所有边集的贡献之和。
考虑dp计算这个贡献，一维看上去不太够就设两维，令\(f_{u,i}\)表示只考虑\(u\)的子树，\(u\)所在连通块的大小为\(i\)的所有边集方案在忽略\(i\)所在连通块之后的的贡献之和。这个是经典的树上背包。
考虑优化，令\(g_u=k\sum\limits_iif_{u,i},F_u(x)=\sum\limits_if_{u,i}x^i\)，那么我们有

\[F_u(x)=x\prod\limits_v(g_v+F_v(x)),g_u=kF_u'(1) \]

计算可得

\[g_u=k\prod\limits_v(g_v+F_v(1))+\prod\limits_v(g_v+F_v(1))\sum\limits_v\frac{kF_v'(1)}{g_v+F_v(1)} \]

这里的\(F_v'(1)=g_v\)，因此我们只关心\(F_u(1)\)，而显然有\(F_u(1)=\prod\limits_v(g_v+F_v(1))\)。
再令\(h_u=F_u(1)=\sum\limits_if_{u,i}\)，那么可以得到

\[h_u=\prod\limits_v(g_v+h_v),g_u=h_u(k+\sum\limits_v\frac{g_v}{g_v+h_v}) \]

这样我们就可以直接\(O(n)\)计算出答案了。
顺带一提\(ans=\frac{(1-y)^n}{n^2}g_1\)。
现在考虑两棵树都未确定的情况。

\[ans=\sum\limits_{E_1}\sum\limits_{S\subseteq E_1}g(S)y^{n-|S|}(1-y)^{|S|}=\sum\limits_Sg(S)^2y^{n-|S|}(1-y)^{|S|} \]

这个式子和上面的差不多，但是注意\(S\)的枚举范围是所有森林。
我们考虑用和上面类似的方法展开\(g(S)\)，同时为了方便设\(k=\frac{yn^2}{1-y}\)，可以得到

\[ans=\frac{(1-y)^n}{n^4}\sum\limits_S\prod\limits_{i=1}^mka_i^2 \]

因为\(S\)的枚举范围已经没有限制了，所以我们考虑转而枚举连通块。
因为一棵\(a_i\)个点的树有\(a_i^{a_i-2}\)个，所以一个连通块的贡献是\(ka_i^{a_i}\)。
而我们知道森林的方案数的EGF就是连通块的方案数的EGF的\(\exp\)。
连通块的EGF为\(F(x)=\sum\limits_{i=0}^{+\infty}\frac{ki^i}{i!}x^i\)，森林的EGF就是\(G(x)=\exp(F(x))\)。
那么\(ans=\frac{(1-y)^n}{n^4}n![x^n]G(x)\)。

#include<bits/stdc++.h>
using ll=unsigned long long;
#define pi pair<int,int>
#define pb push_back
using namespace std;
const int N=262147,P=998244353;
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
int mod(int a){return a+(a>>31&P);}
int power(int a,int k){int r=1;for(;k;k>>=1,a=(ll)a*a%P)if(k&1)r=(ll)r*a%P;return r;}
int n,y,op;
namespace op0
{
    map<pi,int>mp;
    void main()
    {
	int ans=0;
	for(int i=1,u,v;i<n;++i) u=read(),v=read(),mp[pi{u,v}]=mp[pi{v,u}]=1;
	for(int i=1;i<n;++i) if(mp.count(pi{read(),read()})) ++ans;
	printf("%d",power(y,n-ans));
    }
}
namespace op1
{
    vector<int>E[N];
    int g[N],h[N],k;
    void dfs(int u,int fa)
    {
	h[u]=1,g[u]=k;
	for(int v:E[u])
	{
	    if(v==fa) continue;
	    dfs(v,u);
	    h[u]=(ll)h[u]*mod(g[v]+h[v]-P)%P,g[u]=mod(g[u]+(ll)g[v]%P*power(mod(g[v]+h[v]-P),P-2)%P-P);
	}
	g[u]=(ll)h[u]*g[u]%P;
    }
    void main()
    {
	if(y==1) return (void)(printf("%d",power(n,n-2)));
	for(int i=1,u,v;i<n;++i) u=read(),v=read(),E[u].pb(v),E[v].pb(u);
	k=(ll)y*n%P*power(mod(1-y),P-2)%P,dfs(1,0);
	printf("%d",(ll)g[1]%P*power(mod(1-y),n)%P*power(n,P-3)%P);
    }
}
namespace op2
{
    int inv[N],lim(1),rev[N],w[N],fac[N],ifac[N],f[N],g[N];
    int getlen(int n){return 1<<(32-__builtin_clz(n<<1));}
    void init(int n)
    {
	inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
	for(int i=2;i<=n;++i)inv[i]=(ll)(P-P/i)*inv[P%i]%P,fac[i]=(ll)fac[i-1]*i%P,ifac[i]=(ll)ifac[i-1]*inv[i]%P;
	n<<=1;
	int l(-1);
	while(lim<=n) lim<<=1,++l;
	for(int i=1;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
	int g(power(3,(P-1)>>(++l)));
	w[lim>>1]=1;
	for(int i=(lim>>1)+1;i<lim;++i) w[i]=(ll)w[i-1]*g%P;
	for(int i=(lim>>1)-1;i;--i) w[i]=w[i<<1];
	lim=l;
    }
    void NTT(int*a,int l,int f)
    {
	if(!f) reverse(a+1,a+l);
	static ll t[N];
	int u(lim-__builtin_ctz(l)),x,p(P-(P-1)/l);
	for(int i=0;i<l;++i) t[rev[i]>>u]=a[i];
	for(int i=1;i<l;i<<=1) for(int j=0,d=i<<1;j<l;j+=d) for(int k=0;k<i;++k) x=t[i+j+k]*w[i+k]%P,t[i+j+k]=t[j+k]+P-x,t[j+k]+=x;
	for(int i=0;i<l;++i) a[i]=t[i]%P;
	if(!f) for(int i=0;i<l;++i) a[i]=(ll)a[i]*p%P;
    }
    void Inv(int*a,int*b,int deg)
    {
	if(deg==1) return(void)(b[0]=power(a[0],P-2));
	static int t[N];
	Inv(a,b,(deg+1)>>1);
	int l(getlen(deg));
	memcpy(t,a,deg<<2),memset(t+deg,0,(l-deg)<<2),NTT(t,l,1),NTT(b,l,1);
	for(int i=0;i<l;++i) b[i]=(ll)mod(2-(ll)b[i]*t[i]%P)*b[i]%P;
	NTT(b,l,0),memset(b+deg,0,(l-deg)<<2);
    }
    void Der(int*a,int*b,int deg){for(int i=1;i<deg;++i)b[i-1]=(ll)a[i]*i%P;b[deg-1]=0;}
    void Int(int*a,int*b,int deg){for(int i=1;i<deg;++i)b[i]=(ll)a[i-1]*inv[i]%P;b[0]=0;}
    void Ln(int*a,int*b,int deg)
    {
	static int t[N];int l(getlen(deg));
	Inv(a,t,deg),Der(a,b,deg);
	NTT(t,l,1),NTT(b,l,1);
	for(int i=0;i<l;++i) t[i]=(ll)t[i]*b[i]%P;
	NTT(t,l,0),Int(t,b,deg),memset(t,0,l<<2),memset(b+deg,0,(l-deg)<<2);
    }
    void Exp(int*a,int*b,int deg)
    {
	if(deg==1) return(void)(b[0]=1);
	static int t[N];
	Exp(a,b,(deg+1)>>1),Ln(b,t,deg);
	int l(getlen(deg));
	for(int i=0;i<deg;++i) t[i]=mod(a[i]-t[i]);
	memset(t+deg,0,(l-deg)<<2),++t[0];
	NTT(t,l,1),NTT(b,l,1);
	for(int i=0;i<l;++i) b[i]=(ll)b[i]*t[i]%P;
	NTT(b,l,0),memset(b+deg,0,(l-deg)<<2),memset(t+deg,0,(l-deg)<<2);
    }
    void main()
    {
	if(y==1) return (void)(printf("%d",power(n,2*n-4)));
	init(n+1);int k=(ll)y*n%P*n%P*power(mod(1-y),P-2)%P;
	for(int i=1;i<=n;++i) f[i]=(ll)k*power(i,i)%P*ifac[i]%P;
	Exp(f,g,n+1),printf("%d",(ll)g[n]*fac[n]%P*power(mod(1-y),n)%P*power(n,P-5)%P);
    }
}
int main()
{
    n=read(),y=read(),op=read();
    if(op==0) return op0::main(),0;
    if(op==1) return op1::main(),0;
    if(op==2) return op2::main(),0;
}

远古计算机

Luogu
LOJ
UOJ
第一个点直接写，第二个点打表，第三个点最短路，第四个点打个时间戳然后最短路，第五个点开两维跑\(10\)遍最短路。

I君的商店

Luogu
LOJ
UOJ
一个非常自然的想法是先排序然后二分找一下。
信息论告诉我们基于比较的排序是不低于\(O(n\log n)\)的。
但是因为这个序列的元素都是\(0,1\)，所以我们可以构造一个更加优秀的办法。
考虑构造一个可以容纳确定不是\(0\)的数并且单调不减的序列。
先把\(0\)扔进序列，用\(a\)表示这个序列的最后一个元素。
然后我们先令\(x=1,y=2\)。
从前往后枚举\(3,\cdots,n\)。
先进行一次比较，令\(v_x\le v_y\)。
然后如果有\(v_a\ge v_x+v_y\)，那么说明有\(v_x=0\)，\(x\)可以不管了，我们令\(x=i\)。
否则有\(v_y\ge v_a\)，我们把\(y\)扔进序列，即令\(a=y\)，并且令\(y=i\)。
做完之后我们把序列reverse一下，那么这个序列就是前面一段\(1\)后面一段\(0\)了。
\(x,y\)满足一个是\(n\)另一个还没扔进序列，不妨令\(x\)为没扔进序列的那个。
比较一次序列首端和\(x\)找到确定的一个\(1\)。
然后通过二分找到最后一个可能是\(1\)的位置。具体的话每次比较确定的那个\(1\)和\(v_{mid}+v_{mid+1}\)的大小就行了。
然后根据奇偶性什么的稍微判断一下留下来的\(x\)和最后那个可能的\(1\)到底是不是\(1\)。
同时序列的前缀\(1\)也已经被我们找出来了。
这样就做完了。
记得特判序列单调的那一档。

#include<algorithm>
#include<cstring>
#include<numeric>
#include"shop.h"
const int N=100007;
using std::reverse;
using std::swap;
int id[N];
int cmp1(int a,int b){static int S[1],T[1];S[0]=a,T[0]=b;return query(T,1,S,1);}
int cmp2(int a,int b,int c){static int S[1],T[2];S[0]=a,T[0]=b,T[1]=c;return query(T,2,S,1);}
void find_price(int tid,int n,int k,int ans[])
{
    int i,l,r,mid;
    if(n<=2||tid==3)
    {
	for(int i=0;i<n;++i) id[i]=i;
	if(!cmp1(0,n-1)) reverse(id,id+n);
	for(l=0,r=n;l+1<r;) if((mid=(l+r)>>1)<n-1&&!cmp2(id[0],id[mid],id[mid+1])) l=mid; else r=mid;
	ans[id[r]]=(l+1-k)&1;
	for(int i=0;i<=l;++i) ans[id[i]]=1;
	return ;
    }
    int tot=0,x=1,y=2,a=0,mx;
    id[tot++]=0;
    for(i=3;i<=n;++i)
    {
	if(cmp1(x,y)) swap(x,y);
	if(cmp2(a,x,y)) x=i;
	else id[tot++]=a=y,y=i;
    }
    reverse(id,id+tot),x=x<n? x:y,mx=cmp1(id[0],x)? id[0]:x;
    for(l=0,r=tot;l+1<r;) if((mid=(l+r)>>1)<tot-1&&!cmp2(mx,id[mid],id[mid+1])) l=mid; else r=mid;
    if((l+1-k)&1) ans[cmp1(id[r],x)? id[r]:x]=1;
    else if(!cmp2(mx,id[r],x)) ans[id[r]]=ans[x]=1;
    for(int i=0;i<=l;++i) ans[id[i]]=1;
}

推荐阅读