FFT/NTT 擂台
这里有个在线评测网站，可以按照运行速度排序。我在一些提交抢到了前三的位置。欢迎大家来攻擂！只能提交单个文件，数据需要与标准 IO 交互，应该只能单线程。
[*]多项式乘法 https://judge.yosupo.jp/problem/convolution_mod
[*]多项式乘法(非ntt模数) https://judge.yosupo.jp/problem/convolution_mod_1000000007
[*]多项式乘法逆 https://judge.yosupo.jp/problem/inv_of_formal_power_series
[*]多项式幂函数 https://judge.yosupo.jp/problem/pow_of_formal_power_series
[*]多项式多点求值 https://judge.yosupo.jp/problem/multipoint_evaluation
[*]多项式快速插值 https://judge.yosupo.jp/problem/polynomial_interpolation
其他还有很多算法，不一一列举了。 没想到查着算法查回dalao帖子里了hhh，那就看看高精度乘法所用的FFT吧 https://duck.ac/submission/20297 https://duck.ac/submission/22458 这个回帖中的代码只有967个字节，但是运行速度排到15名，不知是原始代码是何人所写。
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstring>
using U=unsigned;using V=unsigned long long;constexpr U P=998244353,N=1<<21;constexpr U F(U a,U b){U c=1;for(;b;b/=2)b&1&&(c=(V)c*a%P),a=(V)a*a%P;return c;}U R,T{0,1};void f(U*a){for(U b=1;b^N;b++)if(R<b)a^=a]^=a^=a];for(U b=1,c,d,e,f;b^N;b*=2)for(c=0;c^N;c+=b*2)for(d=0;d^b;d++)e=a,f=(V)a*T%P,(a=e+f)>=P&&(a-=P),(a=e-f)>=P&&(a+=P);}main(){for(U a=1;a^N;a++)R=(R+a%2*N)/2;for(U a=2,b,c;a^N;a*=2)for(b=F(3,P/a/2),c=a/2;c^a;c++)T=T,T=(V)T*b%P;std::cin.tie(0)->sync_with_stdio(0);U a,b,c{},d{};char x,y;std::cin>>x>>y,a=strlen(x)-1,b=strlen(y)-1;for(U e=0;e<=a;e++)c=x^48;for(U e=0;e<=b;e++)d=y^48;f(c),f(d);for(U e=0;e^N;e++)c=(V)c*d%P;f(c);a+=b+1;for(U e=*d=0,f=F(N,P-2);e^a;e++)d+=(V)c[(N-e)%N]*f%P,d=d/10,d%=10;while(!d)a--;for(;~a;a--)std::cout<<d;}
liangbch 发表于 2024-11-24 13:36
https://duck.ac/submission/22458 这个回帖中的代码只有967个字节，但是运行速度排到15名，不知是原始代码 ...
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstring>
using U = unsigned;
using V = unsigned long long;
constexpr U P = 998244353, N = 1 << 21;
constexpr U F(U a, U b)
{
U c = 1;
for (; b; b /= 2)
b & 1 && (c = (V)c*a%P), a = (V)a*a%P;
return c;
}
U R, T{ 0,1 };
void f(U*a) {
for (U b = 1; b^N; b++)
if (R < b)
a ^= a] ^= a ^= a];
for (U b = 1, c, d, e, f; b^N; b *= 2)
for (c = 0; c^N; c += b * 2)
for (d = 0; d^b; d++)
e = a, f = (V)a * T % P, (a = e + f) >= P && (a -= P), (a = e - f) >= P && (a += P);
}
main() {
for (U a = 1; a^N; a++)
R = (R + a % 2 * N) / 2;
for (U a = 2, b, c; a^N; a *= 2)
for (b = F(3, P / a / 2), c = a / 2; c^a; c++)
T = T, T = (V)T * b%P;
std::cin.tie(0)->sync_with_stdio(0);
U a, b, c{}, d{};
char x, y;
std::cin >> x >> y, a = strlen(x) - 1, b = strlen(y) - 1;
for (U e = 0; e <= a; e++)
c = x ^ 48;
for (U e = 0; e <= b; e++)
d = y ^ 48;
f(c), f(d);
for (U e = 0; e^N; e++)
c = (V)c * d % P; f(c);
a += b + 1;
for (U e = *d = 0, f = F(N, P - 2); e^a; e++)
d += (V)c[(N - e) % N] * f%P, d = d / 10, d %= 10;
while (!d)a--;
for (; ~a; a--)
std::cout << d;
}
写着代码的人怎么没被打死?! :lol;P
页:
[1]