結果
問題 | No.2932 えっえっ嘘嘘嘘待って待って待って???えマジで?ほんとに?マジでやばすぎなんだけど?えっおっほんとにこんなにDPしちゃっていいんですかい???マジでやばすぎなんだけど??? |
ユーザー | dadas |
提出日時 | 2024-10-12 15:34:42 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,396 bytes |
コンパイル時間 | 2,181 ms |
コンパイル使用メモリ | 202,100 KB |
実行使用メモリ | 66,048 KB |
最終ジャッジ日時 | 2024-10-12 15:34:47 |
合計ジャッジ時間 | 3,476 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
65,844 KB |
testcase_01 | AC | 51 ms
65,792 KB |
testcase_02 | WA | - |
testcase_03 | AC | 52 ms
65,948 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 51 ms
65,920 KB |
testcase_09 | AC | 51 ms
65,664 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 52 ms
65,920 KB |
testcase_14 | AC | 49 ms
65,792 KB |
ソースコード
#include <bits/stdc++.h>// #include <ext/pb_ds/assoc_container.hpp>// #include <ext/pb_ds/tree_policy.hpp>// using namespace __gnu_pbds;// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>using namespace std;void _main();int main() {cin.tie(0);ios::sync_with_stdio(false);_main();return 0;}using ll = long long;using ull = unsigned long long;using ld = long double;using vi = std::vector<int>;using vvi = std::vector<vi>;using vl = std::vector<ll>;using vii = std::vector<pair<int, int> >;using vvl = std::vector<vl>;using vll = std::vector<pair<ll , ll> >;using vd = std::vector<double>;using vvd = std::vector<vd>;using vs = std::vector<std::string>;using vvs = std::vector<vs>;using vb = std::vector<bool>;using vvb = std::vector<vb>;using vc = std::vector<char>;using vvc = std::vector<vc>;using pii = std::pair<int, int>;using pll = std::pair<ll, ll>;using piil = std::pair<pair<int, int>, ll>;using mii = std::map<int, int>;using mll = std::map<ll, ll>;using pql = std::priority_queue<ll>;using pqi = std::priority_queue<int>;using pqiil = std::priority_queue<pair<pair<int, int>, ll> >;using pqii = std::priority_queue<pair<int, int> >;#define pb push_back#define ps push#define eb emplace_back#define is insert#define er erase#define f first#define s second#define lb lower_bound#define ub upper_bound#define sf(i) sizeof(i)#define endl "\n"#define sz(v) ((int)(v).size())#define all(v) (v).begin(), (v).end()#define rep(i, L, R) for(ll i = L;i<=R;i++)#define pcis precisiontemplate<typename T>struct infinity {static constexpr T max=std::numeric_limits<T>::max();static constexpr T min=std::numeric_limits<T>::min();static constexpr T value=std::numeric_limits<T>::max()/2;static constexpr T mvalue=std::numeric_limits<T>::min()/2;};template<typename T>constexpr T INF=infinity<T>::value;constexpr ll lINF=INF<ll>;constexpr int iINF = INF<int>;constexpr ld PI = 3.1415926535897932384626;ll frac[4000001], inv[4000001];const ll MD =998244353;const ll MOD =998244353;ll fpow(ll x, ll y, ll mod) {if (!y) return 1%mod;x %= mod;ll ret = 1;while(y > 0) {if(y%2 == 1) ret = (ret*x)%mod;x = (x*x)%mod;y /= 2;}return ret;}void initComb() {frac[0] = 1;inv[0] = 1;for (int i = 1; i <= 4000000; i++) {frac[i] = (frac[i - 1] * i) % MD;}inv[4000000] = fpow(frac[4000000], MD - 2, MD);for (int i = 4000000; i > 0; i--) {inv[i - 1] = (inv[i] * i) % MD;}}ll C(ll n, ll k) {if (n < k)return 0;return ((frac[n] * inv[k]) % MD * inv[n - k]) % MD;}void _main() {ll N, M;cin >>N>>M;ll K;cin >> K;initComb();// 아래 N-1번, 오른쪽 M-1 중 아래 N-1번 경우수//ll TMP = fpow(K, N*M - (N+M-1), MOD)*C(N+M-2,N-1);TMP %= MOD;// C(K, N+M-1)를 구해야함// K가 존나 큰게 문제임// MOD도 너무 크네// MOD만 살짝 작으면 해볼만한데 하// MOD로 나눴을때 0이 되는 경우를 확인?// 아 이거 그건가 윌슨인가..? 아니 아닌데 ;;// K!/[(N+M-1)! * (K-M-N+1)!]for (ll i = 1; i<=N+M-1; i++) {TMP *= i;TMP %= MOD;}for (ll i = K-M-N+2; i<=K; i++) {TMP *= fpow(i, MOD-2 ,MOD);TMP %= MOD;}cout << TMP<< endl;}