数树
Luogu
LOJ
UOJ
不管怎样先特判(y=1)的情况。
先考虑固定一棵树的情况。
设固定的树的边集为(E_1)，枚举的树的边集为(E_2)。
设(f(T)=y^{n-|T|})，那么(ans=sumlimits_{E_2}f(E_1cap E_2))。
考虑经典子集反演
因此我们有
设(g(S)=sumlimits_{Ssubseteq E_2}1)即包含(S)的树的个数，则有
推到这里差不多到底了，我们考虑一下(g(S))。
假设(S)把(n)个点分成了(m)个连通块，每个连通块有(a_i)个点。
有点经验的话应该能够看出这是个Ex-Cayley定理的形式。
即(g(S)=n^{m-2}prodlimits_{i=1}^ma_i)
我们把这个代进去，注意到(n=|S|+m)，同时为了方便我们记(k=frac{yn}{1-y})
这告诉我们每个大小为(a_i)连通块会产生(ka_i)的贡献，而一个边集的贡献为它划分的连通块的贡献之积，我们要求的是所有边集的贡献之和。
考虑dp计算这个贡献，一维看上去不太够就设两维，令(f_{u,i})表示只考虑(u)的子树，(u)所在连通块的大小为(i)的所有边集方案在忽略(i)所在连通块之后的的贡献之和。这个是经典的树上背包。
考虑优化，令(g_u=ksumlimits_iif_{u,i},F_u(x)=sumlimits_if_{u,i}x^i)，那么我们有
计算可得
这里的(F_v'(1)=g_v)，因此我们只关心(F_u(1))，而显然有(F_u(1)=prodlimits_v(g_v+F_v(1)))。
再令(h_u=F_u(1)=sumlimits_if_{u,i})，那么可以得到
这样我们就可以直接(O(n))计算出答案了。
顺带一提(ans=frac{(1-y)^n}{n^2}g_1)。
现在考虑两棵树都未确定的情况。
这个式子和上面的差不多，但是注意(S)的枚举范围是所有森林。
我们考虑用和上面类似的方法展开(g(S))，同时为了方便设(k=frac{yn^2}{1-y})，可以得到
因为(S)的枚举范围已经没有限制了，所以我们考虑转而枚举连通块。
因为一棵(a_i)个点的树有(a_i^{a_i-2})个，所以一个连通块的贡献是(ka_i^{a_i})。
而我们知道森林的方案数的EGF就是连通块的方案数的EGF的(exp)。
连通块的EGF为(F(x)=sumlimits_{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(nlog n))的。
但是因为这个序列的元素都是(0,1)，所以我们可以构造一个更加优秀的办法。
考虑构造一个可以容纳确定不是(0)的数并且单调不减的序列。
先把(0)扔进序列，用(a)表示这个序列的最后一个元素。
然后我们先令(x=1,y=2)。
从前往后枚举(3,cdots,n)。
先进行一次比较，令(v_xle v_y)。
然后如果有(v_age v_x+v_y)，那么说明有(v_x=0)，(x)可以不管了，我们令(x=i)。
否则有(v_yge 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;
}