結果
問題 | No.2245 Second Smallest |
ユーザー |
![]() |
提出日時 | 2023-01-13 22:53:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 9,140 bytes |
コンパイル時間 | 4,377 ms |
コンパイル使用メモリ | 259,500 KB |
最終ジャッジ日時 | 2025-02-10 03:03:45 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#line 1 "c.cpp"#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,n) for (int i = 0; i < int(n); ++i)#define repp(i,n,m) for (int i = m; i < int(n); ++i)#define reb(i,n) for (int i = int(n)-1; i >= 0; --i)#define all(v) v.begin(),v.end()using namespace std;using namespace atcoder;using ll = long long;using ull = unsigned long long;using ld = long double;using P = pair<int, int>;using PL = pair<long long, long long>;using pdd = pair<long double, long double>;using pil = pair<int,ll>;using pli = pair<ll,int>;template<class T>istream &operator>>(istream &is,vector<T> &v){for(auto &e:v)is>>e;return is;}template<typename T>bool range(T a,T b,T x){return (a<=x&&x<b);}template<typename T>bool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));}template<typename T>void rev(vector<T> &v){reverse(v.begin(),v.end());}void revs(string &s) {reverse(s.begin(),s.end());}template<typename T>void sor(vector<T> &v, int f=0){sort(v.begin(),v.end());if(f!=0) rev(v);}template<typename T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}template<typename T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<typename T>void uniq(vector<T> &v){sor(v);v.erase(unique(v.begin(),v.end()),v.end());}template<typename T1, typename T2>void print(pair<T1,T2> a);template<typename T>void print(vector<T> v);template<typename T>void print(vector<vector<T>> v);void print(){ putchar(' '); }void print(bool a){ printf("%d", a); }void print(int a){ printf("%d", a); }void print(long a){ printf("%ld", a); }void print(long long a){ printf("%lld", a); }void print(char a){ printf("%c", a); }void print(char a[]){ printf("%s", a); }void print(const char a[]){ printf("%s", a); }void print(long double a){ printf("%.15Lf", a); }void print(const string& a){ for(auto&& i : a) print(i); }void print(unsigned int a){ printf("%u", a); }void print(unsigned long long a) { printf("%llu", a); }template<class T> void print(const T& a){ cout << a; }int out(){ putchar('\n'); return 0; }template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }template<typename T1,typename T2>void print(pair<T1,T2> a){print(a.first);print(),print(a.second);}template<typename T>void print(vector<T> v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())print();}}template<typename T>void print(vector<vector<T>> v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())out();}}void yes(){out("Yes");}void no (){out("No");}void yn (bool t){if(t)yes();else no();}void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);}void o(){out("!?");}namespace noya2{const int INF = 1001001007;const long long mod1 = 998244353;const long long mod2 = 1000000007;const long long inf = 2e18;const long double pi = 3.14159265358979323;const long double eps = 1e-7;const vector<int> dx = {0,1,0,-1,1,1,-1,-1};const vector<int> dy = {1,0,-1,0,1,-1,-1,1};const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";const string alp = "abcdefghijklmnopqrstuvwxyz";const string NUM = "0123456789";} // namespace noya2using namespace noya2;using mint = modint998244353;//using mint = modint1000000007;//using mint = modint;void out(mint a){out(a.val());}void out(vector<mint> a){vector<ll> b(a.size()); rep(i,a.size()) b[i] = a[i].val(); out(b);}void out(vector<vector<mint>> a){for (auto v : a) out(v);}istream &operator>>(istream &is,vector<mint> &v){for(auto &e:v){ll _x;is>>_x;e=_x;}return is;}#line 2 "factrial_calculated.hpp"#line 4 "factrial_calculated.hpp"const std::vector<int> fact_par1e7_mod107 ={1 ,682498929 ,491101308 ,76479948 ,723816384 ,67347853 ,27368307 ,625544428 ,199888908 ,888050723 ,927880474 ,281863274 ,661224977 ,623534362 ,970055531 ,261384175 ,195888993 ,66404266 ,547665832 ,109838563 ,933245637 ,724691727 ,368925948 ,268838846 ,136026497 ,112390913 ,135498044 ,217544623 ,419363534 ,500780548 ,668123525 ,128487469 ,30977140 ,522049725 ,309058615 ,386027524 ,189239124 ,148528617 ,940567523 ,917084264 ,429277690 ,996164327 ,358655417 ,568392357 ,780072518 ,462639908 ,275105629 ,909210595 ,99199382 ,703397904 ,733333339 ,97830135 ,608823837 ,256141983 ,141827977 ,696628828 ,637939935 ,811575797 ,848924691 ,131772368 ,724464507 ,272814771 ,326159309 ,456152084 ,903466878 ,92255682 ,769795511 ,373745190 ,606241871 ,825871994 ,957939114 ,435887178 ,852304035 ,663307737 ,375297772 ,217598709 ,624148346 ,671734977 ,624500515 ,748510389 ,203191898 ,423951674 ,629786193 ,672850561 ,814362881 ,823845496 ,116667533 ,256473217 ,627655552 ,245795606 ,586445753 ,172114298 ,193781724 ,778983779 ,83868974 ,315103615 ,965785236 ,492741665 ,377329025 ,847549272 ,698611116 ,};const std::vector<int> fact_par1e7_mod998 ={1 ,295201906 ,160030060 ,957629942 ,545208507 ,213689172 ,760025067 ,939830261 ,506268060 ,39806322 ,808258749 ,440133909 ,686156489 ,741797144 ,390377694 ,12629586 ,544711799 ,104121967 ,495867250 ,421290700 ,117153405 ,57084755 ,202713771 ,675932866 ,79781699 ,956276337 ,652678397 ,35212756 ,655645460 ,468129309 ,761699708 ,533047427 ,287671032 ,206068022 ,50865043 ,144980423 ,111276893 ,259415897 ,444094191 ,593907889 ,573994984 ,892454686 ,566073550 ,128761001 ,888483202 ,251718753 ,548033568 ,428105027 ,742756734 ,546182474 ,62402409 ,102052166 ,826426395 ,159186619 ,926316039 ,176055335 ,51568171 ,414163604 ,604947226 ,681666415 ,511621808 ,924112080 ,265769800 ,955559118 ,763148293 ,472709375 ,19536133 ,860830935 ,290471030 ,851685235 ,242726978 ,169855231 ,612759169 ,599797734 ,961628039 ,953297493 ,62806842 ,37844313 ,909741023 ,689361523 ,887890124 ,380694152 ,669317759 ,367270918 ,806951470 ,843736533 ,377403437 ,945260111 ,786127243 ,80918046 ,875880304 ,364983542 ,623250998 ,598764068 ,804930040 ,24257676 ,214821357 ,791011898 ,954947696 ,183092975 ,};const long long mod998 = 998244353;const long long mod107 = 1000000007;const long long factpar = 10000000;long long fact998(long long n){if (n >= mod998) return 0;long long res = fact_par1e7_mod998[n/factpar];for (ll nn = n/factpar*factpar+1; nn <= n; nn++){res = (res * nn) % mod998;}return res;}long long fact107(long long n){if (n >= mod107) return 0;long long res = fact_par1e7_mod107[n/factpar];for (ll nn = n/factpar*factpar+1; nn <= n; nn++){res = (res * nn) % mod107;}return res;}#line 2 "binom.hpp"#line 4 "binom.hpp"namespace noya2{template<typename T>struct Binom{Binom(int lim = 300000){ extend(lim); }static T fact(int x) {if (x < 0) return T(0);extend(x);return kaijo[x];}static T ifact(int x){if (x < 0) return T(0);extend(x);return kainv[x];}static T C(int n, int r){if (n < 0 || n < r || r < 0) return T(0);extend(n);return kaijo[n] * kainv[r] * kainv[n-r];}static T P(int n, int r){if (n < 0 || n < r || r < 0) return T(0);extend(n);return kaijo[n] * kainv[n-r];}static T H(int n, int r){if (n < 0 || r < 0) return T(0);return (r == 0 ? T(1) : C(n+r-1,r));}T operator()(int n, int r){ return C(n,r); }template<class... Cnts> static T M(const Cnts&... cnts){return multinomial(0,T(1),cnts...);}private:static T multinomial(const int& sum, const T& div_prod){if (sum < 0) return T(0);return fact(sum) * div_prod;}template<class... Tail> static T multinomial(const int& sum, const T& div_prod, const int& n1, const Tail&... tail){if (n1 < 0) return T(0);return multinomial(sum+n1,div_prod*ifact(n1),tail...);}static std::vector<T> kaijo, kainv;static void extend(int lim){int siz = kaijo.size();if (siz > lim) return ;int nsiz = siz * 2;kaijo.resize(nsiz+1), kainv.resize(nsiz+1);for (int i = siz; i <= nsiz; i++) kaijo[i] = kaijo[i-1] * T(i);kainv[nsiz] = kaijo[nsiz].inv();for (int i = nsiz-1; i >= siz; i--) kainv[i] = kainv[i+1] * T(i+1);extend(lim);}};template<typename T>std::vector<T>Binom<T>::kaijo = vector<T>(2,T(1));template<typename T>std::vector<T>Binom<T>::kainv = vector<T>(2,T(1));} // namespace noya2#line 81 "c.cpp"void solve(){int h, w, k; cin >> h >> w >> k;if (h > w) swap(h,w);mint facthw = fact998(h*w-h);Binom<mint> bnm;mint ans = 0;for (int c = h; c >= 0; c--){ans += bnm(h,c) * bnm(w,c) * bnm.fact(c+k-1) * facthw;facthw *= (h*w-c+1);}ans *= k;ans /= fact998(h*w+k);out(ans.val());}int main(){fast_io();int t = 1; //cin >> t;while(t--) solve();}