75分求助

P1009 [NOIP1998 普及组] 阶乘之和

I_AK_Ynoi @ 2022-07-09 11:59:20

#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline __int128 read(){
        register __int128 x = 0,f = 1;
        register char ch = getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-'){
                f = -1;
            }
            ch = getchar();
        }
        while(ch>='0'&&ch<='9'){
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x*f;
    }
    inline void write(__int128 x){
        if(x<0){
            putchar('-');
            x = -x;
        }
        register int n = 0;
        char s[100];
        while(x||!n){
            s[n++] = '0' + x % 10;
            x /= 10;
        }
        while(n--){
            putchar(s[n]);
        }
        return;
    }
}
using namespace IO;
int main(){
    __int128 a[1000], b = 0, n;
    n = read();
    a[1] = 1;
    for(int i=2;i<=n+1;i++){
        a[i] = a[i-1] * i;
    }
    for(int i=1;i<=n;i++){
        b = b + a[i];
    }
    write(b);
    return 0;
}

by I_AK_Ynoi @ 2022-07-09 12:02:10

有没有比__int128更大的?


by Super_Supper @ 2022-07-09 12:05:08

@I_AK_Ynoi 有,高精度


by I_AK_Ynoi @ 2022-07-09 12:06:28

验证码 czfq 祭


by I_AK_Ynoi @ 2022-07-09 12:07:06

高精度代码有点长,本人很懒


by Super_Supper @ 2022-07-09 12:08:33

@I_AK_Ynoi python?


by I_AK_Ynoi @ 2022-07-09 12:09:27

谢谢您,我去写Python


by I_AK_Ynoi @ 2022-07-09 12:11:08

n=int(input())
sum = 0
sum1 = 1
for i in range(1,n+1):
    for j in range(1,i+1):
        sum1 *= j
    sum += sum1
    sum1 = 1
print(sum)

A了这道题


by Ruiqun2009 @ 2022-07-12 15:24:29

@I_AK_Ynoi 如果真要写高精度的话,配上4次NTT的MTT高精乘法是最佳选择 (虽然本题用不到)

高精板子大概是这样的: 运算 时间复杂度 空间复杂度 附注
\Theta(n),O(n),\Omega(n) \theta(1),o(1),\omega(1)
\Theta(n),O(n),\Omega(n) \theta(1),o(1),\omega(1)
\Theta(n\log n),O(n\log n),\Omega(n\log n) \theta(n),o(n),\omega(n)
\Theta(n\log n),O(n\log n),\Omega(n\log n) \theta(n\log n),o(n\log n),\omega(n\log n) 由于是牛迭,常数有点大
\Theta(n\log n),O(n\log n),\Omega(n\log n) \theta(n\log n),o(n\log n),\omega(n\log n)

我啥时候才能写出这样的高精板子。


|