Submission #4343029
Source Code Expand
#include<stdio.h> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<string.h> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(...) fprintf(stderr, __VA_ARGS__) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) { for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); } putchar('\n'); } template<unsigned MOD> struct ModInt { static const unsigned static_MOD = MOD; unsigned x; void undef() { x = (unsigned)-1; } bool isnan() const { return x == (unsigned)-1; } inline int geti() const { return (int)x; } ModInt() { x = 0; } ModInt(const ModInt &y) { x = y.x; } ModInt(int y) { if (y<0 || (int)MOD<=y) y %= (int)MOD; if (y<0) y += MOD; x=y; } ModInt(unsigned y) { if (MOD<=y) x = y % MOD; else x = y; } ModInt(long long y) { if (y<0 || MOD<=y) y %= MOD; if (y<0) y += MOD; x=y; } ModInt(unsigned long long y) { if (MOD<=y) x = y % MOD; else x = y; } ModInt &operator+=(const ModInt y) { if ((x += y.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(const ModInt y) { if ((x -= y.x) & (1u<<31)) x += MOD; return *this; } ModInt &operator*=(const ModInt y) { x = (unsigned long long)x * y.x % MOD; return *this; } ModInt &operator/=(const ModInt y) { x = (unsigned long long)x * y.inv().x % MOD; return *this; } ModInt operator-() const { return (x ? MOD-x: 0); } ModInt inv() const { unsigned a = MOD, b = x; int u = 0, v = 1; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if (u < 0) u += MOD; return ModInt(u); } ModInt pow(long long y) const { ModInt b = *this, r = 1; if (y < 0) { b = b.inv(); y = -y; } for (; y; y>>=1) { if (y&1) r *= b; b *= b; } return r; } friend ModInt operator+(ModInt x, const ModInt y) { return x += y; } friend ModInt operator-(ModInt x, const ModInt y) { return x -= y; } friend ModInt operator*(ModInt x, const ModInt y) { return x *= y; } friend ModInt operator/(ModInt x, const ModInt y) { return x *= y.inv(); } friend bool operator<(const ModInt x, const ModInt y) { return x.x < y.x; } friend bool operator==(const ModInt x, const ModInt y) { return x.x == y.x; } friend bool operator!=(const ModInt x, const ModInt y) { return x.x != y.x; } }; //const LL MOD = 1000000007; const LL MOD = 998244353; typedef ModInt<MOD> Mint; const int MAX = 1100000; Mint inv[MAX+1], fact[MAX+1], fact_inv[MAX+1]; void init() { inv[1] = 1; for (int i=2; i<=MAX; i++) inv[i] = inv[MOD%i] * (MOD-MOD/i); fact[0] = fact_inv[0] = 1; for (int i=1; i<=MAX; i++) { fact[i] = fact[i-1] * i; fact_inv[i] = fact_inv[i-1] * inv[i]; } } Mint nCk(int n, int k) { return fact[n] * fact_inv[k] * fact_inv[n-k]; } int N, M; Mint D(int y, int x) { if (y < 0 || x < 0) return 0; return nCk(x+y, x); } Mint solve() { Mint B = D(N, M); Mint GH = D(N, M-1), GV = D(N-1, M); Mint de = 1; Mint ans = 0; int x = M-1, y = N; int dx = 1, dy = 0; for (;;) { ans += B / de; // eprintf("%d %d %d\n", ans.geti(), GH.geti(), GV.geti()); if (dx == M && dy == N) break; if (dx == dy) { GH += D(y, x-1) * D(N-y, M-1-x); GV += D(y-1, x) * D(N-1-y, M-x); x--; dx++; } else if (dy == N) { dx++; } else { y--; dy++; GH -= D(y, x) * D(N-1-y, M-1-x); GV -= D(y, x) * D(N-1-y, M-1-x); } B += GH + GV; de += 1; } return ans; } void MAIN() { init(); scanf("%d%d", &N, &M); if (N > M) swap(N, M); Mint ans = solve(); ans /= D(N, M); printf("%d\n", ans.geti()); } int main() { int TC = 1; // scanf("%d", &TC); REP (tc, TC) MAIN(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Yes or No |
User | natsugiri |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 4266 Byte |
Status | AC |
Exec Time | 192 ms |
Memory | 13312 KB |
Compile Error
./Main.cpp: In function ‘void MAIN()’: ./Main.cpp:134:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &N, &M); ^
Judge Result
Set Name | Sample | Partial | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt |
Partial | sample_01.txt, sample_02.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_2_01.txt, subtask_2_02.txt, subtask_2_03.txt, subtask_2_04.txt, subtask_2_05.txt, subtask_2_06.txt, subtask_2_07.txt, subtask_2_08.txt, subtask_2_09.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_28.txt, subtask_2_29.txt, subtask_2_30.txt, subtask_2_31.txt, subtask_2_32.txt, subtask_2_33.txt, subtask_2_34.txt, subtask_2_35.txt, subtask_2_36.txt, subtask_2_37.txt, subtask_2_38.txt, subtask_2_39.txt, subtask_2_40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 37 ms | 13184 KB |
sample_02.txt | AC | 37 ms | 13184 KB |
sample_03.txt | AC | 37 ms | 13184 KB |
sample_04.txt | AC | 36 ms | 13184 KB |
sample_05.txt | AC | 36 ms | 13184 KB |
subtask_1_01.txt | AC | 37 ms | 13184 KB |
subtask_1_02.txt | AC | 36 ms | 13184 KB |
subtask_1_03.txt | AC | 36 ms | 13184 KB |
subtask_1_04.txt | AC | 36 ms | 13184 KB |
subtask_1_05.txt | AC | 37 ms | 13184 KB |
subtask_1_06.txt | AC | 37 ms | 13184 KB |
subtask_1_07.txt | AC | 37 ms | 13184 KB |
subtask_1_08.txt | AC | 36 ms | 13184 KB |
subtask_1_09.txt | AC | 37 ms | 13184 KB |
subtask_1_10.txt | AC | 37 ms | 13184 KB |
subtask_1_11.txt | AC | 37 ms | 13184 KB |
subtask_1_12.txt | AC | 37 ms | 13184 KB |
subtask_1_13.txt | AC | 39 ms | 13184 KB |
subtask_1_14.txt | AC | 44 ms | 13184 KB |
subtask_1_15.txt | AC | 63 ms | 13184 KB |
subtask_1_16.txt | AC | 63 ms | 13184 KB |
subtask_1_17.txt | AC | 63 ms | 13184 KB |
subtask_1_18.txt | AC | 63 ms | 13184 KB |
subtask_1_19.txt | AC | 63 ms | 13184 KB |
subtask_1_20.txt | AC | 64 ms | 13184 KB |
subtask_1_21.txt | AC | 64 ms | 13184 KB |
subtask_1_22.txt | AC | 63 ms | 13184 KB |
subtask_1_23.txt | AC | 63 ms | 13184 KB |
subtask_1_24.txt | AC | 61 ms | 13184 KB |
subtask_1_25.txt | AC | 60 ms | 13184 KB |
subtask_2_01.txt | AC | 36 ms | 13184 KB |
subtask_2_02.txt | AC | 37 ms | 13184 KB |
subtask_2_03.txt | AC | 37 ms | 13184 KB |
subtask_2_04.txt | AC | 184 ms | 13184 KB |
subtask_2_05.txt | AC | 188 ms | 13184 KB |
subtask_2_06.txt | AC | 184 ms | 13184 KB |
subtask_2_07.txt | AC | 189 ms | 13184 KB |
subtask_2_08.txt | AC | 186 ms | 13184 KB |
subtask_2_09.txt | AC | 184 ms | 13184 KB |
subtask_2_10.txt | AC | 189 ms | 13184 KB |
subtask_2_11.txt | AC | 189 ms | 13184 KB |
subtask_2_12.txt | AC | 186 ms | 13184 KB |
subtask_2_13.txt | AC | 184 ms | 13184 KB |
subtask_2_14.txt | AC | 188 ms | 13184 KB |
subtask_2_15.txt | AC | 188 ms | 13184 KB |
subtask_2_16.txt | AC | 188 ms | 13184 KB |
subtask_2_17.txt | AC | 186 ms | 13184 KB |
subtask_2_18.txt | AC | 175 ms | 13184 KB |
subtask_2_19.txt | AC | 154 ms | 13184 KB |
subtask_2_20.txt | AC | 95 ms | 13184 KB |
subtask_2_21.txt | AC | 96 ms | 13184 KB |
subtask_2_22.txt | AC | 97 ms | 13184 KB |
subtask_2_23.txt | AC | 96 ms | 13184 KB |
subtask_2_24.txt | AC | 96 ms | 13184 KB |
subtask_2_25.txt | AC | 97 ms | 13184 KB |
subtask_2_26.txt | AC | 96 ms | 13184 KB |
subtask_2_27.txt | AC | 96 ms | 13184 KB |
subtask_2_28.txt | AC | 97 ms | 13184 KB |
subtask_2_29.txt | AC | 100 ms | 13184 KB |
subtask_2_30.txt | AC | 114 ms | 13184 KB |
subtask_2_31.txt | AC | 133 ms | 13184 KB |
subtask_2_32.txt | AC | 192 ms | 13312 KB |
subtask_2_33.txt | AC | 189 ms | 13184 KB |
subtask_2_34.txt | AC | 189 ms | 13184 KB |
subtask_2_35.txt | AC | 186 ms | 13184 KB |
subtask_2_36.txt | AC | 186 ms | 13184 KB |
subtask_2_37.txt | AC | 107 ms | 13184 KB |
subtask_2_38.txt | AC | 88 ms | 13184 KB |
subtask_2_39.txt | AC | 181 ms | 13184 KB |
subtask_2_40.txt | AC | 113 ms | 13184 KB |