最近队友拿来一个蛮有意思的东西
给定一个类似于斐波那契数列的东西，让你去求它的第(n)项((n<=10^{18}))，由于模数为1e9+7,可以先降一波幂,相当于(n<=10^9+7)，要么去推下特征方程要么矩阵快速幂，但是这题把带log的做法卡了，引出了一个被叫做光速幂的东西，但我感觉叫块速幂更正常点...
就叫块速幂吧，实际上很简单，如果求(p^q)，(p)已经给定，(q)的上限也已经确定是在(1e12)左右或者以下，设(sq=sqrt{q})那么我们线性预处理处理出(p cdots p^{sq}),再处理出(p^{sq},p^{2sq}cdots)
那看到这个式子应该很显然了(p^q=p^{q/sq}p^{sq}p^{q\%sq})
对于所有(n<=1e12)的询问我们都能(o(1))计算
类似板子的东西（这玩意真的有必要存板子么
struct KSM
{
int fac[MAXN];
int facp[MAXN];
ll p; //给定p
ll maxq = 1e9 + 10; //已知的p的幂次上限(maxq<=1e12)
int sqrtq;
void init(ll x)
{
sqrtq = int(sqrt(maxq)) + 1;
p = x;
//预处理到p^sqrtq
fac[0] = 1;
for (int i = 1; i <= sqrtq; i++)
fac[i] = 1LL * fac[i - 1] * p % MOD;
//再处理(p^sqtr)^sqtr
facp[0] = 1;
for (int i = 1; i <= sqrtq; i++)
facp[i] = 1LL * facp[i - 1] * fac[sqrtq] % MOD;
}
int cal(int x)
{
return 1LL * facp[x / sqrtq] * fac[x % sqrtq] % MOD;
}
}
队友拿来的那道题
解题过程
求(a_n=233a_{n-1}+666a_{n-2})
去网上搜下斐波那契通项公式怎么求就知道了
这种数列基本可以令(a_n=p^n)次将递推公式化成(p^2=233p+666)
解得(p_1=frac{233+sqrt{56953}}{2}), (p_2=frac{233-sqrt{56953}}{2})
(A,B)为任意实数,(a_n=Ap_1^n+Bp_2^n)
把(a_1=1,a_2=233)分别代入
如果把数值一开始带进去除了会受到233和666的毒害以外毫无意义..先把(p_1,p_2)放在里面推一波
可以得到(B=frac{233-p_1}{p_2(p_2-p_1)},A=frac{233-p_2}{p_1(p_1-p_2)})
所以(B=frac{frac{233-sqrt{56953}}{2}}{p_2(p_2-p_1)}=frac{p_2}{p_2(p_2-p_1)}=frac{1}{p_2-p_1}=frac{1}{sqrt{56953}})
同理(A=frac{-1}{sqrt{56953}})
所以(a_n=frac{(233+sqrt{56953})^n-(233-sqrt{56953})^n}{2^nsqrt{56953}})
掏出二次剩余板子找到(sqrt{56953})的二次剩余是(188305837)
所以在膜1e9+7条件下
(a_n=frac{(frac{233+188305837}{2})^n-(frac{233-188305837}{2})^n}{188305837})
(=frac{(94153035)^n-(905847205)^n}{188305837})
好像算好了 还被卡了一手常数
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// freopen("k.in", "r", stdin);
// freopen("k.out", "w", stdout);
// clock_t c1 = clock();
// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
mt19937 rnd(time(NULL));
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ls ((x) << 1)
#define rs ((x) << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<char, char> PCC;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 1e5 + 7;
const ll MAXM = 4e5 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-7;
ll qpw(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = (ans * a) % MOD;
(a *= a) %= MOD;
b >>= 1;
}
return ans;
}
struct KSM
{
int fac[MAXN];
int facp[MAXN];
ll p; //给定p
ll maxq = 1e9 + 10; //已知的p的幂次上限(maxq<=1e12)
int sqrtq;
void init(ll x)
{
sqrtq = int(sqrt(maxq)) + 1;
p = x;
//预处理到p^sqrtq
fac[0] = 1;
for (int i = 1; i <= sqrtq; i++)
fac[i] = 1LL * fac[i - 1] * p % MOD;
//再处理(p^sqtr)^sqtr
facp[0] = 1;
for (int i = 1; i <= sqrtq; i++)
facp[i] = 1LL * facp[i - 1] * fac[sqrtq] % MOD;
}
int cal(int x)
{
return 1LL * facp[x / sqrtq] * fac[x % sqrtq] % MOD;
}
} a, b;
namespace Mker
{
unsigned long long SA, SB, SC;
void init() { scanf("%llu%llu%llu", &SA, &SB, &SC); }
unsigned long long rand()
{
SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
unsigned long long t = SA;
SA = SB, SB = SC, SC ^= t ^ SA;
return SC;
}
} // namespace Mker
int del(int a, int b)
{
int tmp = a - b;
if (tmp < 0)
tmp += MOD;
return tmp;
}
int main()
{
int t;
a.init(94153035), b.init(905847205);
int inv = qpw(188305837, MOD - 2);
int ans = 0;
scanf("%d", &t);
Mker::init();
while (t--)
{
int n = Mker::rand() % (MOD - 1);
ans ^= 1LL * del(a.cal(n), b.cal(n)) * inv % MOD;
}
printf("%d
", ans);
return 0;
}