atcoder beginner contest 293 e - geometric progression 无法求逆元/数列通项-爱代码爱编程

传送门:ATcoder

题目描述:

Given integers A, X, and M,find ∑ i = 0 X − 1 A i \sum\limits_{i=0}^{X-1}Ai i=0∑X−1​Ai,modulo M

输入:
1000000000 1000000000000 998244353
输出:
919667211

首先X的范围达到了$1e12$,所以$O(X)$的算法肯定是过不了的.

然后当时我赛时就想起来之前有一次我做过一道自幂的题目,然后对与一个数不断自幂取模来说,必存在一个循环节.这个我在上述链接中已经有详细证明+解释,此处就不在赘述了.然后我就基于循环节的想法去打这道题.复杂度应该是低于$O(M)$的.但是可能是因为取模运算比较慢,所以最后是TLE了.

然后现在讲一下正解.首先假设你没有像我一样sb的去用循环节去做这道题,那么你应该不难发现 A i A^i Ai是一个等比数列,那么原题就是一道等比数列求和的题目,那么你可能十分的激动直接开做, 1 − q X 1 − X \frac{1-q^X}{1-X} 1−X1−qX​,分子只用快速幂可以解决,但是你会发现分母需要使用逆元,但是这个逆元可能是不存在的(可以证明,但是比较麻烦).所以不能直接求.

我们可以换一种想法就是将 ∑ i = 0 X − 1 A i \sum\limits_{i=0}^{X-1}Ai i=0∑X−1​Ai看成是一个等比数列的一个通项,也就是设一个 C i = ∑ i = 0 X − 1 A i Ci=\sum\limits_{i=0}^{X-1}Ai Ci=i=0∑X−1​Ai,可以显然的发现$Ci$本身就是一个等比数列,所以我们现在的任务就是求出CX的值即可.我们可以发现$Ci=C(i-1)\ast A+1$对于这种数列题,可以使用矩阵来快速解决

考虑有
[ C i ] = [ A 1 ] ∗ [ C i − 1 1 ] \left[ \begin{matrix} Ci \end{matrix} \right]=\left[ \begin{matrix} A&1 \end{matrix} \right]*\left[ \begin{matrix} Ci-1 \\ 1 \end{matrix} \right] [Ci​]=[A​1​]∗[Ci−11​]

但是为了满足矩阵乘法的正确性(行数相同),我们补充一下两边矩阵

[ C i 1 ] = [ A 1 0 1 ] ∗ [ C i − 1 1 ] \left[ \begin{matrix} Ci \\ 1\end{matrix} \right]=\left[ \begin{matrix} A&1 \\ 0 & 1 \end{matrix} \right]*\left[ \begin{matrix} Ci-1 \\ 1 \end{matrix} \right] [Ci1​]=[A0​11​]∗[Ci−11​]

定义初始矩阵为 C 0 = [ 0 1 ] C0=\left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] C0=[01​]
那么 C 1 = [ A 1 0 1 ] ∗ [ 0 1 ] C1=\left[ \begin{matrix} A & 1 \\ 0 & 1 \end{matrix} \right]*\left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] C1=[A0​11​]∗[01​]

那么 C X = [ A 1 0 1 ] x ∗ [ 0 1 ] CX=\left[ \begin{matrix} A & 1 \\ 0 & 1 \end{matrix} \right]^{x}*\left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] CX=[A0​11​]x∗[01​]

然后我们直接使用矩阵快速幂来迅速解决这道题即可

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int Mod,A,X;
int ans[10][10],x[10][10],c[10][10];
void x_pow() {
	for(int i=0;i<2;i++) {
		for(int j=0;j<2;j++) {
			c[i][j]=x[i][j];
			x[i][j]=0;
		}
	}
	for(int i=0;i<2;i++) {
		for(int j=0;j<2;j++) {
			for(int k=0;k<2;k++) {
				x[i][j]=(x[i][j]+c[i][k]*c[k][j]%Mod)%Mod;
			}		
		}
	}
}
void ans_pow() {
	for(int i=0;i<2;i++) {
		for(int j=0;j<1;j++) {
			c[i][j]=ans[i][j];
			ans[i][j]=0;
		}
	}
	for(int i=0;i<2;i++) {
		for(int j=0;j<1;j++) {
			for(int k=0;k<2;k++) {
				ans[i][j]=(ans[i][j]+x[i][k]*c[k][j]%Mod)%Mod;
			}
		}
	}
}
void juzhen_qpow(int k) {
	while(k) {
		if(k&1) ans_pow();
		k>>=1;
		x_pow();
	}
}
signed main() {
	A=read(),X=read(),Mod=read();
	x[0][0]=A;x[0][1]=1;x[1][0]=0;x[1][1]=1;
	ans[0][0]=0;ans[1][0]=1;
	juzhen_qpow(X);
	cout<<ans[0][0]<<endl;
	return 0;
}