hdu6395 Sequence 2018杭电多校第7场1010 【矩阵快速幂+分块】

题目链接

题意：

给你A, B, C, D, p, n这些条件

通过公式

请你推出第n项答案（mod1e9+7）

题解： 有前面几项推出后一项的公式一般都是用矩阵快速幂来求， 主要是p/n难以进行操作，那么我们便根据p/n的值来进行分块

例如 p = 16  n = 55

分块可分为 ：

p/3 = 5          3

p/4 = 4          4

p/5 = 3          5

p/6 = 2          6 , 7 , 8

p/9 = 1          9 , 10 , 11, 12, 13, 14, 15, 16 

p/17 = 0       17 ........55 

以此类推在这些区间内的p/i的值不变

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

const int mod = 1e9+7;
int A, B, C, D, n, p;

struct Matrix{
	int t[3][3];
	Matrix(){
		memset(t, 0, sizeof(t));//初始化都为0 
	}
}mat; 

Matrix operator * (Matrix aa, Matrix bb){//定义矩阵相乘 
	Matrix cc;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			ll ans = 0;
			for(int k = 0; k < 3; k++){
				ans += (ll)aa.t[i][k]*bb.t[k][j];
			}
			cc.t[i][j] = ans%mod;
		}
	}
	return cc; 
}

Matrix QuickPow(Matrix aa, int b){//快速幂 
	Matrix cc = mat;
	while(b){
		if(b&1){
			cc = cc*aa;
		}
		aa = aa*aa;
		b>>=1;
	}
	return cc;
}
 
int main() {
	mat.t[0][0] = mat.t[1][1] = mat.t[2][2] = 1;
		/**
		1 0 0
		0 1 0
		0 0 1
		矩阵快速幂所用的单位矩阵 
		**/
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d%d%d%d%d",&A, &B, &C, &D, &p, &n);
		if(n == 1){
			printf("%d\n",A);
			continue;
		}
		Matrix f;
		f.t[0][0] = D;//   D C 0 
		f.t[0][1] = C;//   1 0 0 
		f.t[1][0] = 1;//   0 0 1
		f.t[2][2] = 1;
		int flag = 0;
		
		for(int i = 3; i <= n;){
			if(p/i == 0){//当i > p 时，p/i = 0 
				Matrix w = f;
				w = QuickPow(w, n-i+1);
				printf("%d\n",(w.t[0][0]*(ll)B+w.t[0][1]*(ll)A+w.t[0][2])%mod);
				flag = 1;
				break;
			}
			int j = min(n, p/(p/i));//分块 
			Matrix w = f;
			/**
			D C p/i       B       B*D+A*C+p/i
			1 0 0     *   A   =   B
			0 0 1         1       1
			**/
			w.t[0][2] = p/i;//在这个区间内 p/i的值不会变 
			w = QuickPow(w, j-i+1);
			ll a = (w.t[1][0]*(ll)B + w.t[1][1]*(ll)A + w.t[1][2]) % mod;
			ll b = (w.t[0][0]*(ll)B + w.t[0][1]*(ll)A + w.t[0][2]) % mod;
			A = a;
			B = b;
			i = j+1;
		}
		if(flag){
			continue;
		}
		printf("%d\n", B); 
	}
	return 0;
}