快速幂/矩阵快速幂

快速幂:

int pow_mod(int a,int b,int c)
{
    a=a%c;
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans;
}

快速乘法:

ll q_mul(ll a,ll b)//计算a*b%mod的值
{
    ll ans=0;
    while(b)
    {
        if(b&1)
        {
            ans=(ans+a)%mod;
        }
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}

矩阵快速幂模板:

依赖:#define mem(a,b) memset(a,b,sizeof(a)) 与全局模数 const ll mod=...。 注意:矩阵元素为 int a[N][N],当 mod 接近 1e9 时 a.a[i][j]*b.a[j][k] 会超出 int 范围,大模数下请把存储与中间运算改为 ll(或相乘前显式转 (ll))。

const int N=2;
struct Matrix
{
	int a[N][N];
	Matrix()
	{
		mem(a,0);
	}
	void init()
	{
		mem(a,0);
		for(int i=0; i<N; i++)
			a[i][i]=1;
	}
};
void print(Matrix a)
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
			printf("%d ",a.a[i][j]);
		puts("");
	}
}
// 以下两个 mul 二选一,不能同时编译(函数签名相同会重定义)
Matrix mul(Matrix a,Matrix b)//未优化
{
	Matrix ans;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			for(int k=0; k<N; k++)
			{
				ans.a[i][j]+=a.a[i][k]*b.a[k][j];
				ans.a[i][j]%=mod;
			}
	return ans;
}
Matrix mul_sparse(Matrix a, Matrix b)//稀疏矩阵优化(与上方 mul 二选一,不能同时编译)
{
    Matrix ans;
    for (ll i = 0; i < N; i++)
        for (ll j = 0; j < N; j++)
            if (a.a[i][j])
                for (ll k = 0; k < N; k++)
                    ans.a[i][k] = (ans.a[i][k] + a.a[i][j] * b.a[j][k]) % mod;
    return ans;
}
Matrix mat_pow(Matrix a,int n)
{
	Matrix ans;
	ans.init();
	while(n)
	{
		if(n&1)
			ans=mul(ans,a);
		a=mul(a,a);
		n>>=1;
	}
	return ans;
}