complexor @ 2022-01-19 11:26:08
蒟蒻在做 P1919 【模板】A*B Problem 升级版(FFT 快速傅里叶变换) 这题时遇到一个关于
在NTT时:
若在临时前加入static修饰符,则会无报错消息地编译失败:
void NTT(int *g, bool fl, int n)
{
tsetup(n);
static ull f[MAXN << 1], w[MAXN << 1] = {1};//就是这里
for (int i = 0; i < n; i++)
f[i] = (((ll)MOD << 5) + g[tr[i]]) % MOD;
for (int len = 1; len < n; len <<= 1)
{
ull rt = fpow(fl ? _G : invG, (MOD - 1) / (len << 1));
for (int i = 1; i < len; i++)
w[i] = w[i - 1] * rt % MOD;
for (int p = 0; p < n; p += (len << 1))
for (int cur = 0; cur < len; cur++)
{
int t = w[cur] * f[p | len | cur] % MOD;
f[p | len | cur] = f[p | cur] + MOD - t;
f[p | cur] = f[p | cur] + t;
}
if (len == (1 << 10))
for (int i = 0; i < n; i++)
f[i] %= MOD;
}
if (fl)
for (int i = 0; i < n; i++)
g[i] = f[i] % MOD;
else
{
ull invn = inv(n);
for (int i =0; i < n; i++)
g[i] = f[i] % MOD * invn % MOD;
}
}
若去除修饰符,则可以愉快的AC:
oid NTT(int *g, bool fl, int n)
{
tsetup(n);
ull f[MAXN << 1], w[MAXN << 1] = {1};//还是这里
for (int i = 0; i < n; i++)
f[i] = (((ll)MOD << 5) + g[tr[i]]) % MOD;
for (int len = 1; len < n; len <<= 1)
{
ull rt = fpow(fl ? _G : invG, (MOD - 1) / (len << 1));
for (int i = 1; i < len; i++)
w[i] = w[i - 1] * rt % MOD;
for (int p = 0; p < n; p += (len << 1))
for (int cur = 0; cur < len; cur++)
{
int t = w[cur] * f[p | len | cur] % MOD;
f[p | len | cur] = f[p | cur] + MOD - t;
f[p | cur] = f[p | cur] + t;
}
if (len == (1 << 10))
for (int i = 0; i < n; i++)
f[i] %= MOD;
}
if (fl)
for (int i = 0; i < n; i++)
g[i] = f[i] % MOD;
else
{
ull invn = inv(n);
for (int i =0; i < n; i++)
g[i] = f[i] % MOD * invn % MOD;
}
}
有没有大佬知道这是什么原因?
by 幽灵特工 @ 2022-01-19 11:30:39
@complexor 可否把完整代码发出来让我调试一下
by 幽灵特工 @ 2022-01-19 11:31:15
哦已经解决了吗那就没事了
没解决再艾特我
by complexor @ 2022-01-19 11:35:55
解决了但不知道怎么解决的
by complexor @ 2022-01-19 11:44:41
哦懂了,所以把初始化的 "={1}"删去就可以了
static ull f[MAXN << 1], w[MAXN << 1];
w[0] = 1;
by complexor @ 2022-01-19 11:45:18
但为什么本地能过?
by rxjdasiwzl @ 2022-01-19 11:45:34
@complexor 大括号初始化巨大数组导致编译出来的可执行文件太大。所以不要用大括号初始化数组。
by 小粉兔 @ 2022-01-19 12:30:25
@rxjdasiwzl 正确的。
by 小粉兔 @ 2022-01-19 12:31:18
特别是不要初始化全局数组。常见于筛法对质数判断数组的初始化,数组大小一开大就寄了。
by complexor @ 2022-01-20 12:43:08
学到了 蟹蟹大佬
orz