QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#374549#8316. Random PermutationPetroTarnavskyi#Compile Error//C++201.4kb2024-04-02 15:04:072024-04-02 15:04:08

Judging History

你现在查看的是最新测评结果

  • [2024-04-02 15:04:08]
  • 评测
  • [2024-04-02 15:04:07]
  • 提交

answer

const int mod = 998244353;

int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
	return (LL)a * b % mod;
}
int binpow(int a, int n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

const int LEN = 1 << 23;
const int GEN = 31;
const int IGEN = binpow(GEN, mod - 2);

void fft(VI& a, bool inv)
{
	int lg = __builtin_ctz(SZ(a));
	FOR(i, 0, SZ(a))
	{
		int k = 0;
		FOR(j, 0, lg)
			k |= ((i >> j) & 1) << (lg - j - 1);
		if (i < k)
			swap(a[i], a[k]);
	}
	for (int len = 2; len <= SZ(a); len += 2)
	{
		int ml = binpow(inv ? IGEN : GEN, LEN / len);
		for (int i = 0; i < SZ(a); i += len)
		{
			int pw = 1;
			FOR(j, 0, len / 2)
			{
				int v = a[i + j];
				int u = mult(a[i + j + len / 2], pw);
				a[i + j] = add(v, u);
				a[i + j + len / 2] = sub(v, u);
				pw = mult(pw, ml);
			}
		}
	}
	if (inv)
	{
		int m = binpow(SZ(a), mod - 2);
		FOR(i, 0, SZ(a))
			a[i] = mult(a[i], m);
	}
}

VI mult(VI a, VI b)
{
	int sz = 0;
	int sum = SZ(a) + SZ(b) - 1;
	while ((1 << sz) < sum)
		sz++;
	a.resize(1 << sz);
	b.resize(1 << sz);
	fft(a, false);
	fft(b, false);
	FOR(i, 0, SZ(a))
		a[i] = mult(a[i], b[i]);
	fft(a, true);
	a.resize(sum);
	return a;
}

详细

answer.code: In function ‘int mult(int, int)’:
answer.code:13:17: error: ‘LL’ was not declared in this scope
   13 |         return (LL)a * b % mod;
      |                 ^~
answer.code:13:20: error: expected ‘;’ before ‘a’
   13 |         return (LL)a * b % mod;
      |                    ^
      |                    ;
answer.code: At global scope:
answer.code:32:6: error: variable or field ‘fft’ declared void
   32 | void fft(VI& a, bool inv)
      |      ^~~
answer.code:32:10: error: ‘VI’ was not declared in this scope
   32 | void fft(VI& a, bool inv)
      |          ^~
answer.code:32:14: error: ‘a’ was not declared in this scope
   32 | void fft(VI& a, bool inv)
      |              ^
answer.code:32:17: error: expected primary-expression before ‘bool’
   32 | void fft(VI& a, bool inv)
      |                 ^~~~
answer.code:67:1: error: ‘VI’ does not name a type
   67 | VI mult(VI a, VI b)
      | ^~