依旧是常数很大的板子。
在 H_Kaguya
改动之前,达到了 \(2.61\,s\) 的绝望时间
现在好多了,\(1.10\,s\)。(内存不连续访问我会记你一辈子的)
#include <iostream>
char ch;
short get_single() {
ch = getchar();
while(ch < '0')
ch = getchar();
return ch&15;
}
const int mod = 998244353;
const int g = 3;
const int g_inv = 332748118;
const int N = 2100010;
long long quick_pow(long long _a,int _n,int _p = mod) {
long long _res = 1;
while(_n) {
if(_n&1)
_res = _res*_a%_p;
_a = _a*_a%_p;
_n >>= 1;
}
return _res;
}
int rev[N];
int a[N], b[N];
int lim;
void ntt_init() {
int tmp = lim>>1;
for(int i = 1;i < lim;++i) {
rev[i] = rev[i>>1]>>1;
if(i&1)
rev[i] |= tmp;
}
}
void NTT(int *f,int opt) {
for(int i = 0;i < lim;++i)
if(i < rev[i])
std :: swap(f[i],f[rev[i]]);
long long w_n, w;
for(register int i = 1, step = 2;i < lim;i <<= 1, step <<= 1) {
w_n = quick_pow(~opt ? g : g_inv,(mod-1)/step);
for(register int j = 0, upd = i;j < lim;j += step, upd += step) {
w = 1;
for(register int k = j, l = i+j;k < upd;++k, ++l, w = w*w_n%mod) {
int y = w*f[l]%mod;
f[l] = f[k]-y;
if(f[l] < 0)
f[l] += mod;
f[k] += y;
if(f[k] >= mod)
f[k] -= mod;
}
}
}
if(!~opt) {
long long inv_lim = quick_pow(lim,mod-2);
for(int i = 0;i < lim;++i)
f[i] = f[i]*inv_lim%mod;
}
}
int n, m;
int main() {
scanf("%d %d",&n,&m);
for(int i = 0;i <= n;++i)
a[i] = get_single();
for(int i = 0;i <= m;++i)
b[i] = get_single();
n += m;
lim = 1<<31-__builtin_clz(n);
if(lim&n)
lim <<= 1;
ntt_init();
NTT(a,1);
NTT(b,1);
for(int i = 0;i < lim;++i)
a[i] = 1ll*a[i]*b[i]%mod;
NTT(a,-1);
for(int i = 0;i <= n;++i)
printf("%d ",a[i]);
return 0;
}
原文地址:http://www.cnblogs.com/bikuhiku/p/Fast_Number-Theoretic_Transform.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性