QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#17038#2142. Yurik and Woodwork Lesson123456#AC ✓31ms14952kbC++202.6kb2021-12-31 19:12:322022-05-04 12:51:08

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 12:51:08]
  • 评测
  • 测评结果:AC
  • 用时:31ms
  • 内存:14952kb
  • [2021-12-31 19:12:32]
  • 提交

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"