2018-12-26 17:54


  • Golang
  • r语言
  • erlang

Problem Description
Recently, Mr. Frog has learned binary indexed tree. Here is the code of adding t to the interval [1,x]:

void add (int x, int t ){
    for (int i = x; i != 0; i -= i & (-i))
        a[i] += t;

If Mr. Frog is required to add t to the interval [l,r], he will add(r,t), and then add(l - 1,-t).

The cost of an interval [l,r] is defined as the number of the “really changed point”. The “really changed point” is the point whose value is modified by the given code.

For example, in order to add 1 to the interval [6,6], Mr. Frog will add 1 to the interval 1,6, and add -1 to the interval 1,5.

As the result, a[6] will be added by 1, a[5] will be added by -1, and a[4] will be added by 0. a[6] and a[5] are “really changed point”, and the cost is 2.

Mr. Frog wants to calculate the sum of the cost of the interval [l,r]⊆ [1,n] where l and r are two integers. Help Mr. Frog solve the problem.

The first line contains only one integer T (T≤10000), which indicates the number of test cases.

For each test case, it contains an integer n (1≤n≤1018).

For each test case, output one line ”Case #x: y”, where x is the case number (starting from 1), y is the sum of the cost (modulo 1000000007).

Sample Input

Sample Output
Case #1: 1
Case #2: 4
Case #3: 10

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享