Aggregated Counting

转： https://blog.csdn.net/cq_phqg/article/details/48417111

题解：

可以令n=1+2+2+3+3+......+ i 这个序列的长度为p

那么a[n]=1*1+2*2+3*2+...... + p*i

那么不难发现a[a[n]] = 1*1 + (2+3)*2 + (4+5)*3 + (6+7+8)*4 + ... + (pre+1 + pre+2 + ... + pre+b[p] ) * p

b[p]为p在原序列中出现的次数

pre，b[p]这些值都可以预处理算出每次询问可以O（1）算出答案

pre 是第p-1项的pre + b[p-1]

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long ll;

const int MOD = (int)1e9+;

const int INF = (int)1e9;

const int MAXN = ;

int a[MAXN+];

int b[MAXN+];

int sum[MAXN+];

int dp[MAXN+];

int pre[MAXN+];

int sz,val;

int add(int x,int y){

    x+=y;

    if(x>=MOD)x-=MOD;

    return x;

}

int po(int x,int n){

    int ans=;

    int temp=x;

    while(n){

        if(n&)ans=(ll)ans*temp%MOD;

        temp=(ll)temp*temp%MOD;

        n>>=;

    }

    return ans;

}

int main()

{

    val=po(,MOD-);

    a[]=;

    a[]=;

    a[]=;

    int sz=;

    for(int i=;;i++){

        int cnt=a[i];

        while(cnt){

        a[++sz]=i;

        cnt--;

        if(sz>=MAXN)break;

        }

        if(sz>=MAXN)break;

    }

    for(int i=;i<=MAXN;i++){

        sum[i]=sum[i-]+a[i];

        if(sum[i]>=INF)break;

    }

    for(int i=;i<=MAXN;i++){

        dp[i]=add(dp[i-],(ll)( add(add(add(pre[i-],),pre[i-]),a[i]) )*a[i]%MOD*i%MOD*val%MOD);

        pre[i]=add(pre[i-],a[i]);

    }

    int t;scanf("%d",&t);

    while(t--){

        int n;scanf("%d",&n);

        int l=,r=MAXN;

        int pos;

        while(l<=r){

            int mid=l+r>>;

            if(n<=sum[mid]){

                pos=mid;

                r=mid-;

            }

            else l=mid+;

        }

        int x=n-sum[pos-];

        int ans=add(dp[pos-],(ll)( add(add(add(pre[pos-],),pre[pos-]),x) )*x%MOD*pos%MOD*val%MOD);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

Aggregated Counting（找规律 + 预处理）

Aggregated Counting

最新文章

热门文章