20181018多校联测


T1题意


给三个排列,求三维偏序 范围1e6


Solution


纯CDQ分治是肯定过不了的。
可以想一想这题与一般的三维偏序有什么区别:
是的,三个数列都是排列,一个数只会在一个数列出现一次。
那么我们可以考虑计算以下三个玩意:



对于每一对需要计算答案的点对(i,j),它一定在X,Y,Z中都被算过一遍。
对于不需要算答案的点对,它一定的X,Y,Z中的一个里面被算过一次。
所以答案就是:


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 2000100
#define reg register
#define ll long long
#define inf 2147483647
#define ui unsigned int
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
struct node{int x,y,z;}a[maxn];
ui SA,SB,SC,tr[maxn];ll n,ans;
inline ui rd(){
    SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;
    ui t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;
}
inline void gen(){
    for (int i=1; i<=n; ++i) a[i].x=i;
    for (int i=1; i<=n; ++i) swap(a[i].x,a[1+rd()%n].x);
    for (int i=1; i<=n; ++i) a[i].y=i;
    for (int i=1; i<=n; ++i) swap(a[i].y,a[1+rd()%n].y);
    for (int i=1; i<=n; ++i) a[i].z=i;
    for (int i=1; i<=n; ++i) swap(a[i].z,a[1+rd()%n].z);
}
inline void ins(int x){for (; x<=n; x+=lowbit(x)) ++tr[x];}
inline int query(int x){int ret=0;for (; x; x-=lowbit(x)) ret+=tr[x];return ret;}
inline int cmp1(node a,node b){return a.x<b.x;}
inline int cmp2(node a,node b){return a.y<b.y;}
inline ll C(ll n,ll m){
    if(m==0||n==m||n==1) return 1;ll g=min(m,n-m),f=1;
    for(ll i=1; i<=g; i++) f=f*(n-i+1)/i;return f;
}
inline void get(){
    sort(a+1,a+n+1,cmp1);
    for (int i=1; i<=n; ++i)
        ans+=query(a[i].y),ins(a[i].y);
    memset(tr,0,sizeof tr);
    for (int i=1; i<=n; ++i)
        ans+=query(a[i].z),ins(a[i].z);
    memset(tr,0,sizeof(tr));
    sort(a+1,a+n+1,cmp2);
    for (int i=1; i<=n; ++i)
        ans+=query(a[i].z),ins(a[i].z);
    ans-=C(n,2),ans>>=1;wt(ans,'\n');
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(n),read(SA),read(SB),read(SC);
    gen(),get();return 0;
}

T2题意


挖坑待填。


Solution


挖坑待填。


Code

挖坑待填。
T3题意


给一棵树,每次询问u,v,k,opt,求k条简单路径的交仅为u到v的简单路径的方案数


Solution


树DP
判断是否是子树可以通过dfs序,就免去了LCA这一步骤。


Code
    已更新!能A!qwq   

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 100100
#define reg register
#define ll long long
#define mod 998244353
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    ll t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
inline ll qpow(ll a,ll b){
    ll res=1;
    for (; b; a=(a*a)%mod,b>>=1) if (b&1) (res*=a)%=mod;
    return res;
}
ll n,q,tot,fa[maxn],f[maxn][510],fac[510],fact[510];
ll nxt[maxn<<1],fir[maxn],to[maxn<<1],cnt,dfn[maxn],sz[maxn],g[510];
inline void ins(ll x,ll y){
    nxt[++cnt]=fir[x],fir[x]=cnt,to[cnt]=y;
    nxt[++cnt]=fir[y],fir[y]=cnt,to[cnt]=x;
}
inline void dfs1(ll now){ll line=0;
    dfn[now]=++tot,sz[now]=1,f[now][0]=1;
    for (ll i=fir[now]; i; i=nxt[i])
        if (dfn[to[i]]==0) {fa[to[i]]=now; dfs1(to[i]);sz[now]+=sz[to[i]];
            for (ll j=line; ~j; --j)f[now][j+1]=(f[now][j+1]+f[now][j]*sz[to[i]]%mod)%mod;line++;
        }
}
inline void solve(ll u,ll s,ll k){
    memcpy(g,f[u],sizeof(g));ll v=0;
    for (ll i=fir[u]; i; i=nxt[i])
        if (to[i]!=fa[u]&&dfn[to[i]]<=dfn[s]&&dfn[s]<=dfn[to[i]]+sz[to[i]]-1){v=to[i];break;}
    for (ll i=1; i<=k; ++i)g[i]=((g[i]-g[i-1]*sz[v])%mod+mod)%mod;
    for (ll i=k; i; --i)g[i]=(g[i]+g[i-1]*(n-sz[u]))%mod;
}
int main(){
    read(n),read(q);
    for (ll x,y,i=1; i<n; ++i)read(x),read(y),ins(x,y);dfs1(1);
    fac[0]=fact[0]=1;for (ll i=1; i<=500; ++i) fac[i]=fac[i-1]*i%mod;
    fact[500]=qpow(fac[500],mod-2);for (ll i=499; i; --i) fact[i]=fact[i+1]*(i+1)%mod;
    for (ll u,v,k,opt,i=1; i<=q; ++i){
        read(u),read(v),read(k),read(opt);
        if (dfn[u]>dfn[v]) swap(u,v);
        if (dfn[u]+sz[u]<=dfn[v]){
            if (opt==1) wt((f[u][k]+f[u][k-1])*(f[v][k]+f[v][k-1])%mod*fac[k]%mod*fac[k]%mod,'\n');
            else{
                ll tmp=0,ans=0;
                for (ll i=0; i<=k; i++) (tmp+=f[u][i]*fac[k]%mod*fact[k-i]%mod)%=mod;
                for (ll i=0; i<=k; i++) (ans+=f[v][i]*fac[k]%mod*fact[k-i]%mod)%=mod;
                wt(ans*tmp%mod,'\n');
            }
        }else{
            if (opt==1){
                ll ans=(f[v][k]+f[v][k-1])*fac[k]%mod;solve(u,v,k);
                ans=ans*(g[k]+g[k-1])%mod*fac[k]%mod;wt(ans,'\n');
            }else{
                ll ans=0,tmp=0;
                for (ll i=0; i<=k; i++) tmp=(tmp+f[v][i]*fac[k]%mod*fact[k-i]%mod)%mod;solve(u,v,k);
                for (ll i=0; i<=k; i++) ans=(ans+g[i]*fac[k]%mod*fact[k-i]%mod)%mod;wt(ans*tmp%mod,'\n');
            }
        }
    }
    return 0;
}

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s