高精度不会啊啊啊QAQ

nuo_ru_nuoX @ 2023-06-07 19:48:15

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<stack>
#include<set>
using namespace std;
long long f(long long n) 
{
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n-1) + f(n-2);
}
int main()
{
    long long n;
    cin>>n;
    cout<<f(n);
}

by elbissoPtImaerD @ 2023-06-07 19:50:40

@jie41044 不会可以学：https://oi-wiki.org/math/bignum/#%E5%AE%9A%E4%B9%89。

by SCAR_L @ 2023-06-07 19:55:11

@jie41044 详见我的这篇文章。
要想直接看代码也可以看这里。

给个关注呗~~

by nuo_ru_nuoX @ 2023-06-07 19:56:57

扼扼扼...... 看了有一点点思路, 改革终于队了 谢前者

by nuo_ru_nuoX @ 2023-06-07 19:59:34

@SCAR_L 给了关关

(支持壶关吗)

by Eleveslaine @ 2023-06-07 20:01:56

指条明路：py

by FengYuXinMing @ 2023-06-07 20:11:01

@Franz_Liszt 6,C艹直呼：6

by Bodhi @ 2023-06-07 20:33:24

@jie41044

其实除了高精度，你的算法还有几个问题

一是时间复杂度，你的写法的时间复杂度是O(2^n)，在n<=5000的范围下肯定T飞，所以还需要加上记忆化

二是main结尾要加return 0，虽然测评机上都能过，但这是一个好习惯 ，指不定哪次就给你来个RE

我的代码（有些抽象）：

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

string mem[5010];
short resnum[2000]; // 开1000还爆RE的出题人是屑
string plus_(string x, string y)
{ // 抽象的高精加，我大概每次写的都不一样，因为只要原理弄懂了，一切都好搞
    memset(resnum, 0, sizeof(resnum)); // 三年OI一场空，多用不清见祖宗
    string res;
    int ressz = max(x.size(), y.size()) + 1;
    reverse(x.begin(), x.end());
    reverse(y.begin(), y.end());
    while (x.size() < ressz)
        x = x + '0';
    while (y.size() < ressz)
        y = y + '0'; // 补0，防止访问空下标
    int p = 0;
    for (p = 0; p < ressz; ++p)
    {
        resnum[p] += (x[p] - '0') + (y[p] - '0');
        if (resnum[p] >= 10)
        {
            resnum[p] %= 10;
            resnum[p + 1] += 1;
        }
    }
    char c;
    for (p = 0; p <= ressz; ++p)
    {
        c = resnum[p] + '0';
        res = res + c;
    }
    reverse(res.begin(), res.end());
    while (res[0] == '0') // 删前导0
        res.erase(0, 1);
    return res;
}
string f(int x)
{
    if (x == 1)
        return "1";
    if (x == 2)
        return "2";
    if (mem[x].size())
        return mem[x];
    return mem[x] = plus_(f(x - 1), f(x - 2));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr); // 读写优化
    int n;
    cin >> n;
    cout << f(n) << '\n';
    return 0;
}

调着高精度代码，我又回忆起了2021年初学高精度时被它支配的恐惧，因为细节太多

by nuo_ru_nuoX @ 2023-06-07 20:38:14

@Bodhi

拜谢大姥!!

先上膝盖

by SCAR_L @ 2023-06-07 21:55:29

@jie41044 当然