QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129098#618. 多项式乘法Houraisan_Kaguya#Compile Error//C++141.7kb2023-07-21 21:31:532023-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]
  • 评测
  • [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;
      |                         ^~~~