QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129098 | #618. 多项式乘法 | Houraisan_Kaguya# | Compile Error | / | / | C++14 | 1.7kb | 2023-07-21 21:31:53 | 2023-07-21 21:31:56 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-21 21:31:56]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-07-21 21:31:53]
- 提交
answer
#include <stdio.h>
#include <algorithm>
#define sz 2777777
using namespace std;
#define long __int64
const int md = 998244353;
int n, m, len;
int fx[sz], gx[sz], poi[sz];
int read();
int fst(int, int);
void ntt(int*, int);
void ttn(int*, int);
int main()
{
n = read() + 1; m = read() + 1;
for (int i = 0; i < n; ++i)
fx[i] = read();
for (int i = 0; i < m; ++i)
gx[i] = read();
len = 1 << __lg(n + m) + 1;
for (int i = 1; i < len; ++i)
{
poi[i] = poi[i >> 1] >> 1;
if (i & 1)
poi[i] |= len >> 1;
}
ntt(fx, len); ntt(gx, len);
for (int i = 0; i < len; ++i)
fx[i] = (long)fx[i] * gx[i] % md;
ttn(fx, len);
for (int i = 0; i < n + m - 1; ++i)
printf ("%d ", fx[i]);
putchar('\n');
return 0;
}
int read()
{
int x = 0;
char c = getchar();
while (c < '0') c = getchar();
do {
x = x * 10 + (c & 15);
c = getchar();
}while (c >= '0');
return x;
}
int fst(int a, int b)
{
int c = 1;
while (b)
{
if (b & 1)
c = (long)c * a % md;
a = (long)a * a % md;
b >>= 1;
}
return c;
}
void ntt(int *a, int b)
{
for (int i = 1; i < b; ++i)
if (i < poi[i])
swap(a[i], a[poi[i]]);
int dt, now, tmp;
for (int i = 1; i < b; i <<= 1)
{
dt = fst(3, (md - 1) / i >> 1);
for (int j = 0; j < b; j += (i << 1))
{
now = 1;
for (int k = 0; k < i; ++k)
{
tmp = (long)now * a[j | k | i] % md;
a[j | k | i] = (a[j | k] + md - tmp) % md;
a[j | k] = (a[j | k] + tmp) % md;
now = (long)now * dt % md;
}
}
}
}
void ttn(int *a, int b)
{
ntt(a, b);
int inv = fst(b, md - 2);
for (int i = 0; i < b; ++i)
a[i] = (long)a[i] * inv % md;
for (int i = 1, j = b - 1; i < j; ++i, --j)
swap(a[i], a[j]);
}
詳細信息
answer.code: In function ‘int main()’: answer.code:5:14: error: ‘__int64’ was not declared in this scope; did you mean ‘__int64_t’? 5 | #define long __int64 | ^~~~~~~ answer.code:29:26: note: in expansion of macro ‘long’ 29 | fx[i] = (long)fx[i] * gx[i] % md; | ^~~~ answer.code: In function ‘int fst(int, int)’: answer.code:5:14: error: ‘__int64’ was not declared in this scope; did you mean ‘__int64_t’? 5 | #define long __int64 | ^~~~~~~ answer.code:55:30: note: in expansion of macro ‘long’ 55 | c = (long)c * a % md; | ^~~~ answer.code:5:14: error: ‘__int64’ was not declared in this scope; did you mean ‘__int64_t’? 5 | #define long __int64 | ^~~~~~~ answer.code:56:22: note: in expansion of macro ‘long’ 56 | a = (long)a * a % md; | ^~~~ answer.code: In function ‘void ntt(int*, int)’: answer.code:5:14: error: ‘__int64’ was not declared in this scope; did you mean ‘__int64_t’? 5 | #define long __int64 | ^~~~~~~ answer.code:76:40: note: in expansion of macro ‘long’ 76 | tmp = (long)now * a[j | k | i] % md; | ^~~~ answer.code: In function ‘void ttn(int*, int)’: answer.code:5:14: error: ‘__int64’ was not declared in this scope; did you mean ‘__int64_t’? 5 | #define long __int64 | ^~~~~~~ answer.code:90:25: note: in expansion of macro ‘long’ 90 | a[i] = (long)a[i] * inv % md; | ^~~~