csps模拟67神炎皇，降雷皇，幻魔皇题解

题面：https://www.cnblogs.com/Juve/articles/11648975.html

神炎皇：

打表找规律？和$phi$有关？

答案就是$sumlimits_{i=2}^{n}phi(i)*frac{n}{i*i}$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
int n,ans=0;
int prime[2000006],tot=0,phi[10000006];
bool vis[10000007];
void get_phi(int N){
    vis[1]=phi[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]) prime[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*prime[j]<=N;j++){
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}
signed main(){
    scanf("%lld",&n);
    get_phi(sqrt(n)+1);
    for(int i=2;i<=sqrt(n);++i)
        ans+=phi[i]*(n/(i*i));
    printf("%lld
",ans);
    return 0;
}

降雷皇

基础不牢，地动山摇。。。赶紧补一发LIS

给定序列$a_i$，设f[i]表示以a[i]结尾的最长上升序列长度

则$f[i]=max(f[j]+1)(j<i&&a[j]<a[i])$

设g[i]表示以i为结尾的最长上升序列的个数

则有$g[i]=sumlimits_{j=1}^{i-1}[a[j]<a[i]&&f[j]=f[i]-1]*g[j]$

这样就有了$O(n^2)$转移

然后用树状数组加速转移

树状数组下标为权值，顺序扫保证了j<i，树状数组查询a[i]-1保证了a[j]<a[i]，然后树状数组即可

当然也可以线段树，原理是一样的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
const int mod=123456789;
int n,typ,a[MAXN],mx=0;
pair<int,int>c[MAXN*10],f[MAXN],ans;//changdu,geshu
int lowbit(int x){
	return x&(-x);
}
int update(int pos,pair<int,int> val){
	for(int i=pos;i<=mx;i+=lowbit(i)){
		if(c[i].first<val.first) c[i]=val;
		else if(c[i].first==val.first) (c[i].second+=val.second)%=mod;
	}
}
pair<int,int> query(int pos){
	pair<int,int>res;
	res.first=0,res.second=1;
	for(int i=pos;i>0;i-=lowbit(i)){
		if(res.first<c[i].first) res=c[i];
		else if(res.first==c[i].first) (res.second+=c[i].second)%=mod;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&typ);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),mx=max(mx,a[i]);
	for(int i=1;i<=n;++i){
		f[i]=query(a[i]-1);
		++f[i].first;
		update(a[i],f[i]);
		if(ans.first<f[i].first) ans=f[i];
		else if(ans.first==f[i].first) (ans.second+=f[i].second)%=mod;
	}
	if(typ==0) printf("%d
",ans.first);
	else printf("%d
%d
",ans.first,ans.second);
	return 0;
}

幻魔皇：

产生贡献的只有白点，我们按两个白点lca的颜色分类

如果两个白点lca是白点，那么这个白点一定是两个白点中的一个

枚举两个白点的距离，不难发现只有深度在[1,n-i]的白点在它的子树中有距离为i的白点

设sum[i]表示前i层白点个数，w[i]表示第i层白点个数，因为每个白点的子树结构都相同，所以每个白点所在子树中第i层的白点个数都相等

所以贡献就是sum[n-i]*w[i]，

如果两个白点的lca是黑点，枚举两个白点到黑点的距离i，j，只有深度为[1,n-max(i,j)]的黑点有贡献

设f[i]表示前i层的黑点个数，那么答案就是f[n-max(i,j)]*w[i]*w[j+1]，其中i，j是有顺序的，i表示在黑点的白儿子的子树中的点，j表示在黑点的黑儿子的子树中的点

sum[],w[],f[]用fib递推

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN=5005;
const int mod=123456789;
int n,w[MAXN],sum[MAXN],f[MAXN],ans[MAXN<<1];
signed main(){
    scanf("%lld",&n);
    w[1]=w[3]=w[4]=1;w[2]=0;
    for(int i=5;i<=n;++i) w[i]=(w[i-1]+w[i-2])%mod;
    for(int i=1;i<=n;++i) sum[i]=(sum[i-1]+w[i])%mod;
    f[1]=0,f[2]=f[3]=1;
    for(int i=4;i<=n;++i) f[i]=(f[i-1]+f[i-2])%mod;
    for(int i=1;i<=n;++i) f[i]=(f[i-1]+f[i])%mod;
    for(int i=1;i<n;++i){
        (ans[i]+=(sum[n-i]*w[i+1])%mod)%=mod;
        for(int j=1;j<n;++j)
            (ans[i+j]+=f[n-max(i,j)]*w[i]%mod*w[j+1]%mod)%=mod;
    }
    for(int i=1;i<=2*n;++i) printf("%lld ",ans[i]);
    puts("");
    return 0;
}