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;
}
