[2015 Regional Online]長春C Aggregated Counting[打表找法则+分块打表]

じòぴé(′▽`)じòぴéじòぴéじòぴéじòぴéじòぴéじòぴéじòぴéじòぴぴéじòぴぴéじòぴぴéじòぴぴぴéじòぴぴé
ゆっくり話しましょう.2つの記号を定義する:d[i]は元のシーケンスのi番目のlast(n)は(タイトルに定義されている)を表し、元のシーケンスの中で最後にnが現れる位置の下付き(明らかにタイトルが要求され、last(last(n))を求める)そして、下書き紙に勝手に書き、明らかにlast(n)=Σi=1 nd[i]
もともと計画していたのは、nが大きいときのlast(n)をすばやく計算できるように書くことで、私は時計を打ってみることにしました.

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

int d[500005];

int main(){
    freopen("03table.txt","w",stdout);
    d[1]=1;
    d[2]=2;
    d[3]=2;
    int lastp=3;
    for(int i=3;lastp<=500000;i++){
        for(int j=0;j<d[i]&&lastp<=500000;j++){
            d[++lastp]=i;
        }
    }
    ll sum=0;
    for(int i=1;i<=500000;i++){
        sum+=d[i];
        sum%=1000000007;
        printf("%d %d %I64d
",i,d[i],sum);
    }
    return 0;
}

そして私もその時何を考えていたのか思い出せませんでした(d[i]を2、3、4に区切って保存しているようです.....の値の位置で生み出せる数の最後の位置?どうせ冷静で論理的でない行為ですから…)

sum+=d[i];

次のように書き換えます.

sum+=d[i]*i;

そして表を開けてみると、last(last(n))を求めたようです.トイレに行って落ち着いて、帰ってきて計算して、本当のようです!
そこで私たちは今新しい目標を持っていて、last(last(n))を表を打つ方法を通じて、計算を完成します.まず1つの問題を解決しなければならない:d[i],iの範囲は10億で、このようなint配列はメモリを爆発させて、開けられないでしょう......幸いにも私たちは:last(n)=Σi=1 nd[i]を持っています.そこで,d[i]の接頭辞和を用いて,nごとにd[n]を二分検索で位置決めし,その後上を探しても毎回二分をやり直す必要がなく,直接推定すればよい.そして、d[n]はどのくらい算出しておけばいいのでしょうか.時計を続けてlast(n)≧109のn値を見つけて、喜んで発見して、n=500000の時で十分です.もちろん、n≦109の場合、すべての打表は現実的ではなく、古典的な打表スキーム:ブロック打表--d個ごとに、答えを出力し、その後、所望の複雑度d/2を検索するたびに.喜んで次の表のプログラムを書きました.

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAXN=500000;

int d[MAXN+5];
int sum[MAXN+5];

int main(){
    freopen("03tablecode.txt","w",stdout);
    printf("0,");
    d[1]=1;
    d[2]=2;
    d[3]=2;
    int lastp=3;
    for(int i=3;lastp<=MAXN;i++){
        for(int j=0;j<d[i]&&lastp<=MAXN;j++){
            d[++lastp]=i;
        }
    }
    for(int i=1;i<=MAXN;i++)
        sum[i]+=sum[i-1]+d[i];
    int p=1;
    ll presum=0;
    for(int i=1;i<=1000000000;i++){
        while(sum[p]<i)p++;
        presum+=(ll)p*(ll)i;
        presum%=1000000007;
        if(i%200000==0)printf("%I64d,",presum);
    }
    return 0;
}

注意して、ここは10万項目ごとに1つの値を打つのが多すぎて、100 KBの表は提出できません;20万件ごとに1つの値を打って、表が半分小さくて、順調に提出することができます.そして表を上の打表プログラムに似たコードに貼り付けて、複雑さを期待して運が良かったかも?提出するとTLEが・・・
そしてよく観察すると、実際にはd[i]の接頭辞とsum[i]を十分に利用していないことが分かった.nとそれに対応するd[n]は既知であり、sum[d[n]−1]≦i≦sum[d[n]]を満たすiについては、これらのiが最終結果に乗じたd[i]と同じであることが明らかになった.派手な50 KBのコードで、15 msと4 MBのメモリで解決しました・・・
コードは次のとおりです.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAXDN=500000;

int d[MAXDN+5];
int table[5005]={};//    ，    
void init(){
    d[1]=1;
    d[2]=2;
    d[3]=2;
    int lastp=3;
    for(int i=3;lastp<=MAXDN;i++){
        for(int j=0;j<d[i]&&lastp<=MAXDN;j++){
            d[++lastp]=i;
        }
    }
    for(int i=2;i<=MAXDN;i++)
        d[i]+=d[i-1];
}

int main(){
    init();
    int T,n;
    for(scanf("%d",&T);T--;){
        scanf("%d",&n);
        int goal=n/200000*200000;
        int p=lower_bound(d+1,d+MAXDN+1,goal)-d;

        int presum=table[n/200000];
        for(int i=goal+1;i<=n;i++){
            while(d[p]<i)p++;

            //      
            int obs=(min(d[p],n)-i+1);
            int fe=i+min(d[p],n);
            ll tmp=(ll)fe*obs/2;
            tmp%=1000000007;
            //    d[i]   ，     
            presum+=(1LL*p*tmp)%1000000007;
            if(presum>1000000007)presum-=1000000007;
            i=d[p]; p++;
        }
        printf("%d
",presum);
    }
    return 0;
}