题目描述

给定两个正整数 $x, n$， 求 $x^0+x^1+x^2+x^3+...+x^n$ 的值

由于结果太大, 只需要输出结果模 998244353 的余数

• 提示
• 设：$f(n) = x^0+x^1+x^2+x^3+...+x^n$
• $xf(n)=x^1+x^2+x^3+...+x^n+x^{n+1}$
• $xf(n)-f(n)=x^{n+1}-x^0$
• $f(n)=\frac{x^{n+1}-1}{x-1}$
• $x^{n+1}$ 可以用快速幂求出
• $\frac{1}{x-1}$ 可以用乘法逆元算出（$x==1$ 时需要特判）

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int P = 998244353;

// n >= 1, 二进制求快速幂
template<typename T>
T power(T x, i64 n) {
	T ans = x; n -= 1;
	for (; n > 0; n >>= 1, x = x * x % P) if (n & 1) ans = ans * x % P;
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	i64 x, n;
	cin >> x >> n;
	if (x == 1) cout << n % P << '\n';
	else {
		i64 p = power(x, n + 1) - 1;  // 注意这里 p 可能是负数
		i64 q = power(x - 1, P - 2);  // 费马小定理求 x - 1 的逆元
		
		// 由于 p 可能是负数, 所以 p * q % P 也可能是负数
		cout << (p * q % P + P) % P << '\n';
	}
	return 0;
}

输入格式

• 输入两个正整数 $x, n (1 \le x \le 10^3, 1 \le n \le 10^{12})$
• 注意 $n$ 的值请用 long long 存储

输出格式

• 输出结果模 998244353 的余数

2 3

15

2 1000000000000

688880193

提示

• 样例 1

  • $2^0+2^1+2^2+2^3=1+2+4+8=15$

• 先看 $n$ 是奇数的情况

• 设 $f(5) = x^0+x^1+x^2+x^3+x^4+x^5$

  • $f(5) = x^0+x^1+x^2+x^3(x^0+x^1+x^2)$
  • $f(5) = (x^0+x^1+x^2)\cdot(1+x^3)$
  • $f(5) = f(2)\cdot(1+x^3)$
  • $f(5) = f(5/2)\cdot(1+x^{(5+1)/2})$
  • 那么只需要计算 $f(n/2)$ 就可以通过上面的公式计算出 $f(n)$

• 再看 $n$ 是偶数的情况

• 设 $f(6) = x^0+x^1+x^2+x^3+x^4+x^5+x^6$

  • $f(6) = x^0+x^1+x^2+x^3+x^3(x^0+x^1+x^2+x^3)-x^3$
  • $f(6) = (x^0+x^1+x^2+x^3)\cdot(1+x^3)-x^3$
  • $f(6) = f(3)\cdot(1+x^3)-x^3$
  • $f(6) = f(6/2)\cdot(1+x^{(6+1)/2})-x^{(6+1)/2}$
  • 那么只需要计算 $f(n/2)$ 就可以通过上面的公式计算出 $f(n)$

• 我们可以这样实现递归函数

long long solve(long long x, long long n) {
    // 第一步: 递归函数先写终止条件
    if (n == 0) return 1;

    // 第二步: 将问题分解成几个小问题
    long long ans = solve(x, n / 2);  // 小问题的答案
    long long d = power(x, (n + 1) / 2);
    // 请填写下面的逻辑
    // 由 ans 和 d 计算出答案
    
}

数据规模与限制

• $1 \le x \le 10^3, 1 \le n \le 10^{12}$
• 1s, 1024KiB for each test case.