A. 神炎皇

尝试枚举$a$,$b$的$gcd$，设为$d$。

那么有$$ans=\sum \limits_{d=1}^{n} \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{n} [gcd(i,j)==d][i+j<=n][i+j|i=j]$$

 $$ans=\sum \limits_{d=1}^{n} \sum \limits_{i=1}^{n/d} \sum \limits_{j=1}^{n/d}[gcd(i,j)==1][i+j<=n/d][id+jd|ijd^2]$$

 由$i+j \nmid ij$

 $$ans=\sum \limits_{d=1}^{n} \sum \limits_{i=1}^{n/d} \sum \limits_{j=1}^{n/d}[gcd(i,j)==1][i+j<=n/d][i+j|d]$$

发现后面多与$i+j$有关，故枚举$i+j$，设为$k$。

$$ans=\sum \limits_{d=1}^{n} \sum \limits_{k=1}^{n/d} \varphi(k)[k|d]$$

注意我们在前面已经除过一次$d$了，故$k*d=a+b<=n$      $k|d \rightarrow d>=k$

即$k*k*d<=n$，符合条件的d共有$\lfloor \frac{n}{k*k} \rfloor$个

$$ans=\sum \limits_{k=1}^{\sqrt n} \varphi(k) \lfloor \frac{n}{k*k} \rfloor$$

 

 

 

 

B. 降雷皇

问题是最长上升子序列，并输出方案数。

显然用一个简单数据结构（如树状数组）维护一下每个权值的最优解和方案数就完了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<tuple>
 4 using namespace std;
 5 const int N=1e5+7;
 6 const int mod=123456789;
 7 int n,id,mx;
 8 int s[N],b[N],sz[N];
 9 inline int lowbit(int x){
10     return x&-x;
11 }
12 inline void modify(int x,int val,int js){
13     for(;x<=mx;x+=lowbit(x))
14         if(val==b[x]) (sz[x]+=js)%=mod;
15         else if(val>b[x]) sz[x]=js,b[x]=val;
16 }
17 inline pair<int,int> query(int x,pair<int,int> ans=make_pair(0,0)){
18     for(;x;x^=lowbit(x))
19         if(b[x]>ans.first) ans.first=b[x],ans.second=sz[x];
20         else if(b[x]==ans.first) (ans.second+=sz[x])%=mod;
21     return ans;
22 }
23 int main(){
24     scanf("%d%d",&n,&id);
25     for(int i=1;i<=n;++i) scanf("%d",&s[i]),++s[i],++s[i],mx=max(mx,s[i]);
26     modify(1,0,1);
27     int val,cnt;
28     for(int i=1;i<=n;++i){
29         tie(val,cnt)=query(s[i]-1);
30         modify(s[i],val+1,cnt);
31     }
32     tie(val,cnt)=query(mx);
33     printf("%d\n",val);
34     if(id) printf("%d\n",cnt);
35     return 0;
36 }
tuple写法

 

 

 

C. 幻魔皇

首先是一些显然的结论。

对于一个节点，如果深度和颜色相同，那么贡献的答案是相同的。

分别考虑不同深度，白色点为$lca$的贡献和黑色点为$lca$的贡献。

前者的贡献是显然的，因为白色点只有一个儿子。

后者的贡献类似一个卷积的形式，暴力做n次卷积，复杂度是$O(n^3)$的。

如果用$fft$，可以优化为$O(n^2logn)$，然而任意模数似乎并不简单。

然后就死掉了。

正解是优化了卷积的过程。

可以发现，相邻两次卷积的结果是类似的：

因为卷积的内容是类似的。

只要将相邻两次卷积的增加量处理出来就可以了。