【洛谷 P5110】 块速递推（矩阵加速，分块打表）

题目链接

掌握了分块打表法了。原来以前一直想错了。。。

块的大小\(size=\sqrt n\)，每隔\(size\)个数打一个表，还要在\(0\text{~}size-1\)每个数打一个表。

然后就可以做到\(O(1)\)查询了。

比如要求\(A^{n}\)，只需要算出\(biao[n/size]*pow[n\mod size]\)就好了。

然后我是看题解用了通项公式。。事实上套个矩阵也没有影响。

#include <cstdio>

#include <cmath>

#define ll unsigned long long

#define MOD 1000000007

namespace Mker{

    ll SA,SB,SC;

    void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}

    ll rand(){

        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;

        ll t=SA;

        SA=SB,SB=SC,SC^=t^SA;return SC;

    }

}

int T, ans, tmp, a[1000010], b[1000010], c[1000010], d[1000010], e, size;

int n;

inline int f_pa(int k){

	return (long long)a[k / size] * c[k % size] % MOD;

}

inline int f_pb(int k){

	return (long long)b[k / size] * d[k % size] % MOD;

}

inline void make_a(int n, int k){

	tmp = 1;

	while(k){

	  if(k & 1) tmp = (long long)tmp * n % MOD;

	  n = (long long)n * n % MOD;

	  k >>= 1;

	}

	a[e] = tmp;

}

inline void make_b(int n, int k){

	tmp = 1;

	while(k){

	  if(k & 1) tmp = (long long)tmp * n % MOD;

	  n = (long long)n * n % MOD;

	  k >>= 1;

	}

	b[e] = tmp;

}

int main(){

	size = sqrt(1000000006); c[0] = d[0] = 1;

	for(int i = 0; i <= 1000000006; i += size, ++e)

	   make_a(94153035, i), make_b(905847205, i);

	for(int i = 1; i < size; ++i) c[i] = (long long)c[i - 1] * 94153035 % MOD;

	for(int i = 1; i < size; ++i) d[i] = (long long)d[i - 1] * 905847205 % MOD;

	scanf("%d", &T);

	Mker::init();

	while(T--){

	  n = Mker::rand() % 1000000006;

	  ans ^= (233230706ll * (f_pa(n) - f_pb(n)) % MOD + MOD) % MOD;

    }

    printf("%d\n", ans);

    return 0;

}

【洛谷 P5110】 块速递推（矩阵加速，分块打表）的相关教程结束。