3 篇博文 含有标签「算法」

国际象棋是很久以前由一个印度人 Shashi 发明的，当他把该发明献给国王的时候，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi 要求以这种方式给他一些粮食：棋盘的第 1 个方格里只放 1 粒麦粒，第 2 格 q 个,第 3 格 q^2^ 个,第 4 格 q^3^ 个……，直到 n 个格子全部放满。这个奖赏最终会是什么样子的呢？Shashi 已经有算法了，请你算一算吧。

当然 Shashi 并不关心具体的数有多少了，他有一个检验你的答案是否与他心意相通的办法:把你求出的答案对 100000007 取模看看和 Shashi 算的是否一样就行了。

输入描述

本题输入具有多组样例。

第一行为一个数 t (1 ≤ t ≤ 500)，代表测试数据的组数。

之后的 t 行，每行两个数 q, n (1 ≤ q, n ≤ 10^18^)，含义见题目描述。

输出描述

输出共 t 行，每行一个数，为你算的答案。 友情提醒：你算的答案应该比 100000007 小。

样例描述

样例输入：

3
2 1
2 2
2 3

样例输出：

1
3
7

样例解释

对于样例：

• q = 2, n = 1 时仅有1个麦粒
• q = 2, n = 2 时有 1 + 2 = 3 个麦粒
• q = 2, n = 3 时有 1 + 2 + 2^2^ = 7 个麦粒

作者｜cugbacm
单位｜中国地质大学（北京）
代码长度限制｜16 KB
时间限制｜1000 ms
内存限制｜256 MB

如下是一个起泡排序的修改程序:

long long BubbleSort(int r[],int n){
int bound,exchange=n-1;
long long ans=0;
while(exchange!=0){
    bound=exchange,exchange=0;
    for(int j=0;j<bound;j++){
        if(r[j]>r[j+1]) 
        {
            int temp=r[j];
            r[j]=r[j+1];
            r[j+1]=temp;
            ans++;
            exchange=j;
        }
    }
}
return ans;
}

请你给出上述函数的返回值。

输入描述

第一行一个正整数 n (1 ≤ n ≤ 2⋅10^5^) 接下来一行共 n 个数，依次为 r[] 中的元素且 r >中的元素 r[i] (0 ≤ i < n) 满足 −10^18^ ≤ r[i] ≤ 10^18^。

输出描述

一行一个数，函数的返回值。

样例

样例1

样例输入

1
1

样例输出

0

样例2

样例输入

2
1 2

样例输出

0

作者 | cugbacm
单位 | 中国地质大学（北京）
代码长度限制 | 16 KB
时间限制 | 1000 ms
内存限制 | 512 MB