首页
登录 | 注册

[bzoj5399]illustrious——打表找规律

题面:

[bzoj5399]illustrious——打表找规律

思路:

好一个打表题。。。
首先我们要发现各种性质:
f[n]直接对应了n在序列中出现的次数,又因为f[n]是单调递增的,然后我们就可以通过前1e6的数据二分来算出后面任意一个f[n]
至于怎么算g[g[n]]发现它的差分数组为nf[n],所以g[g[n]]=i=1nif[i],因为中间的f[i]不同的数只有1e6个,相同的f[i]可以通过等差数列求和来算,计算出和的前缀和,然后再二分一下算末尾的片段就好了。
然后就可以化简h[n]=h[g[f[n]1]]+g[g[n]]。理论上来说这样的话这题就可以过了,但是带了一个log也是美中不足,
观察到g[n]的意义为f[n]的前缀和,也就是f[m]=n的m的最大值,也就是一段相同的数的下标的最后一个,所以我们可以一整块一整块地从前往后推,同时计算g[g[n]]的时候也可以利用前面的状态了。
这题教给我太多了。。。。

/*======================================
 * Author : ylsoi
 * Problem : illustrious
 * Algorithm : print the table and math
 * Time : -2018.6.22
 * =====================================*/
#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;

using namespace std;

void File(){
    freopen("20180622T3.in","r",stdin);
    freopen("20180622T3.out","w",stdout);
}

const int maxn=1e6+10;
const ll mod=998244353;
int T,n;
ll f[maxn],g[maxn],gsum[maxn],gg[maxn];

ll F(ll x){return lower_bound(g+1,g+maxn-9,x)-g;}

ll GG(ll x){
    int pos=upper_bound(g+1,g+maxn-9,x)-g-1;
    return (gsum[pos]+(pos+1)*(g[pos]+1+x)*(x-g[pos])/2)%mod;
}

void init(){
    f[1]=1;
    REP(i,2,maxn-10)f[i]=f[i-f[f[i-1]]]+1;
    REP(i,1,maxn-10)g[i]=g[i-1]+f[i];
    REP(i,1,maxn-10)gsum[i]=(gsum[i-1]+i*(2*g[i-1]+f[i]+1)*f[i]/2)%mod;
    REP(i,1,1000)gg[i]=g[g[i]];
}

ll cal(ll x){
    ll ret=0;
    while(x){
        ret=(ret+GG(x))%mod;
        ll nex=g[F(x)-1];
        x=nex;
    }
    return ret;
}

int main(){
    File();
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%lld\n",cal(n));
    }
    return 0;
}


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号