HDU 5439 Aggregated Counting

Aggregated Counting

Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 672    Accepted Submission(s): 305

Problem Description Aggregated Counting Meetup (ACM) is a regular event hosted by Intercontinental Crazily Passionate Counters (ICPC). The ICPC people recently proposed an interesting sequence at ACM2016 and encountered a problem needed to be solved.

The sequence is generated by the following scheme.

1. First, write down 1, 2 on a paper.

2. The 2nd number is 2, write down 2 2’s (including the one originally on the paper). The paper thus has 1, 2, 2 written on it.

3. The 3rd number is 2, write down 2 3’s. 1, 2, 2, 3, 3 is now shown on the paper.

4. The 4th number is 3, write down 3 4’s. 1, 2, 2, 3, 3, 4, 4, 4 is now shown on the paper.

5. The procedure continues indefinitely as you can imagine. 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, . . . .

The ICPC is widely renowned for its counting ability. At ACM2016, they came up with all sorts of intriguing problems in regard to this sequence, and here is one: Given a positive number  n , First of all, find out the position of the last  n  that appeared in the sequence. For instance, the position of the last 3 is 5, the position of the last 4 is 8. After obtaining the position, do the same again: Find out the position of the last (position number). For instance, the position of the last 3 is 5, and the position of the last 5 is 11. ICPC would like you to help them tackle such problems efficiently.

Input The first line contains a positive integer  T,T≤2000 , indicating the number of queries to follow. Each of the following  T  lines contain a positive number  n(n≤109)  representing a query.  

Output Output the last position of the last position of each query  n . In case the answer is greater than  1000000006 , please modulo the answer with  1000000007 .  

Sample Input

3
3
10
100000
        

Sample Output

11
217
507231491
        

Source 2015 ACM/ICPC Asia Regional Changchun Online  

看了好久才懂的一題、、、

自己看懂了規律，英文差還是有好處的，一開始自己寫的時候就認為輸入的n是求序列的前n項和、、、、

結果看了别人的部落格才知道、、、是求f(f(n))、、、

借鑒了一下：

若将題目中的A數組進行另一種寫法  則有

A 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 .......

如果用B來記錄出現i次的數有多少個  則有

B 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 ......

 A B 數組完全相同。

那麼就是求A的前n項和的問題了。。。因為n太大了  打表也打不出來、、、是以就對公式化簡

在B數組中，暴力跑一邊發現  b的前400000多萬項和已經大于1e9了，40多萬不是很大，是以就拿B數組作為突破口

A與B的關系呢、、、就是 sum(Ai|1<=i<=n)=1*1+(2+3)*2+(4+5)*3+...+(Bp項)p

最後的一個不足Bp項、、、

這樣看來，隻要确定每一個p的序列開頭，則可以用B數組确定裡面有幾個連續的數，等差數列前n項和就能快速的出和了。是以隻要打40+萬的表就能解決了、、、

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

ll ans[500010],b[500010],a[500010];
int len;
const ll Mod=1e9+7;

void init()
{
    a[1]=1;
    a[2]=2;
    b[1]=1;
    b[2]=11;
    ans[1]=1;
    ans[2]=3;
    int it=2,aa=a[it]-1;
    for(int i=3;;i++)
    {
        a[i]=it;
        aa--;
        ans[i]=ans[i-1]+it;//儲存第i個等差數列的其實項
        b[i]=(b[i-1]+((ans[i]+ans[i-1]+1)*it*i/2)%Mod)%Mod;
        if(aa==0)
        {
            it++;
            aa=a[it];
        }

        if(ans[i]>=1e9)
        {
            len=i;
            break;
        }
    }
}

int main()
{
    len=0;
    init();
    int t,n;
    scanf("%d",&t);
    while(t--&&scanf("%d",&n))
    {
        int low=lower_bound(ans+1,ans+len,n)-ans; //确定n是在哪一個連續的區間内
            ll sum=b[low]; 
            sum=((sum-((ans[low]-n)*(n+1+ans[low])/2)*low%Mod)%Mod+Mod)%Mod; //減掉n+1到該區間最後的數的結果
            printf("%lld\n",sum);
    }
}