Submission #952717

#	Time	Username	Problem	Language	Result	Execution time	Memory
952717		jacobtpl	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	87 / 100	9069 ms	1508 KiB

festival2

#include <iostream>
#include <vector>
#include <cassert>
using ll = long long;

int MOD = 998244353;

bool ckmax(auto &a, auto const& b) {return b>a?a=b,1:0;}
bool ckmin(auto &a, auto const& b) {return b<a?a=b,1:0;}

#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(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);}

	friend mint pow(mint a, auto b) {
		mint r(1);
		for(;b;b>>=1, a*=a)
			if(b&1)
				r *= a;
		return r;
	}
};

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);

	for(int i = 1;i <= N; ++i)
	{
		vector<mint> val_at(i + 1);
		for(int j = 1;j <= i; ++j)
		{
			if(j >= 2) {
				int ext = j - 2;
				int nxt_i = i - 2 - ext;
				if(nxt_i >= 0 && i * 2 - (j + 1)  >= 0 && i * 2 - (j + 1) - ext >= 0)
					val_at[j] += mint(j-1) * fac[i * 2 - (j + 1)] * invfac[i * 2 - (j + 1) - ext] * sum_dp[nxt_i];
			}
			int mid = j - 1;
			if(i - mid >= 0 && (i * 2 - (j + 1) - mid) >= 0)
				val_at[j] += dp[i - 1 - mid] * fac[i * 2 - (j + 1)] * invfac[i * 2 - (j + 1) - mid];
		}
		for(int j = sz(val_at) - 2;j >= 0;--j)
			val_at[j] += val_at[j+1];

		dp[i] = val_at[1];
		for(int j = 1;j < sz(val_at); j++)
			sum_dp[i] += val_at[j];
	}

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

Compilation message (stderr)

festival2.cpp:8:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool ckmax(auto &a, auto const& b) {return b>a?a=b,1:0;}
      |            ^~~~
festival2.cpp:8:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool ckmax(auto &a, auto const& b) {return b>a?a=b,1:0;}
      |                     ^~~~
festival2.cpp:9:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    9 | bool ckmin(auto &a, auto const& b) {return b<a?a=b,1:0;}
      |            ^~~~
festival2.cpp:9:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    9 | bool ckmin(auto &a, auto const& b) {return b<a?a=b,1:0;}
      |                     ^~~~
festival2.cpp:59:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   59 |  friend mint pow(mint a, auto b) {
      |                          ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 27 / 27
• Subtask 4: 14 / 14
• Subtask 5: 36 / 36
• Subtask 6: 0 / 13