找回密码
 欢迎注册
查看: 6080|回复: 3

[擂台] FFT/NTT 擂台

[复制链接]
发表于 2023-6-28 13:59:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
这里有个在线评测网站,可以按照运行速度排序。我在一些提交抢到了前三的位置。欢迎大家来攻擂!

只能提交单个文件,数据需要与标准 IO 交互,应该只能单线程。



其他还有很多算法,不一一列举了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-1-11 23:23:52 | 显示全部楼层
没想到查着算法查回dalao帖子里了hhh,那就看看高精度乘法所用的FFT吧 https://duck.ac/submission/20297

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首帖奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-11-24 13:36:46 | 显示全部楼层
https://duck.ac/submission/22458 这个回帖中的代码只有967个字节,但是运行速度排到15名,不知是原始代码是何人所写。


  1. #pragma GCC optimize("Ofast")
  2. #include<iostream>
  3. #include<cstring>
  4. 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[N],T[N]{0,1};void f(U*a){for(U b=1;b^N;b++)if(R[b]<b)a[b]^=a[R[b]]^=a[b]^=a[R[b]];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[c+d],f=(V)a[b+c+d]*T[b+d]%P,(a[c+d]=e+f)>=P&&(a[c+d]-=P),(a[b+c+d]=e-f)>=P&&(a[b+c+d]+=P);}main(){for(U a=1;a^N;a++)R[a]=(R[a/2]+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[c*2]=T[c],T[c*2+1]=(V)T[c]*b%P;std::cin.tie(0)->sync_with_stdio(0);U a,b,c[N]{},d[N]{};char x[N],y[N];std::cin>>x>>y,a=strlen(x)-1,b=strlen(y)-1;for(U e=0;e<=a;e++)c[e]=x[a-e]^48;for(U e=0;e<=b;e++)d[e]=y[b-e]^48;f(c),f(d);for(U e=0;e^N;e++)c[e]=(V)c[e]*d[e]%P;f(c);a+=b+1;for(U e=*d=0,f=F(N,P-2);e^a;e++)d[e]+=(V)c[(N-e)%N]*f%P,d[e+1]=d[e]/10,d[e]%=10;while(!d[a])a--;for(;~a;a--)std::cout<<d[a];}
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复 支持 1 反对 0

使用道具 举报

发表于 2025-9-19 15:47:13 | 显示全部楼层
liangbch 发表于 2024-11-24 13:36
https://duck.ac/submission/22458 这个回帖中的代码只有967个字节,但是运行速度排到15名,不知是原始代码 ...
  1. #pragma GCC optimize("Ofast")
  2. #include<iostream>
  3. #include<cstring>
  4. using U = unsigned;
  5. using V = unsigned long long;
  6. constexpr U P = 998244353, N = 1 << 21;
  7. constexpr U F(U a, U b)
  8. {
  9.         U c = 1;
  10.         for (; b; b /= 2)
  11.                 b & 1 && (c = (V)c*a%P), a = (V)a*a%P;
  12.         return c;
  13. }
  14. U R[N], T[N]{ 0,1 };
  15. void f(U*a) {
  16.         for (U b = 1; b^N; b++)
  17.                 if (R[b] < b)
  18.                         a[b] ^= a[R[b]] ^= a[b] ^= a[R[b]];

  19.         for (U b = 1, c, d, e, f; b^N; b *= 2)
  20.                 for (c = 0; c^N; c += b * 2)
  21.                         for (d = 0; d^b; d++)
  22.                                 e = a[c + d], f = (V)a[b + c + d] * T[b + d] % P, (a[c + d] = e + f) >= P && (a[c + d] -= P), (a[b + c + d] = e - f) >= P && (a[b + c + d] += P);
  23. }
  24. main() {
  25.         for (U a = 1; a^N; a++)
  26.                 R[a] = (R[a / 2] + a % 2 * N) / 2;
  27.         for (U a = 2, b, c; a^N; a *= 2)
  28.                 for (b = F(3, P / a / 2), c = a / 2; c^a; c++)
  29.                         T[c * 2] = T[c], T[c * 2 + 1] = (V)T[c] * b%P;
  30.         std::cin.tie(0)->sync_with_stdio(0);
  31.         U a, b, c[N]{}, d[N]{};
  32.         char x[N], y[N];
  33.         std::cin >> x >> y, a = strlen(x) - 1, b = strlen(y) - 1;
  34.         for (U e = 0; e <= a; e++)
  35.                 c[e] = x[a - e] ^ 48;
  36.         for (U e = 0; e <= b; e++)
  37.                 d[e] = y[b - e] ^ 48;
  38.         f(c), f(d);
  39.         for (U e = 0; e^N; e++)
  40.                 c[e] = (V)c[e] * d[e] % P; f(c);
  41.         a += b + 1;
  42.         for (U e = *d = 0, f = F(N, P - 2); e^a; e++)
  43.                 d[e] += (V)c[(N - e) % N] * f%P, d[e + 1] = d[e] / 10, d[e] %= 10;
  44.         while (!d[a])a--;
  45.         for (; ~a; a--)
  46.                 std::cout << d[a];
  47. }
复制代码

写着代码的人怎么没被打死?!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-10-9 09:59 , Processed in 0.025166 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表