题意：

写下一组数，

1.先写1,2,2。

2.第三个数字是2，所以在后面写两个3。

3.第四个数字是3，所以在后面三个4。

4.像这样可以得到1,2,2,3,3,4,4,4,5,5,5,6,6,6,6。

给出一个数字n，假设这个n的最后出现的位置为p，求p最后出现的位置。其中$n≤10^9$。

思路：

可以找出规律要求的$F[n]=pre[pre[n]]$，其中$pre[n]$为原数列的前缀和，可以写几项。

$$F[1]=pre[pre[1]]=1$$ $$F[2]=pre[pre[2]]=pre[3]=1*1+2*2$$ $$F[3]=pre[pre[3]]=pre[5]=1*1+2*2+3*2$$ $$F[4]=pre[pre[4]]=pre[8]=1*1+2*2+3*2+4*3$$ $$F[5]=pre[pre[5]]=1*1+2*2+3*2+4*3+5*3=1*1+(2+3)*2+(4+5)*3$$ $$F[6]=1*1+(2+3)*2+(4*5)*3+6*4$$ $$F[7]=1*1+(2+3)*2+(4*5)*3+(6+7)*4$$ $$F[8]=1*1+(2+3)*2+(4*5)*3+(6+7+8)*4$$

由此可以知道$F[n]=\sum_{i=1}^ni*f[i]$，其中$f[i]$表示原数列。

因为原数列可以根据值分成几块，所以预处理出

$f[i]$：原数列，

$locr[i]$：i最后一次出现的位置，

$pre[i]$：第$locr[i]$个数的$F[i]$。

这些东西就可以了，对于一个n其他多余的要加的东西可以在块内进行。

所以二分一下每个n在哪一块里再把前面的$pre$和块内的加起来就可以了。

找规律的题做法直接说出来的确有点抽象，这种东西还是要自己手推一下…

找规律的题分块的确是一种写法。

代码：

#define MOD 1000000007
typedef long long ll;
int cnt;
ll f[1000010];
ll locr[1000010];//最后一次出现的位置
ll pre[1000010];//第locr[i]个数的值
int init()
{
    f[1]=1;f[2]=2;f[3]=2;
    int cur=3;
    for(ll i=3;cur<=440000;i++)
    {
        for(int j=0;j<f[i];j++)
            f[++cur]=i;
    }
    /*for(int i=1;i<=20;i++)
        printf("%lld ",f[i]);
    printf("\n");*/
    locr[1]=1;
    for(int i=2;;i++)
    {
        locr[i]=locr[i-1]+f[i];
        if(locr[i]>1e9)
        {
            cnt=i-1;
            break;
        }
    }
    /*for(int i=1;i<=10;i++)
        printf("%lld ",locr[i]);
    printf("\n");*/
    pre[1]=1;
    for(int i=2;i<=cnt;i++)
        pre[i]=(pre[i-1]+((((locr[i-1]+1+locr[i])*(locr[i]-locr[i-1]))%MOD*500000004ll)%MOD*i)%MOD)%MOD;
    /*for(int i=1;i<=10;i++)
        printf("%lld ",pre[i]);
    printf("\n");*/
}
int main()
{
    init();
    //printf("%d\n",cnt);
    int t;
    ll n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        int pos=upper_bound(locr+1,locr+1+cnt,n)-locr;
        pos--;
        //printf("%d\n",pos);
        ll ans=0;
        ans=(ans+pre[pos])%MOD;
        ans=(ans+((((locr[pos]+1+n)*(n-locr[pos]))%MOD*500000004ll)%MOD*(pos+1))%MOD)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}