CF1905E——函数与统计

spdarkle · 2023-12-18 13:43:55 · 题解

精妙的题目，在此记录一个极有意思的想法——OI与函数的结合。

对于一个点作为 lca 的情况，有 (2^{siz_{lc}-1})(2^{siz_{rc}-1}) 种可能。

首先传统的做法是按层统计答案，这里就不说了。不过我们可以利用一个推论：

对于任意一棵节点大小为 n 的线段树，所有节点的 siz 至多有 \log^2n 个不同的值。

证明是容易的，显然每层最多有 \log n 个节点 siz 不一样。

而我们注意到，堆式线段树的编号规则一定，那么编号为 x，区间长度为 k 的线段树子树也有相同的编号规则，我们假设这颗子树内的答案是 f(x,k)。

这样，我们就只需要计算 O(\log^2 n) 个不同的函数值。

而注意到，f(x,k) 可以表示为一个一次函数形式：f(x,k)=k_0x+b_0。

为什么呢？证明如下（证明本质上就是做法）：

注意到 f(x,k) 有两颗子树，编号为 2x,2x+1，那么就有：

容易发现，这个函数式没有遗漏任何信息，且最终状态 f(x,1)_k=1,f(x,1)_b=0。

由此，解决这个问题是容易的。

#include<bits/stdc++.h>
using namespace std;
#define N 105050
#define int long long
const int p=998244353;
struct node{
    int k,b;
    //ans=kx+b
};
int power(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
map<int,node>h;
node solve(int k){
    if(k==1)return (node){1,0};
    if(h.find(k)!=h.end())return h[k];
    int l=(k+1)>>1;
    node lc=solve(l),rc=solve(k-l);
    node res;res.k=0,res.b=0;
    res.k+=(power(2,l)-1)*(power(2,k-l)-1)%p;
    res.b+=lc.b+rc.b;
    res.k+=2ll*(lc.k+rc.k);
    res.b+=rc.k;res.k%=p,res.b%=p;
    h[k]=res;
    return res; 
} 
signed main(){
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        node res=solve(n);
        cout<<((res.k+res.b)%p+p)%p<<"\n";
    }
}

数学与信息学在函数与统计上交汇交融，绽放绚丽的光华，这是多么美的一件事啊。