2022杭电多校联赛第五场 题解

比赛传送门
作者： fn

• 签到题
• • 1010题 Bragging Dice / "吹牛骰子"
• 基本题
• • 1012题 Buy Figurines / 买手办
  • 1003题 Slipper / 拖鞋
• 进阶题
• • 1007题 Count Set / 数集合

题目大意
两个人玩明牌的 “吹牛骰子” 游戏，求先手和后手谁赢。
一个人投出的点数全部不同时，视为没有点数。

考察内容
博弈论

分析
双方都投出全部不同的点数时，全场都没有点数，先手必败，否则先手必胜。

#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
const int N=2e5+10;
ll n,a[N],b[N];

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
		}
		
		int num[10]={0};
		int same=0; // 记录有点数的人 
		
		for(int i=1;i<=n;i++){
			num[a[i]]++;
			if(num[a[i]]>=2){
				same++;
				break; 
			}
		}
		
		memset(num,0,sizeof num);
		for(int i=1;i<=n;i++){
			num[b[i]]++;
			if(num[b[i]]>=2){
				same++;
				break; 
			}
		}
		 
		if(same>=1)cout<<"Win!"< 
基本题 
1012题 Buy Figurines / 买手办 
题目大意
 若干个人排队买手办，每个人选择当前队伍人数最少的排队。
 求最后一个人买完的时间。
 
考察内容
 模拟，复杂度优化
 
分析
 解法不唯一。
 
直接按照题意，模拟每个人排队即可。
 有空队伍时，直接排进去。没有空队伍时，更新所有队伍当前的人数，然后排进人数最少的队伍。
 
#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
int read(int &n){
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 
ll read(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
const int N=2e5+10;
ll n,m;

struct node{
	ll start,last;
}a[N];

bool cmp(node x,node y){
	return x.start v[N]; 
int p[N]; 
 
ll t[N]; // 队伍最后的时间 
ll num[N]; // 队伍人数 

int main(){ 
	int t0; read(t0);
	while(t0--){
		read(n); read(m);
		for(int i=1;i<=n;i++){
			read(a[i].start);
			read(a[i].last);
		}
		sort(a+1,a+n+1,cmp); // 按照开始时间排序 
		
		memset(t,0,sizeof(t[0])*(n+1));
		memset(num,0,sizeof(num[0])*(m+1));
		memset(p,0,sizeof(p[0])*(m+1));
		for(int i=0;i<=m;i++)v[i].clear();
		
		for(int i=1;i<=n;i++){ // 枚举每一个人 
			int F=0;
			for(int j=1;j<=m;j++){ // 枚举每一个队伍 
				if(a[i].start>=t[j]){ // 可以直接排进去 
					F=1;
					t[j]=a[i].start+a[i].last;
					v[j].push_back(t[j]);
					num[j]++; 
					break;
				}	
			} 
			if(F){  
				continue;
			}
			
			// 找不到没有人的队伍时 
			for(int j=1;j<=m;j++){ // 枚举每一个队伍，更新num[j] 
				int len=v[j].size();
				for(int k=p[j];k
					if(v[j][k]<=a[i].start){
						p[j]++;
						num[j]--;
					}
					else{
						break;
					}
				} 
			}
			
			ll minnum=1e18; // 找最少队伍的人数 
			for(int j=1;j<=m;j++){
				minnum=min(minnum,num[j]);
			}
			for(int j=1;j<=m;j++){
				if(num[j]==minnum){ // 人数最少 
					t[j]+=a[i].last;
					v[j].push_back(t[j]);
					num[j]++; 
					break; 
				}	
			} 
		}
		
		ll ans=0;
		for(int i=1;i<=m;i++){
			ans=max(ans,t[i]);
		}
		
		cout< 
 
1003题 Slipper / 拖鞋 
题目大意
 给定一棵树和树上边权，每次可以走树上的边，也可以花费 
    
     
      
       
        p
       
      
      
       p
      
     
    p 的代价向上或向下跳 
    
     
      
       
        k
       
      
      
       k
      
     
    k 层。求点 
    
     
      
       
        s
       
      
      
       s
      
     
    s 到点 
    
     
      
       
        t
       
      
      
       t
      
     
    t 的最短路。
 
考察内容
 树形dp，dfs，最短路
 
分析
 赛时先写了一个dijkstra然后tle了，于是写了个树形dp。
 
每个点和每一层设一个状态，然后从终点开始dfs转移一下即可。
 
状态：
 
    
     
      
       
        f
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       f[i]
      
     
    f[i] 表示第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 个结点到终点的最短距离。
 
    
     
      
       
        f
       
       
        2
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       f2[i]
      
     
    f2[i] 表示第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 层中"最好"的点到终点的最短距离。
 
转移：
 对于每个结点，枚举所有出边和向上向下跳的情况，更新答案。
 
这种方法不添加额外的边，转移时每个结点至多枚举一次，复杂度 
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)
 
#pragma GCC optimize(3) // O3优化 
#include 
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
int read(int &n){
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 
ll read(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
const int N=1e6+5;
const int M=1e6+5; 

int head[N];
int ver[M],edge[M],nxt[M];
bool vis[N];

ll n,tot;
ll k,p,s,t;

ll u[N],v[N],w[N];
ll deep[N];
vector g[N];

ll f[N]; // f[i]表示第i个结点到终点的最短距离 
ll f2[N]; // f2[i]表示第i层中"最好"的点到终点的最短距离 
ll maxd=0;

void add(int x,int y,int z){
	ver[++tot]=y;
	edge[tot]=z; // 记录边权 
	nxt[tot]=head[x];
	head[x]=tot;
}

void dfs(int v,int fa,int d1){ // 标记结点深度 
	deep[v]=d1;
	for(auto a1:g[v]){
		if(a1==fa)continue;
		
		dfs(a1,v,d1+1);
	}
}

void dfs2(int v){
	if(vis[v])return;
	
	vis[v]=1;
	int x=v;
	for(int i=head[x];i>0;i=nxt[i]){ // 枚举出边 
		int y=ver[i];
		int z=edge[i]; // z保存边权 
		if(abs(deep[x]-deep[y])==k){ // 可以跳 
			z=min((ll)z,p); // 更新z 
		}
		
		if(f[y]>f[x]+z){ 
			f[y]=f[x]+z; // 转移	
		}			
		if(deep[y]+k<=maxd){
			f[y]=min(f[y],f2[deep[y]+k]+p); // 转移 
			f2[deep[y]]=min(f2[deep[y]],f[y]);
		}
		if(deep[y]-k>=1){
			f[y]=min(f[y],f2[deep[y]-k]+p); // 转移 
			f2[deep[y]]=min(f2[deep[y]],f[y]);
		}
		
		dfs2(y); 
	}
}

struct node{
	ll deep,id;
}n1[N];

bool cmp(node nx,node ny){
	return nx.deep // 初始化 
	memset(head,0,sizeof(head[0])*(n+1));
	memset(vis,0,sizeof(vis[0])*(n+1));
	memset(deep,0,sizeof(deep[0])*(n+1));
	
	memset(ver,0,sizeof ver);
	memset(edge,0,sizeof edge);
	memset(nxt,0,sizeof nxt);
	tot=0; 
	
	for(int i=0;i<=n;i++){
		g[i].clear();
	}
}

int main(){ // 树形dp 
	int t0; read(t0);
	while(t0--){
		read(n);
		for(int i=1;i<=n-1;i++){
			read(u[i]);
			read(v[i]);
			read(w[i]);
		}
		read(k); read(p); // 可以花费p跳过深度差距为k的结点 
		read(s); read(t);
		
		init(n); // 初始化 
		
		for(int i=1;i<=n-1;i++){			
			add(u[i],v[i],w[i]);
			add(v[i],u[i],w[i]);
			
			g[u[i]].push_back(v[i]);
			g[v[i]].push_back(u[i]);
		}
		dfs(1,0,1); // 从根结点开始，标记每个结点的深度 
		
		for(int i=0;i<=n;i++){
			f[i]=f2[i]=1e18;
		}
		f[t]=0; // 终点到自己距离0 
		
		maxd=deep[1]; // 保存最大深度 
		for(int i=2;i<=n;i++){
			maxd=max(maxd,deep[i]); 
		}
		f2[deep[t]]=0; 
	
		// 转移和终点直接连接的点 
		int x=t;
		for(int i=head[x];i>0;i=nxt[i]){
			int y=ver[i];
			int z=edge[i]; // z保存边权 
			
			if(f[y]>f[x]+z){
				f[y]=f[x]+z;
				f2[deep[y]]=min(f2[deep[y]],f[y]);
			}
		}
		
		for(int i=max(k,t+1);i<=maxd;i++){
			f2[i]=min(f2[i],f2[i-k]+p); // 更新f2[] 
		}
		for(int i=t-1;i>=1;i--){
			f2[i]=min(f2[i],f2[i+k]+p); // 更新f2[] 
		}
	
		dfs2(t); // 转移 
		
		cout< 
 
进阶题 
1007题 Count Set / 数集合 
题目大意
 从一个 
    
     
      
       
        1
       
      
      
       1
      
     
    1 到 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的排列中选 
    
     
      
       
        k
       
      
      
       k
      
     
    k 个数字，要求每个选出的数字和所有选中的下标都不同。
 
求选择的方案数。
 
考察内容
 生成函数，NTT，数学知识，Pólya定理
 
分析
 
 
#include
#define fr(i,l) for(S i=0;i
    U ans=1;
    while(b)
    {
        if(b&1)ans=(UL)ans*a%mod;
        a=(UL)a*a%mod;
        b>>=1;
    }
    return ans;
}
U mo(U x){return x>=mod?x-mod:x;}
U& mul(U&a,U b){return a=(UL)a*b%mod;}
void mov(U*a,const U*b,S len){memmove(a,b,len*sizeof(U));}

namespace Poly
{
    constexpr S ml=1<<19,mn=80;
    U mem[(ml+16)*mn],*stk[mn],top=mn,f[(ml+16)*2],wr[ml+16],wi[ml+16],ninv[ml+16];
    U*m(){return stk[--top];}void m(U*p){stk[top++]=p;}
    S up(S x){S l=1;while(l
        fr(i,mn)stk[i]=mem+i*(ml+16);
        U*fp;
        for(S len=1;fp=f+len,len<=ml;len<<=1)
            fr(i,len)fp[i]=(fp[i>>1]>>1)|(i&1?len>>1:0);
        for(S len=1;len
            U Wr=pow(g,(mod-1)/(len<<1));
            U Wi=pow(gi,(mod-1)/(len<<1));
            U tr=1,ti=1;
            fr(i,len)
            {
                wr[len+i]=tr;mul(tr,Wr);
                wi[len+i]=ti;mul(ti,Wi);
            }
        }
    }
#define lst(n,a,x) poly&n(a){x return*this;}
struct poly{
    U*mem,*a;
    S len;
    poly(S len):len(len){a=mem=m();cls(0,len);}
    poly():poly(1){}
    poly(U x):poly(){a[0]=x;}
    poly(U*l,S len):len(len){a=mem=m();mov(a,l,len);}
    poly(const poly&b):poly(b.a,b.len){}
    ~poly(){if(mem)m(mem);}
    lst(operator=,const poly&b,if(mem)rsz(b.len);mov(a,b.a,b.len);)
    U& operator[](S idx){return a[idx];}
    poly& cls(S l,S len){memset(a+l,0,len*4);return *this;}
    lst(rsz,S nlen,if(nlen>len)cls(len,nlen-len);len=nlen;)
    template
    lst(NTT,S len=-1,static UL a[ml+16];
        if(~len)rsz(len);else len=this->len;
        fr(i,len)a[i]=this->a[f[len+i]];
        for(S i=1;i
            U*w=wp+i;
            for(S j=0;j
                UL x=a[j+k];
                UL y=a[i+j+k]*w[k]%mod;
                a[j+k]=x+y;
                a[i+j+k]=x-y+mod;
            }
        }
        fr(i,len)this->a[i]=a[i]%mod;
    )
    lst(NTTi,S len=-1,NTT(len);*this*=pow(this->len,mod-2);)
    poly operator+(const poly&b){return poly(*this)+=b;}
    poly operator-(const poly&b){return poly(*this)-=b;}
    poly operator*(const poly&b){return poly(*this)*=b;}
    poly operator*(U x){return poly(*this)*=x;}
    lst(operator+=,const poly&b,rsz(max(len,b.len));fr(i,b.len)a[i]=mo(a[i]+b.a[i]);)
    lst(operator-=,const poly&b,rsz(max(len,b.len));fr(i,b.len)a[i]=mo(a[i]-b.a[i]+mod);)
    lst(operator*=,poly b,S l=up(len+b.len-1);NTT(l).vmul(b.NTT(l)).NTTi();)
    lst(operator*=,U x,fr(i,len)mul(a[i],x);)
    lst(vmul,const poly&b,fr(i,len)mul(a[i],b.a[i]);)
    lst(print,,fr(i,len)printf("%u ",a[i]);puts("");)
};
};
using Poly::poly;

U fact[500001];
U ifact[500001];

U C(int n,int m){
    if(m<0||m>n)return 0;
    return (UL)fact[n]*ifact[m]%mod*ifact[n-m]%mod;
}
int p[500000];
int vis[500000];
int sz[500000],num;

poly calc(int l,int r){
    if(l==r){
        poly t(sz[l]/2+1);
        t[0]=1;
        for(S i=1;i
        int mid=l+r>>1;
        poly a=calc(l,mid);
        poly b=calc(mid+1,r);
        int len=a.len+b.len-1;
        return (a*=b).rsz(len);
    }
}


void sol(){
    int n,k;
    scanf("%d%d",&n,&k);
    fr(i,n)scanf("%d",p+i),p[i]--;
    memset(vis,0,4*n);
    num=0;
    fr(i,n){
        if(!vis[i]){
            vis[i]=1;
            sz[num]=1;
            int t=p[i];
            while(!vis[t]){
                vis[t]=1;
                sz[num]++;
                t=p[t];
            }
            if(sz[num]>1)num++;
        }
    }
    poly a=calc(0,num-1);
    
    if(k>=a.len){
    	printf("0n");
    }
    else{
    	printf("%un",a[k]);
    }
}

int main(){
    Poly::init();
    
	// 预处理阶乘 
    fact[0]=1;
    for(S i=1;i<=500000;i++)
        fact[i]=(UL)fact[i-1]*i%mod; 
        
    ifact[500000]=pow(fact[500000],mod-2);
    for(S i=500000;i;i--)
        ifact[i-1]=(UL)ifact[i]*i%mod;
        
    int T;
    scanf("%d",&T);
    while(T--)sol();
}