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
给一棵树,每次询问u,v,k,opt,求k条简单路径的交仅为u到v的简单路径的方案数
Solution
树DP
判断是否是子树可以通过dfs序,就免去了LCA这一步骤。
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 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; }