oj.uz

Submission #956055

# Submission time Handle Problem Language Result Execution time Memory
956055 2024-03-31T23:57:18 Z frodakcin Festivals in JOI Kingdom 2 (JOI23_festival2) C++17
100 / 100
 3945 ms 1996 KB 
#include <iostream>
#include <vector>
#include <cassert>
using ll = long long;

int MOD = 998244353;

#ifdef LOCAL
template<typename T>
struct vector: std::vector<T> {
	template<typename... V> vector(V&&... args): std::vector<T>(std::forward<V>(args)...) {}
	T& operator [](size_t idx) {return vector::at(idx);}
	T const& operator[](size_t idx) const {return vector::at(idx);}
};
#else
using std::vector;
#endif
using std::pair, std::cin, std::cout;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) std::begin(x), std::end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}

struct mint {
	int v;
	explicit operator int() {return v;}
	mint(): v(0) {}
	mint(int z) {
		if(z < -MOD || MOD <= z) z %= MOD;
		if (z < 0) z += MOD;
		v = z;
	}
	mint(ll z) {
		z %= MOD;
		if (z < 0) z += MOD;
		v = z;
	}
	friend mint invert(mint a) {
		ll x, y, g = euclid(a.v, MOD, x, y);
		assert(g == 1); return mint(x);
	}
	mint& operator+= (mint const& o) {if((v+=o.v)>=MOD) v-=MOD; return *this;}
	mint& operator-= (mint const& o) {if((v-=o.v)<0) v+=MOD; return *this;}
	mint& operator*= (mint const& o) {v=(ll)v*o.v%MOD; return *this;}
	mint& operator/= (mint const& o) {return *this *= invert(o);}

	friend mint operator+ (mint a, mint const& b) {return a+=b;}
	friend mint operator- (mint a, mint const& b) {return a-=b;}
	friend mint operator* (mint a, mint const& b) {return a*=b;}
	friend mint operator/ (mint const& a, mint const& b) {return a*invert(b);}
};

vector<mint> multiply(vector<mint> &&a, vector<mint> &&b) {
	assert(a.size() >= 1);
	assert(b.size() >= 1);

	if(std::min(a.size(), b.size()) <= 16) {
		vector<mint> ans(a.size() + b.size() - 1);
		for(int i = 0;i < a.size(); ++i)
			for(int j = 0;j < b.size(); ++j)
				ans[i + j] += a[i] * b[j];
		return ans;
	}
	else {
		size_t fin_sz = a.size() + b.size() - 1;
		if(a.size() < b.size()) a.resize(b.size());
		if(b.size() < a.size()) b.resize(a.size());

		// ((aH << m) + aL) * ((bH << m) + bL)
		// = (aH * bH << m + m) + (aL * bL) + ((aH * bL << m) + (aL * bH << m))

		// (aH * bL + aL * bH) = (aH + aL) * (bH + bL) - aH * bH - aL * bL;

		int m = (a.size() + 1) / 2; // LOW size >= HI size

		vector<mint> H = multiply({m+all(a)}, {m+all(b)});
		vector<mint> L = multiply({a.begin(), a.begin() + m}, {b.begin(), b.begin() + m});

		for(int i = 0;i + m < a.size(); ++i) a[i] += a[i+m], b[i] += b[i+m];
		a.resize(m);
		b.resize(m);

		vector<mint> M = multiply(std::move(a), std::move(b));
		assert(M.size() == L.size());
		for(int i = 0;i < M.size(); ++i)
		{
			M[i] -= L[i];
			if(i < H.size()) M[i] -= H[i];
		}

		vector<mint> ans = std::move(L);
		ans.resize(fin_sz);
		for(int i = 0;i < M.size() && i + m < fin_sz; ++i) ans[i+m] += M[i];
		for(int i = 0;i < H.size() && i + 2*m < fin_sz; ++i) ans[i+2*m] += H[i];
		return ans;
	}
}

int const maxn = 2e4 + 10;
mint fac[2*maxn],invfac[2*maxn];

int main(){
	int N;
	cin.tie(0);cin.sync_with_stdio(0);
	cin >> N >> MOD;
	fac[0] = mint(1);invfac[0] = mint(1);
	for(int i=1; i<2*maxn; i++){
		fac[i] = (fac[i-1] * mint(i));
		invfac[i] = mint(1) / fac[i];
	}

	vector<mint> dp(N + 1);
	vector<mint> sum_dp(N + 1);

	dp[0] = mint(1);
	sum_dp[0] = mint(1);

	auto induce = [&](int l, int m, int r) {
		auto apply = [&](vector<mint>& ans, auto &&dep_i, auto &&dep_j, auto &&dep_i_j) {
			// ans[i] += fj(j) * fij(i+j)
			// => ans[K+i-1] += fj(K-j-1) * fij(i+j)
			// => ans[K+i-1 - (off)] += fj(K-j-1) * fij(i+j - off)

			int K = m;
			int off = l + m;

			vector<mint> f1(K - l);
			for(int j = l;j < m; ++j) f1[K - j - 1] = dep_j(j);
			vector<mint> f2;
			for(int ij = l + m;ij <= r + m - 2; ++ij) f2.push_back(dep_i_j(ij));

			vector<mint> res = multiply(std::move(f1), std::move(f2));

			for(int i = m;i < r; ++i)
				ans[i] += res[i + K - 1 - (off)] * dep_i(i);
		};

		apply(dp,
				[&](int i){return mint(1);},
				[&](int j){return dp[j]*invfac[2*j];},
				[&](int ij){return fac[ij-1];});

		apply(sum_dp,
				[&](int i){return mint(i);},
				[&](int j){return dp[j]*invfac[2*j];},
				[&](int ij){return fac[ij-1];});
		apply(sum_dp,
				[&](int i){return mint(1);},
				[&](int j){return dp[j]*invfac[2*j]*mint(-j);},
				[&](int ij){return fac[ij-1];});

		apply(dp,
				[&](int i){return mint(i);},
				[&](int j){return sum_dp[j]*invfac[2*j+1];},
				[&](int ij){return fac[ij-1];});
		apply(dp,
				[&](int i){return mint(1);},
				[&](int j){return sum_dp[j]*invfac[2*j+1]*mint(-j-1);},
				[&](int ij){return fac[ij-1];});

		apply(sum_dp,
				[&](int i){return mint(i) * mint(i) - mint(i);},
				[&](int j){return sum_dp[j]*invfac[2*j+1];},
				[&](int ij){return fac[ij-1];});
		apply(sum_dp,
				[&](int i){return mint(1);},
				[&](int j){return sum_dp[j]*invfac[2*j+1] * (mint(j) * mint(j) + mint(j));},
				[&](int ij){return fac[ij-1];});
		apply(sum_dp,
				[&](int i){return mint(-2*i);},
				[&](int j){return sum_dp[j]*invfac[2*j+1]*mint(j);},
				[&](int ij){return fac[ij-1];});
	};

	auto solve = [&](auto const& solve, int l, int r) ->void{
		if(l + 1 == r) return;
		int m = l + (r - l) / 2;
		solve(solve, l, m);
		induce(l, m, r);
		solve(solve, m, r);
	};
	solve(solve, 0, N + 1);

	mint default_ans(1);
	for(int i = N * 2 - 1;i >= 1; i -= 2)
		default_ans *= mint(i);
	
#ifdef LOCAL
	for(int i = 0;i <= N; ++i)
		printf("%d -- %d\n", dp[i], sum_dp[i]);
#endif
	printf("%d\n", (int)(default_ans - dp[N]));
	return 0;
}

Compilation message

festival2.cpp: In function 'std::vector<mint> multiply(std::vector<mint>&&, std::vector<mint>&&)':
festival2.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int i = 0;i < a.size(); ++i)
      |                 ~~^~~~~~~~~~
festival2.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int j = 0;j < b.size(); ++j)
      |                  ~~^~~~~~~~~~
festival2.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i = 0;i + m < a.size(); ++i) a[i] += a[i+m], b[i] += b[i+m];
      |                 ~~~~~~^~~~~~~~~~
festival2.cpp:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int i = 0;i < M.size(); ++i)
      |                 ~~^~~~~~~~~~
festival2.cpp:97:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    if(i < H.size()) M[i] -= H[i];
      |       ~~^~~~~~~~~~
festival2.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int i = 0;i < M.size() && i + m < fin_sz; ++i) ans[i+m] += M[i];
      |                 ~~^~~~~~~~~~
festival2.cpp:102:39: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int i = 0;i < M.size() && i + m < fin_sz; ++i) ans[i+m] += M[i];
      |                                 ~~~~~~^~~~~~~~
festival2.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int i = 0;i < H.size() && i + 2*m < fin_sz; ++i) ans[i+2*m] += H[i];
      |                 ~~^~~~~~~~~~
festival2.cpp:103:41: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int i = 0;i < H.size() && i + 2*m < fin_sz; ++i) ans[i+2*m] += H[i];
      |                                 ~~~~~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 772 KB Output is correct
3 Correct 5 ms 772 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 772 KB Output is correct
3 Correct 5 ms 772 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 772 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 6 ms 772 KB Output is correct
13 Correct 5 ms 600 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 772 KB Output is correct
3 Correct 5 ms 772 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 772 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 6 ms 772 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 5 ms 600 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 772 KB Output is correct
18 Correct 5 ms 600 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 772 KB Output is correct
3 Correct 5 ms 772 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 772 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 6 ms 772 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 5 ms 600 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 772 KB Output is correct
18 Correct 5 ms 600 KB Output is correct
19 Correct 10 ms 604 KB Output is correct
20 Correct 9 ms 768 KB Output is correct
21 Correct 9 ms 600 KB Output is correct
22 Correct 6 ms 600 KB Output is correct
23 Correct 6 ms 604 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 772 KB Output is correct
3 Correct 5 ms 772 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 772 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 6 ms 772 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 5 ms 600 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 772 KB Output is correct
18 Correct 5 ms 600 KB Output is correct
19 Correct 10 ms 604 KB Output is correct
20 Correct 9 ms 768 KB Output is correct
21 Correct 9 ms 600 KB Output is correct
22 Correct 6 ms 600 KB Output is correct
23 Correct 6 ms 604 KB Output is correct
24 Correct 198 ms 852 KB Output is correct
25 Correct 197 ms 860 KB Output is correct
26 Correct 198 ms 1104 KB Output is correct
27 Correct 10 ms 604 KB Output is correct
28 Correct 51 ms 808 KB Output is correct
29 Correct 43 ms 604 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 772 KB Output is correct
3 Correct 5 ms 772 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 772 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 6 ms 772 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 5 ms 600 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 772 KB Output is correct
18 Correct 5 ms 600 KB Output is correct
19 Correct 10 ms 604 KB Output is correct
20 Correct 9 ms 768 KB Output is correct
21 Correct 9 ms 600 KB Output is correct
22 Correct 6 ms 600 KB Output is correct
23 Correct 6 ms 604 KB Output is correct
24 Correct 198 ms 852 KB Output is correct
25 Correct 197 ms 860 KB Output is correct
26 Correct 198 ms 1104 KB Output is correct
27 Correct 10 ms 604 KB Output is correct
28 Correct 51 ms 808 KB Output is correct
29 Correct 43 ms 604 KB Output is correct
30 Correct 3852 ms 1996 KB Output is correct
31 Correct 3945 ms 1744 KB Output is correct
32 Correct 3894 ms 1752 KB Output is correct
33 Correct 2393 ms 1400 KB Output is correct
34 Correct 597 ms 1040 KB Output is correct
35 Correct 509 ms 968 KB Output is correct