結果

問題 No.1431 東大文系数学2020第2問改
ユーザー mine691mine691
提出日時 2021-03-14 13:59:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 559 ms / 5,000 ms
コード長 5,213 bytes
コンパイル時間 4,723 ms
コンパイル使用メモリ 281,192 KB
実行使用メモリ 249,832 KB
最終ジャッジ日時 2024-11-06 03:41:06
合計ジャッジ時間 14,537 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 434 ms
249,808 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 396 ms
249,636 KB
testcase_06 AC 321 ms
249,768 KB
testcase_07 AC 322 ms
249,668 KB
testcase_08 AC 332 ms
249,692 KB
testcase_09 AC 559 ms
249,668 KB
testcase_10 AC 432 ms
249,804 KB
testcase_11 AC 355 ms
249,680 KB
testcase_12 AC 457 ms
249,736 KB
testcase_13 AC 403 ms
249,664 KB
testcase_14 AC 413 ms
249,832 KB
testcase_15 AC 404 ms
249,672 KB
testcase_16 AC 393 ms
249,728 KB
testcase_17 AC 385 ms
249,696 KB
testcase_18 AC 389 ms
249,664 KB
testcase_19 AC 545 ms
249,692 KB
testcase_20 AC 389 ms
249,700 KB
testcase_21 AC 481 ms
249,668 KB
testcase_22 AC 178 ms
115,120 KB
testcase_23 AC 550 ms
249,668 KB
testcase_24 AC 522 ms
249,656 KB
testcase_25 AC 2 ms
6,816 KB
testcase_26 AC 4 ms
6,816 KB
testcase_27 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Enjoy your stay. Code by evima

#include <atcoder/convolution>
#include <atcoder/dsu>
#include <atcoder/fenwicktree>
#include <atcoder/lazysegtree>
#include <atcoder/math>
#include <atcoder/maxflow>
#include <atcoder/mincostflow>
#include <atcoder/modint>
#include <atcoder/scc>
#include <atcoder/segtree>
#include <atcoder/string>
#include <atcoder/twosat>
using namespace atcoder;
using mint = modint998244353; // modint1000000007;// modint;

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
using ll = long long;
using lll = __int128;
using vl = vector<ll>;
using vs = vector<string>;
using LOOPVAR_TYPE = ll;

#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define sz(x) ll((x).size())
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define rep1(i, n) rep2(i, 0, n)
#define rep2(i, a, b) for (LOOPVAR_TYPE i = LOOPVAR_TYPE(a); i < LOOPVAR_TYPE(b); i++)
#define rep(...)                       \
	GET_MACRO(__VA_ARGS__, rep2, rep1) \
	(__VA_ARGS__)

#define eb emplace_back
#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple

const ld EPS = 1e-9;
const ld PI = 3.14159265358979323846L;
const ll INF = 1070000000LL;
const ll MOD = 998244353LL; // 1000000007LL;

void fast_io()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
}
ll lin()
{
	ll x;
	cin >> x;
	return x;
}
string input()
{
	string s;
	cin >> s;
	return s;
}
vl vin(int n)
{
	vector<ll> v(n);
	rep(i, n) cin >> v[i];
	return v;
}
template <typename T>
bool chmin(T &a, const T &b) { return (b < a) ? (a = b, true) : false; }
template <typename T>
bool chmax(T &a, const T &b) { return (a < b) ? (a = b, true) : false; }
template <typename T>
map<T, ll> freq(const vector<T> &v)
{
	map<T, ll> ret;
	for (T x : v)
		++ret[x];
	return ret;
}
template <typename T>
vector<T> reversed(vector<T> v)
{
	reverse(all(v));
	return v;
}
template <typename T>
vector<T> sorted(vector<T> v)
{
	sort(all(v));
	return v;
}
template <typename T>
vector<T> sub(const vector<T> &v, int from, int to)
{
	vector<T> ret;
	copy(&v[from], &v[to], back_inserter(ret));
	return ret;
}
template <typename T>
string str(const T &x)
{
	stringstream ss;
	ss << x;
	return ss.str();
}
template <typename Tuple, size_t... I>
array<int, sizeof...(I)> str_tuple_impl(stringstream &ss, Tuple &&t, index_sequence<I...>) { return {{(void(ss << str(get<I>(t)) << " "), 0)...}}; }
template <typename Tuple>
string str_tuple(Tuple &&t)
{
	stringstream ss;
	str_tuple_impl(ss, forward<Tuple>(t), make_index_sequence<tuple_size<decay_t<Tuple>>::value>{});
	string s = ss.str();
	if (s.size() > 0)
		s.pop_back();
	return s;
}
template <typename T, typename U>
string str(const pair<T, U> &p) { return str_tuple(p); }
template <typename... T>
string str(const tuple<T...> &t) { return str_tuple(t); }
template <typename T>
string str(const vector<T> &v)
{
	stringstream ss;
	rep(i, sz(v)) ss << v[i] << (i < sz(v) - 1 ? " " : "");
	return ss.str();
}
template <typename T>
void print1(T &&x, const string &end) { cout << str(x) << end; }
void print() { print1("", "\n"); }
template <typename T, typename... U>
void print(T &&head, U &&...tail)
{
	print1(head, " ");
	print(forward<U>(tail)...);
}
template <typename T>
void eprint1(T &&x, const string &end) { cerr << str(x) << end; }
void eprint() { eprint1("", "\n"); }
template <typename T, typename... U>
void eprint(T &&head, U &&...tail)
{
	eprint1(head, " ");
	eprint(forward<U>(tail)...);
}
template <typename... T>
void quit(T &&...x)
{
	print(forward<T>(x)...);
	exit(0);
}
template <typename T, typename U>
void yn(bool cnd, T &&yes = "Yes", U &&no = "No")
{
	if (cnd)
		print(yes);
	else
		print(no);
}
void zip(vl &v)
{
	vl w = v;
	sort(all(w));
	int n = unique(all(w)) - w.begin();
	for (ll &x : v)
		x = lower_bound(&w[0], &w[n], x) - &w[0];
}
vl zipped(vl v)
{
	zip(v);
	return v;
}
map<ll, ll> zipmap(vl v)
{
	map<ll, ll> ret;
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	rep(i, sz(v)) ret[v[i]] = i;
	return ret;
}

vector<mint> fact, ifact, inv;

void init_fact_ifact_inv(ll n)
{
	fact.resize(n + 1);
	ifact.resize(n + 1);
	inv.resize(n + 1);
	fact[0] = 1;
	rep(i, n)
	{
		fact[i + 1] = fact[i] * (i + 1);
	}
	ifact[n] = fact[n].inv();
	for (int i = n - 1; i >= 0; --i)
	{
		ifact[i] = ifact[i + 1] * (i + 1);
	}
	rep(i, n)
	{
		inv[i + 1] = fact[i] * ifact[i + 1];
	}
}

const mint ncr(ll n, ll r)
{
	return n < 0 || r < 0 || r > n ? 0 : fact[n] * ifact[r] * ifact[n - r];
}

void solveOne()
{
	ll N, M, K;
	cin >> N >> M >> K;
	assert(1 <= N and N <= 3000);
	assert(1 <= M and M <= N * N);
	assert(0 <= K and K <= 2 * N - 2);
	init_fact_ifact_inv(N * (N + 2));
	vector<vector<mint>> small(2 * N + 1, vector<mint>(2 * N + 1));
	rep(i, 2 * N + 1) rep(j, i + 1) small[i][j] = ncr(i, j);
	mint ans = 0;
	rep(i, 1, N + 1)
	{
		rep(j, i, N + 1)
		{
			if (2 * N - K - i - j < 0)
				break;
			ans += (i != j ? 2 : 1) * ((K + i + j) & 1 ? -1 : 1) * small[N][i] * small[N][j] * small[2 * N - i - j][2 * N - K - i - j] * ncr(i * j, M);
		}
	}
	print(ans.val());
}

int main()
{
	fast_io();
	cout << setprecision(20);

	int num_tc = 1;
	// cin >> num_tc;

	rep(tc, 1, num_tc + 1)
	{
		// cout << "Case #" << tc << ": " ;// << endl;
		solveOne();
	}
}
0