题解 P6826 【「EZEC-4」月下轻花舞】

· · 题解

题解 P6826 【「EZEC-4」月下轻花舞】

@我谔谔 大佬的分k大小和前缀和优化思路对我很有启发。但我推式子的过程和大佬有所不同。

推式子思路

注意到 \left \lceil \log_{i}j \right \rceil \in Z，所以将 \left \lceil \log_{i}j \right \rceil 以求和号的形式写出来，然后通过交换求和号改变求和顺序，达到去掉大循环的目的。

\sum_{i=l}^{r}(i-1)\sum_{j=1}^{n}\left \lceil \log_{i}j \right\rceil = \sum_{i=l}^{r}(i-1)\sum_{j=1}^{n}\sum_{k\geqslant 1}^{}\sum_{i^{k-1}<j}^{}1

式子的核心在于 i^{k-1}<j 。最内层循环为 i,k 时仍需要遍历计算。当最内层循环 j 时，有

\sum_{j=1}^{n}\sum_{i^{k-1}<j}^{}1=max(n-i^{k-1},0)

于是要求的式子转化为

\sum_{i=l}^{r}(i-1)\sum_{k\geqslant 1}max(n-i^{k-1},0)

让 (i-1)max(n-i^{k-1},0) 有意义时，i^{k-1}\leqslant n，即 k\leqslant log_{i}n+1 。记t=log_{i}n+1，有

\sum_{i=l}^{r}(i-1)\sum_{k\geqslant 1}max(n-i^{k-1},0)=\sum_{i=l}^{r}\sum_{k\leqslant t}(i-1)(n-i^{k-1}) =\sum_{i=l}^{r}\sum_{k\leqslant t}(i-1)n -\sum_{i=l}^{r}\sum_{k\leqslant t}(i^{k}- i^{k-1})=\sum_{i=l}^{r}(i-1)nt-\sum_{i=l}^{r}(i^{t}-1) =\sum_{i=l}^{r}(i-1)nt-\sum_{i=l}^{r}i^{t}+(r-l+1)

枚举 k 的值，k=1,2,3,4时手算求和公式，k\geqslant5时用前缀和数组。处理的区间为(n,r],(\sqrt[]{n},n],(\sqrt[3]{n},\sqrt[]{n}],(\sqrt[4]{n},\sqrt[3]{n}]... 最终处理到 l 。

下面附上代码。需要注意诸多细节，在文中说明。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN (1<<16)+5//开到2*10^18的四次根 
#define MAXK 62
#define MAXT 100005//离线，其实可以不用 
#define MOD 998244353
#define re register long long
ll s[MAXN][MAXK];//前缀和数组 
ll l1[MAXT],r1[MAXT],n1[MAXT];//离线取最大的n，其实没必要 
ll base[MAXN];//辅助预处理，记录下标的幂次 
ll fj[MAXK];//记录n^(1/下标) 
ll t,l,r,n,k,maxn;
ll gsc(ll a,ll b){//取模乘法 
    a%=MOD;b%=MOD;
    return (a*b)%MOD;
}
ll dev(ll a,ll b){//取模除法 
    while(a%b!=0)a+=MOD;
    return a/b;
}
void solve(ll l,ll r,ll n){ 
    ll ans=r-l+1;
    memset(fj,0,sizeof(fj));
    for(re i=1;i<=n;i++){
        fj[i]=pow(n,1.00/i);
        if(fj[i]==1)break;//太小的用不到 
    }
    ll inf=l;
    if(r>fj[4]){//手算公式的需要 
        if(r>fj[3]){
            if(r>fj[2]){
                if(r>n){
                    inf=n+1;
                    inf=max(l,inf);
                    if(l<=r){//处理下界 
                        ll tmp=dev(gsc(r+inf,r-inf+1),2);
                        ans=(ans+dev(gsc(n,gsc(r+inf-2,r-inf+1)),2)-tmp)%MOD;
                        while(ans<0)ans+=MOD;
                        r=n;//改变上标，大于n的已处理完毕 
                    }
                }
                inf=fj[2]+1;
                inf=max(l,inf);
                if(l<=r){
                    ll tmp=(dev(gsc(gsc(r,r+1),2*r+1),6)-dev(gsc(gsc(inf-1,inf),2*inf-1),6))%MOD;
                    ans=(ans+gsc(n,gsc(r+inf-2,r-inf+1))-tmp)%MOD;
                    while(ans<0)ans+=MOD;
                    r=fj[2];
                }
            }
            inf=fj[3]+1;
            inf=max(l,inf);
            if(l<=r){
                ll tmp=(dev(gsc(r,gsc(r,gsc(r+1,r+1))),4)-dev(gsc(inf,gsc(inf,gsc(inf-1,inf-1))),4))%MOD;
                ans=(ans+(dev(gsc(n,gsc(r+inf-2,r-inf+1)),2)*3)%MOD-tmp)%MOD;
                while(ans<0)ans+=MOD;
                r=fj[3];
            }
        }
        inf=fj[4]+1;
        inf=max(l,inf);
        if(l<=r){
            ll tmp=dev(gsc(dev(gsc(gsc(r,r+1),2*r+1),6),gsc(gsc(r,r),3)+gsc(3,r)-1),5)-dev(gsc(dev(gsc(gsc(inf-1,inf),2*inf-1),6),gsc(gsc(inf-1,inf-1),3)+gsc(3,inf-1)-1),5);
            ans=(ans+(dev(gsc(n,gsc(r+inf-2,r-inf+1)),2)*4)%MOD-tmp)%MOD;
            while(ans<0)ans+=MOD;
            r=fj[4];
        }
    }
    for(re t=5;t<=log(n)/log(2)+1;t++){
        inf=fj[t]+1;
        inf=max(l,inf);
        if(l>r)break;//处理下界，当当前处理区间下界>=l的时候就退出 
        if(r>fj[t]){
            ll tmp=(s[r][t]-s[inf-1][t]+MOD)%MOD;
            ans=ans+gsc(dev(gsc(n,gsc(r+inf-2,r-inf+1)),2),t)-tmp;
            while(ans<0)ans+=MOD;
            r=fj[t];
        }
    }
    while(ans<0)ans+=MOD;
    printf("%lld\n",ans%MOD);
}
int main(){
    scanf("%lld",&t);
    for(re i=1;i<=t;i++)scanf("%lld%lld%lld",&l1[i],&r1[i],&n1[i]),maxn=max(maxn,n1[i]);
    for(re i=1;i<=(1<<16);i++){
        base[i]=(i*i)%MOD;
        base[i]=(base[i]*base[i])%MOD;
        base[i]*=i;base[i]%=MOD;
    }
    for(re j=5;j<=log(maxn)/log(2)+1;j++){
        for(re i=1;i<=(1<<16);i++){
            s[i][j]=(s[i-1][j]+base[i])%MOD;
            base[i]=(base[i]*i)%MOD;
        }
    }//预处理 
    for(re q=1;q<=t;q++)solve(l1[q],r1[q],n1[q]);
}