QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#17038 | #2142. Yurik and Woodwork Lesson | 123456# | AC ✓ | 31ms | 14952kb | C++20 | 2.6kb | 2021-12-31 19:12:32 | 2022-05-04 12:51:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double if tight TL
using str = string;
using pi = pair<int,int>;
#define mp make_pair
#define f first
#define s second
#define tcT template<class T
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pi>;
using vl = V<ll>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define pb push_back
#define ft front()
#define bk back()
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 998244353;
// const int MOD = 1e9+7;
const ll INF = 1e18;
const db PI = acos((db)-1);
mt19937 rng(0); // or mt19937_64
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
tcT, class U> T fstTrue(T lo, T hi, U f) {
++hi; assert(lo <= hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
struct mi{
int v; explicit operator int() const {return v;}
mi():v(0) {}
mi(ll _v): v(int(_v%MOD)){v+= (v<0)*MOD;}
};
mi& operator+=(mi& a, mi b){
if((a.v+=b.v) >= MOD) a.v-=MOD;
return a;
}
mi& operator-=(mi& a, mi b){
if((a.v-=b.v) < 0) a.v+=MOD;
return a;
}
mi operator+(mi a, mi b){
return a+=b;
}
mi operator-(mi a, mi b){
return a-=b;
}
mi operator*(mi a, mi b){
return mi((ll)a.v*b.v);
}
using vmi = vector<mi>;
vmi invs, fac, ifac;
void genFac(int SZ){
invs.rsz(SZ), fac.rsz(SZ), ifac.rsz(SZ);
invs[1] = fac[0] = ifac[0] = 1;
FOR(i,2,SZ) invs[i] = mi(-(ll)MOD/i*(int)invs[MOD%i]);
FOR(i,1,SZ) fac[i] = fac[i-1]*i, ifac[i] = ifac[i-1]*invs[i];
}
mi comb(int a, int b){
if(a < b || b < 0) return 0;
return fac[a]*ifac[b]*ifac[a-b];
}
mi choose2(mi a){
return a*(a-1)*invs[2];
}
mi dp[105][105];
struct Eff{
mi f(int n, int m){
return comb(n+m-2, m-1)*comb(n+m-2, n-1)-comb(n+m-2, m)*comb(n+m-2, n);
}
void solve(){
genFac(1000005);
int N, M;
cin >> N >> M;
cout << f(N, M).v << "\n";
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
Eff e; e.solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 20ms
memory: 14736kb
input:
2 2
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 28ms
memory: 14768kb
input:
2 4
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 23ms
memory: 14804kb
input:
100 100
output:
818380736
result:
ok 1 number(s): "818380736"
Test #4:
score: 0
Accepted
time: 20ms
memory: 14832kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 23ms
memory: 14816kb
input:
1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 18ms
memory: 14952kb
input:
1 3
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 23ms
memory: 14892kb
input:
1 4
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 20ms
memory: 14768kb
input:
1 5
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 27ms
memory: 14796kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 29ms
memory: 14808kb
input:
2 2
output:
3
result:
ok 1 number(s): "3"
Test #11:
score: 0
Accepted
time: 18ms
memory: 14756kb
input:
2 3
output:
6
result:
ok 1 number(s): "6"
Test #12:
score: 0
Accepted
time: 24ms
memory: 14780kb
input:
2 4
output:
10
result:
ok 1 number(s): "10"
Test #13:
score: 0
Accepted
time: 26ms
memory: 14792kb
input:
2 5
output:
15
result:
ok 1 number(s): "15"
Test #14:
score: 0
Accepted
time: 30ms
memory: 14884kb
input:
3 1
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 26ms
memory: 14744kb
input:
3 2
output:
6
result:
ok 1 number(s): "6"
Test #16:
score: 0
Accepted
time: 23ms
memory: 14884kb
input:
3 3
output:
20
result:
ok 1 number(s): "20"
Test #17:
score: 0
Accepted
time: 25ms
memory: 14880kb
input:
3 4
output:
50
result:
ok 1 number(s): "50"
Test #18:
score: 0
Accepted
time: 31ms
memory: 14816kb
input:
3 5
output:
105
result:
ok 1 number(s): "105"
Test #19:
score: 0
Accepted
time: 19ms
memory: 14736kb
input:
4 1
output:
1
result:
ok 1 number(s): "1"
Test #20:
score: 0
Accepted
time: 27ms
memory: 14792kb
input:
4 2
output:
10
result:
ok 1 number(s): "10"
Test #21:
score: 0
Accepted
time: 23ms
memory: 14872kb
input:
4 3
output:
50
result:
ok 1 number(s): "50"
Test #22:
score: 0
Accepted
time: 18ms
memory: 14884kb
input:
4 4
output:
175
result:
ok 1 number(s): "175"
Test #23:
score: 0
Accepted
time: 27ms
memory: 14680kb
input:
4 5
output:
490
result:
ok 1 number(s): "490"
Test #24:
score: 0
Accepted
time: 19ms
memory: 14796kb
input:
5 1
output:
1
result:
ok 1 number(s): "1"
Test #25:
score: 0
Accepted
time: 21ms
memory: 14756kb
input:
5 2
output:
15
result:
ok 1 number(s): "15"
Test #26:
score: 0
Accepted
time: 19ms
memory: 14876kb
input:
5 3
output:
105
result:
ok 1 number(s): "105"
Test #27:
score: 0
Accepted
time: 27ms
memory: 14840kb
input:
5 4
output:
490
result:
ok 1 number(s): "490"
Test #28:
score: 0
Accepted
time: 27ms
memory: 14800kb
input:
5 5
output:
1764
result:
ok 1 number(s): "1764"
Test #29:
score: 0
Accepted
time: 28ms
memory: 14840kb
input:
1 9
output:
1
result:
ok 1 number(s): "1"
Test #30:
score: 0
Accepted
time: 23ms
memory: 14816kb
input:
8 4
output:
4950
result:
ok 1 number(s): "4950"
Test #31:
score: 0
Accepted
time: 21ms
memory: 14836kb
input:
2 48
output:
1176
result:
ok 1 number(s): "1176"
Test #32:
score: 0
Accepted
time: 25ms
memory: 14808kb
input:
57 4
output:
278114495
result:
ok 1 number(s): "278114495"
Test #33:
score: 0
Accepted
time: 21ms
memory: 14792kb
input:
82 51
output:
501711451
result:
ok 1 number(s): "501711451"
Test #34:
score: 0
Accepted
time: 25ms
memory: 14732kb
input:
4909 1
output:
1
result:
ok 1 number(s): "1"
Test #35:
score: 0
Accepted
time: 21ms
memory: 14804kb
input:
30 3890
output:
146479684
result:
ok 1 number(s): "146479684"
Test #36:
score: 0
Accepted
time: 21ms
memory: 14836kb
input:
2081 3619
output:
991511011
result:
ok 1 number(s): "991511011"
Test #37:
score: 0
Accepted
time: 22ms
memory: 14808kb
input:
9511 10
output:
282597455
result:
ok 1 number(s): "282597455"
Test #38:
score: 0
Accepted
time: 22ms
memory: 14732kb
input:
21 36014
output:
305749705
result:
ok 1 number(s): "305749705"
Test #39:
score: 0
Accepted
time: 21ms
memory: 14736kb
input:
10049 6765
output:
275321949
result:
ok 1 number(s): "275321949"
Test #40:
score: 0
Accepted
time: 18ms
memory: 14804kb
input:
13036 23902
output:
885509275
result:
ok 1 number(s): "885509275"
Test #41:
score: 0
Accepted
time: 20ms
memory: 14736kb
input:
1 100000
output:
1
result:
ok 1 number(s): "1"
Test #42:
score: 0
Accepted
time: 25ms
memory: 14804kb
input:
100000 1
output:
1
result:
ok 1 number(s): "1"
Test #43:
score: 0
Accepted
time: 21ms
memory: 14892kb
input:
98765 95678
output:
302812642
result:
ok 1 number(s): "302812642"
Test #44:
score: 0
Accepted
time: 25ms
memory: 14796kb
input:
100000 100000
output:
174524777
result:
ok 1 number(s): "174524777"