QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340179#1810. Generate the SequencesHKOI0#AC ✓130ms104952kbC++202.1kb2024-02-28 17:37:262024-02-28 17:37:27

Judging History

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

  • [2024-02-28 17:37:27]
  • 评测
  • 测评结果:AC
  • 用时:130ms
  • 内存:104952kb
  • [2024-02-28 17:37:26]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;

const int N = 2e6 + 11;
const int MOD = 998244353;
int fa[N], fi[N];

int pm(int a, int b){
    if (b == 0) return 1;
    return pm(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}
int mi(int a){
    return pm(a, MOD - 2);
}

int binom(int n, int r){
    return fa[n] * fi[r] % MOD * fi[n - r] % MOD;
}

template<int MOD = 998244353>
struct Mint{
    int value;
    Mint() : value(0) {};
    Mint(int v) : value(v) { value = (value % MOD + MOD) % MOD; };
    Mint operator+ (const Mint& o) const { int res = value + o.value; return res >= MOD ? res - MOD : res; }
    void operator+= (const Mint& o) { *this = *this + o; }
    Mint operator- (const Mint& o) const { int res = value - o.value; return res < 0 ? res + MOD : res; }
    Mint operator* (const Mint& o) const { int res = value * o.value % MOD; return res; }
    Mint operator/ (const Mint& o) const { return *this * o.inv(); }
    Mint inv() const { return mi(value); }
    friend ostream& operator<< (ostream& out, const Mint& m) {
        return cout << m.value;
    }
};

using Zn = Mint<MOD>;
void solve() {
    int n,m;
    cin >> n >> m;
    vector dp(n+2,vector<Zn>(n+2));
    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += dp[i][j];
            if (i - j < j * (m - 2)) {
                dp[i + 1][j] += dp[i][j] * (Zn(j) * Zn(m - 2) - Zn(i - j));
            }
        }
    }
    Zn ans = 0;
    for(int i = 0; i <= n; i++) {
        Zn sum = 0;
        for (int j = 0; j <= i; j++) {
            sum += dp[i][j];
        }
        ans += sum * Zn(binom(n,i));
    }
    cout << ans << '\n';
}

int32_t main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    fa[0] = 1; for (int i = 1; i < N; i++) fa[i] = fa[i - 1] * i % MOD;
    fi[N - 1] = mi(fa[N - 1]); for (int i = N - 2; i >= 0; i--) fi[i] = fi[i + 1] * (i + 1) % MOD;
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 18ms
memory: 35020kb

input:

2 3

output:

5

result:

ok answer is '5'

Test #2:

score: 0
Accepted
time: 30ms
memory: 42808kb

input:

1024 52689658

output:

654836147

result:

ok answer is '654836147'

Test #3:

score: 0
Accepted
time: 7ms
memory: 35056kb

input:

1 2

output:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 19ms
memory: 35008kb

input:

1 3

output:

2

result:

ok answer is '2'

Test #5:

score: 0
Accepted
time: 13ms
memory: 35020kb

input:

1 100000000

output:

2

result:

ok answer is '2'

Test #6:

score: 0
Accepted
time: 17ms
memory: 34728kb

input:

2 2

output:

4

result:

ok answer is '4'

Test #7:

score: 0
Accepted
time: 17ms
memory: 34840kb

input:

2 4

output:

6

result:

ok answer is '6'

Test #8:

score: 0
Accepted
time: 15ms
memory: 34836kb

input:

2 5

output:

7

result:

ok answer is '7'

Test #9:

score: 0
Accepted
time: 11ms
memory: 34840kb

input:

2 100000000

output:

100000002

result:

ok answer is '100000002'

Test #10:

score: 0
Accepted
time: 15ms
memory: 34832kb

input:

3 2

output:

8

result:

ok answer is '8'

Test #11:

score: 0
Accepted
time: 15ms
memory: 34828kb

input:

3 3

output:

14

result:

ok answer is '14'

Test #12:

score: 0
Accepted
time: 19ms
memory: 34804kb

input:

3 4

output:

22

result:

ok answer is '22'

Test #13:

score: 0
Accepted
time: 19ms
memory: 34836kb

input:

3 5

output:

32

result:

ok answer is '32'

Test #14:

score: 0
Accepted
time: 15ms
memory: 34728kb

input:

3 100000000

output:

446563791

result:

ok answer is '446563791'

Test #15:

score: 0
Accepted
time: 60ms
memory: 104952kb

input:

3000 2

output:

21292722

result:

ok answer is '21292722'

Test #16:

score: 0
Accepted
time: 91ms
memory: 104952kb

input:

3000 3

output:

172222927

result:

ok answer is '172222927'

Test #17:

score: 0
Accepted
time: 130ms
memory: 104920kb

input:

3000 100000000

output:

736503947

result:

ok answer is '736503947'

Test #18:

score: 0
Accepted
time: 91ms
memory: 84480kb

input:

2522 61077387

output:

857454425

result:

ok answer is '857454425'

Test #19:

score: 0
Accepted
time: 14ms
memory: 35944kb

input:

426 7215704

output:

799491736

result:

ok answer is '799491736'

Test #20:

score: 0
Accepted
time: 27ms
memory: 38968kb

input:

772 72289915

output:

848141383

result:

ok answer is '848141383'

Test #21:

score: 0
Accepted
time: 36ms
memory: 50952kb

input:

1447 83321470

output:

160422285

result:

ok answer is '160422285'

Test #22:

score: 0
Accepted
time: 86ms
memory: 83468kb

input:

2497 64405193

output:

355300540

result:

ok answer is '355300540'

Test #23:

score: 0
Accepted
time: 26ms
memory: 39220kb

input:

775 9385367

output:

470172346

result:

ok answer is '470172346'

Test #24:

score: 0
Accepted
time: 18ms
memory: 41840kb

input:

982 72596758

output:

7144187

result:

ok answer is '7144187'

Test #25:

score: 0
Accepted
time: 16ms
memory: 35940kb

input:

417 26177178

output:

776374896

result:

ok answer is '776374896'

Test #26:

score: 0
Accepted
time: 50ms
memory: 63736kb

input:

1932 19858856

output:

285834553

result:

ok answer is '285834553'

Test #27:

score: 0
Accepted
time: 98ms
memory: 92792kb

input:

2728 23009122

output:

433516287

result:

ok answer is '433516287'

Test #28:

score: 0
Accepted
time: 55ms
memory: 61396kb

input:

1857 22578508

output:

243488639

result:

ok answer is '243488639'

Test #29:

score: 0
Accepted
time: 121ms
memory: 100988kb

input:

2918 69623276

output:

546299707

result:

ok answer is '546299707'

Test #30:

score: 0
Accepted
time: 43ms
memory: 56344kb

input:

1679 21332149

output:

217000656

result:

ok answer is '217000656'

Test #31:

score: 0
Accepted
time: 36ms
memory: 48468kb

input:

1340 6251797

output:

267221018

result:

ok answer is '267221018'

Test #32:

score: 0
Accepted
time: 24ms
memory: 40236kb

input:

868 64770398

output:

652067665

result:

ok answer is '652067665'