HNOI2018省队集训 Day3

circular

简单题

直接破环为链+倍增即可。

admirable

最开始想的是点分治，因为往上的路径有点不好搞，觉得题解肯定还有复杂度更小的做法就去看题解

然后发现可以处理出以某个儿子为根的f值，就可以直接dfs了，复杂度从\(nlog^3\)变成\(n(log^2+\sqrt n)\)。具体方法就是模拟一下多项式除以二项式再乘上一个二项式，同一size的儿子一起处理。

然后开始写，写了一半要预处理NTT单位根

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,pos=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return pos?x:-x;
} 
#define ll long long
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
typedef vector<int> poly
int n;
const int N = 200001;
const int mod = 998244353;
struct node{
	int v,nex;
}edge[N*2];
int head[N],top=0,sz[N],fa[N],deg[N];
poly sv[N],pw[N];
void add(int u,int v){
	edge[++top].v=v;
	edge[++top].nex=head[u];
	head[u]=top;
}
void dft()
poly operator *(const poly &a,const poly &b){
	poly A=a,B=b;
	int len=1;
	while(len<A.size()+B.size()) len*=2;
	init(len);
	poly C(len,0);
	dft(A,len,1);dft(B,len,1);
	FOR(i,0,len-1) C[i]=1ll*A[i]*B[i]%mod;
	
}
poly work(int l,int r){
	if(l==r) return {1,sv[now][l]};
	int mid=(l+r)>>1;
	return work(l,mid)*work(r,mid);
}
void dfs1(int now,int pre){
	sz[now]=1;fa[now]=pre;
	for(int i=head[now];i;i=edge[i].nex){
		int v=edge[i].v;
		if(v==pre) continue;
		dfs1(v,now);
		sz[now]+=sz[v]; 
		deg[now]++;
		sv[now].push_back(sz[v]);
	}
	pw[now]=work(0,deg[now]-1);
}
int main(){
	n=read();
	FOR(i,1,n-1){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	dfs1(1,0);
	dfs2(1);
}

然后一看题目，模数1e9+9，噔 噔 咚（心肺停止）

写nm

考场上要么写n^2+链要么留到最后再淦吧

illustrious

打表神题

首先打表得出 \(f(i)\) 是i的出现次数，那么我们算1e6个数就可以得出3e9的f

然后 \(f(n)\) 的前缀和 \(g(n)\) 表示 \(f(m) = n\) 的最大的 m

那么 \(f(f(n))\) 表示序列中下标为 \(n\) 处的数（\(f(n)\) ) 的出现次数

\(g(f(n))\) 表示序列中最大的是 \(f(n)\) 的位置。

那么 \(g(f(n)) − f(f(n))\) 则表示序列中第一个等于 \(f(n)\) 的位置的前一个位置，即最后一个为 \(f(n) − 1\) 的位置，即 \(g(f(n) − 1)\) ！

然后考虑算 \(g(g(n))\)

\[\begin{aligned} g(g(n))-g(g(n-1)) &=\sum_{i=g(n-1)+1}^{g(n)} f(i) \\ &=\sum_{i=g(n-1)+1}^{g(n)} n \\ &=n \cdot f(n) \end{aligned} \]

所以 \(g(g(n))=\sum_{i=1}^{n} i \cdot f(i)\)
然后分段算一下