QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141691#2142. Yurik and Woodwork LessonGamal74#AC ✓4ms6760kbC++202.1kb2023-08-17 21:18:112023-08-17 21:18:14

Judging History

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

  • [2023-08-17 21:18:14]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:6760kb
  • [2023-08-17 21:18:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define yes cout << "YES" << '\n';
#define no cout << "NO" << '\n';
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
#define endl '\n'
#define PI acos(-1)
#define Ones(n) __builtin_popcount(n)
#define Onesl(n) __builtin_popcountll(n)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll MOD = 998244353;
const ll N = 2e5 + 5;
const int OO = 0x3f3f3f3f;
const ll LOO = 0x3f3f3f3f3f3f3f3f;
int dx8[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy8[] = {-1, +1, +0, +0, +1, -1, +1, -1};
int dx4[] = {+0, +0, -1, +1};
int dy4[] = {-1, +1, +0, +0};

void Fast() {
    cin.tie(nullptr), cout.tie(nullptr), cin.sync_with_stdio(false), cout.sync_with_stdio(false);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}
ll fac[N], inv[N];
ll mul(const ll &a, const ll &b){
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b){
    return (a + b + 2 * MOD) % MOD;
}

ll pw(ll b, ll p){
    if(p < 0)return 0;
    if(!p)return 1ll;
    ll ret = pw(b, p >> 1ll);
    ret = mul(ret, ret);
    if(p & 1){
        ret = mul(ret, b);
    }
    return ret;
}
void build(){
    fac[0] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = mul(fac[i - 1], i);
    }
    inv[N - 1] = pw(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; --i) {
        inv[i] = mul(inv[i + 1], i + 1);
    }
}

ll nCr(int n, int r){
    if(r > n)return 0;
    return mul(mul(fac[n], inv[n - r]), inv[r]);
}

void Solution() {
    ll n, m;
    cin >> n >> m;
    ll paths = nCr(n + m - 2, m - 1);
    paths = mul(paths, paths);
    ll bad = mul(nCr(n + m - 2, m - 2), nCr(n + m - 2, n - 2));
    ll ans = add(paths, -bad);
    cout << ans << '\n';
}

int main() {
    build();
    Fast();
    int T = 1;
//    cin >> T;
    while (T--) {
        Solution();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 6592kb

input:

2 2

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 4ms
memory: 6592kb

input:

2 4

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 1ms
memory: 6584kb

input:

100 100

output:

818380736

result:

ok 1 number(s): "818380736"

Test #4:

score: 0
Accepted
time: 0ms
memory: 6592kb

input:

1 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 4ms
memory: 6760kb

input:

1 2

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 2ms
memory: 6588kb

input:

1 3

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 4ms
memory: 6544kb

input:

1 4

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 6608kb

input:

1 5

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 4ms
memory: 6608kb

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 4ms
memory: 6760kb

input:

2 2

output:

3

result:

ok 1 number(s): "3"

Test #11:

score: 0
Accepted
time: 2ms
memory: 6496kb

input:

2 3

output:

6

result:

ok 1 number(s): "6"

Test #12:

score: 0
Accepted
time: 4ms
memory: 6592kb

input:

2 4

output:

10

result:

ok 1 number(s): "10"

Test #13:

score: 0
Accepted
time: 4ms
memory: 6584kb

input:

2 5

output:

15

result:

ok 1 number(s): "15"

Test #14:

score: 0
Accepted
time: 1ms
memory: 6544kb

input:

3 1

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 4ms
memory: 6720kb

input:

3 2

output:

6

result:

ok 1 number(s): "6"

Test #16:

score: 0
Accepted
time: 4ms
memory: 6500kb

input:

3 3

output:

20

result:

ok 1 number(s): "20"

Test #17:

score: 0
Accepted
time: 2ms
memory: 6608kb

input:

3 4

output:

50

result:

ok 1 number(s): "50"

Test #18:

score: 0
Accepted
time: 2ms
memory: 6760kb

input:

3 5

output:

105

result:

ok 1 number(s): "105"

Test #19:

score: 0
Accepted
time: 1ms
memory: 6600kb

input:

4 1

output:

1

result:

ok 1 number(s): "1"

Test #20:

score: 0
Accepted
time: 4ms
memory: 6552kb

input:

4 2

output:

10

result:

ok 1 number(s): "10"

Test #21:

score: 0
Accepted
time: 4ms
memory: 6708kb

input:

4 3

output:

50

result:

ok 1 number(s): "50"

Test #22:

score: 0
Accepted
time: 4ms
memory: 6724kb

input:

4 4

output:

175

result:

ok 1 number(s): "175"

Test #23:

score: 0
Accepted
time: 1ms
memory: 6756kb

input:

4 5

output:

490

result:

ok 1 number(s): "490"

Test #24:

score: 0
Accepted
time: 4ms
memory: 6584kb

input:

5 1

output:

1

result:

ok 1 number(s): "1"

Test #25:

score: 0
Accepted
time: 4ms
memory: 6756kb

input:

5 2

output:

15

result:

ok 1 number(s): "15"

Test #26:

score: 0
Accepted
time: 4ms
memory: 6536kb

input:

5 3

output:

105

result:

ok 1 number(s): "105"

Test #27:

score: 0
Accepted
time: 4ms
memory: 6604kb

input:

5 4

output:

490

result:

ok 1 number(s): "490"

Test #28:

score: 0
Accepted
time: 4ms
memory: 6500kb

input:

5 5

output:

1764

result:

ok 1 number(s): "1764"

Test #29:

score: 0
Accepted
time: 0ms
memory: 6540kb

input:

1 9

output:

1

result:

ok 1 number(s): "1"

Test #30:

score: 0
Accepted
time: 4ms
memory: 6540kb

input:

8 4

output:

4950

result:

ok 1 number(s): "4950"

Test #31:

score: 0
Accepted
time: 4ms
memory: 6588kb

input:

2 48

output:

1176

result:

ok 1 number(s): "1176"

Test #32:

score: 0
Accepted
time: 1ms
memory: 6452kb

input:

57 4

output:

278114495

result:

ok 1 number(s): "278114495"

Test #33:

score: 0
Accepted
time: 4ms
memory: 6500kb

input:

82 51

output:

501711451

result:

ok 1 number(s): "501711451"

Test #34:

score: 0
Accepted
time: 1ms
memory: 6592kb

input:

4909 1

output:

1

result:

ok 1 number(s): "1"

Test #35:

score: 0
Accepted
time: 4ms
memory: 6592kb

input:

30 3890

output:

146479684

result:

ok 1 number(s): "146479684"

Test #36:

score: 0
Accepted
time: 1ms
memory: 6588kb

input:

2081 3619

output:

991511011

result:

ok 1 number(s): "991511011"

Test #37:

score: 0
Accepted
time: 4ms
memory: 6504kb

input:

9511 10

output:

282597455

result:

ok 1 number(s): "282597455"

Test #38:

score: 0
Accepted
time: 4ms
memory: 6588kb

input:

21 36014

output:

305749705

result:

ok 1 number(s): "305749705"

Test #39:

score: 0
Accepted
time: 2ms
memory: 6604kb

input:

10049 6765

output:

275321949

result:

ok 1 number(s): "275321949"

Test #40:

score: 0
Accepted
time: 1ms
memory: 6704kb

input:

13036 23902

output:

885509275

result:

ok 1 number(s): "885509275"

Test #41:

score: 0
Accepted
time: 4ms
memory: 6656kb

input:

1 100000

output:

1

result:

ok 1 number(s): "1"

Test #42:

score: 0
Accepted
time: 4ms
memory: 6496kb

input:

100000 1

output:

1

result:

ok 1 number(s): "1"

Test #43:

score: 0
Accepted
time: 1ms
memory: 6752kb

input:

98765 95678

output:

302812642

result:

ok 1 number(s): "302812642"

Test #44:

score: 0
Accepted
time: 2ms
memory: 6588kb

input:

100000 100000

output:

174524777

result:

ok 1 number(s): "174524777"