|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 KeyError 于 2023-11-27 17:32 编辑
背景
张三(对就是那个法外狂徒)发了酒疯,要你帮他算广义费波纳基数列。
因为他很狂所以你要在2秒之内算出来,不然他就会 你。
描述
张三会给你一个小于232的正整数n,请你算出数列的第n项 mod 232。
(广义费波纳基数列是指f(x)=p*f(x-2)+q*f(x-1)的数列)
输入格式
输出格式
数据范围
0<n<232
0<p,q<10
注:
当p=q=1时:
f0 = 1
f1 = 1
f2 = 2
f3 = 3
f4 = 5
f5 = 8
...
已更改mod
哈哈,矩阵快速幂板子题,改一下矩阵的数字就行了。代码:
- #include <bits/stdc++.h>
- using namespace std;
- const long long p = 1ll << 32;
- struct Info {
- long long data[4][4];
- int n, m;
- void init() {
- data[1][1] = data[1][2] = data[2][2] = data[2][1] = 0;
- n = m = 0;
- }
- Info operator * (const Info &b) const {
- Info res;
- memset(res.data, 0, sizeof(res.data));
- res.n = n;
- res.m = b.m;
- for (int i = 1; i <= res.n; i++)
- for (int j = 1; j <= res.m; j++)
- for (int k = 1; k <= b.n; k++)
- res.data[i][j] += data[i][k] * b.data[k][j] % p,
- res.data[i][j] %= p;
- return res;
- }
- };
- Info qpow(Info a, long long k) {
- Info res;
- res.init();
- res.n = a.n;
- res.m = a.m;
- for (int i = 1; i <= a.n; ++i) res.data[i][i] = 1;
- while (k) {
- if (k & 1) res = res * a;
- a = a * a;
- k >>= 1;
- }
- return res;
- }
- Info a;
- long long k, x, y;
- int n;
- long long fib(long long n) {
- Info a;
- a.init();
- a.n = a.m = 2;
- a.data[1][1] = x;
- a.data[1][2] = y;
- a.data[2][1] = 1;
- a.data[2][2] = 0;
- Info f0;
- f0.init();
- f0.n = 1;
- f0.m = 2;
- f0.data[1][1] = 1;
- f0.data[1][2] = 1;
- return (qpow(a, n) * f0).data[2][1];
- }
- int main() {
- long long n;
- scanf("%lld%lld%lld", &n ,&x, &y);
- printf("%lld\n",fib(n));
- }
复制代码
f(0), f(1),f(2) 的定义不太明确,我就懒得管这些了
|
|