思路

__int128 大法好！但是圈钱基金会不给用……

Py 大法好！但是圈钱基金会也不给用……

但是，洛谷可以用啊！

long long 可以写成 __int64，大概相当于 $10^{18}$；而 __int128 的存储范围相当于 long long 的平方，也就是 $10^{36}$。

如果 $n$ 为 $10^9$，则右下角的数大概为 $10^{18}$，则所有数的和也达不到 $10^{36}$，这不就是为 __int128 量身定制的吗？

而且，题目里有一句话：

对于 $100\%$ 的数据：$1\le T\le 10^5$，
$1\le\color{red}\dfrac{K+1}2\le N\color{black} \le 10^9$。

看到标红的部分了吗？这代表我们最多只需要经过最后两行！

所以，我们求出倒数第二行要经过的个数和倒数第一行要经过的个数，用等差数列求和公式直接求解即可。

还有一点，__int128 需要手写输入输出函数，这个不难，很好实现。

代码

#include <iostream>
#include <stack>

using namespace std;

__int128 ans, ks, _1, _2;
unsigned long long t, n, k; // 输入不需要使用 __int128，不需要手写输入。
bool ss;
void out(__int128 s){
	stack<int> st;
	while (s){
		st.push(int(s % 10));
		s /= 10;
	}
	while (st.size()){
		cout << st.top(); // 按位逆序输出
		st.pop();
	}
	cout << endl;
}
int main(){
	cin >> t;
	while (t --){
		cin >> n >> k;
		ss = k % 2;
		k /= 2;
		ks = n * (n + 1) / 2;
		_1 = (ks * 2 - k + 1) * k / 2; // 倒数第一行的和
		_2 = ((ks - n) * 2 - k + 1) * k / 2; // 倒数第二行的和
		ans = _1 + _2;
		if (ss) ans += ks - k; // 若无法整除，则加上最后一行从右往左数第 k 个
		out(ans % 1000000007); // 输出
	}
}