QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100865#1810. Generate the Sequencesckiseki#AC ✓39ms30968kbC++201.8kb2023-04-28 14:55:512023-04-28 14:55:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-28 14:55:53]
  • 评测
  • 测评结果:AC
  • 用时:39ms
  • 内存:30968kb
  • [2023-04-28 14:55:51]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
using std::cerr;
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename Iter>
void orange_(const char *s, Iter L, Iter R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
#define all(v) begin(v), end(v)

using namespace std;


const int mod = 998244353;
void imadd(int &x, int y) {
    x = (x + y >= mod ? x + y - mod : x + y);
}
int mul(int64_t a, int64_t b) {
    return static_cast<int>(a * b % mod);
}

const int maxn = 3025;

int dp[maxn][maxn];
int fac[maxn], ifac[maxn], inv[maxn];
int comb(int a, int b) {
    return mul(fac[a], mul(ifac[b], ifac[a - b]));
}

int main() {
    inv[1] = 1;
    for (int i = 2; i < maxn; i++)
        inv[i] = mul(inv[mod % i], mod - mod / i);
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < maxn; i++)
        fac[i] = mul(fac[i - 1], i), ifac[i] = mul(ifac[i - 1], inv[i]);
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            imadd(dp[i + 1][j + 1], dp[i][j]);
            imadd(dp[i + 1][j], mul((1LL * j * (M - 2) - (i - j)) % mod, dp[i][j]));
        }
    }

    int ans = 0;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            imadd(ans, mul(dp[i][j], comb(N, i)));
        }
    }
    cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3432kb

input:

2 3

output:

5

result:

ok answer is '5'

Test #2:

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

input:

1024 52689658

output:

654836147

result:

ok answer is '654836147'

Test #3:

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

input:

1 2

output:

2

result:

ok answer is '2'

Test #4:

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

input:

1 3

output:

2

result:

ok answer is '2'

Test #5:

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

input:

1 100000000

output:

2

result:

ok answer is '2'

Test #6:

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

input:

2 2

output:

4

result:

ok answer is '4'

Test #7:

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

input:

2 4

output:

6

result:

ok answer is '6'

Test #8:

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

input:

2 5

output:

7

result:

ok answer is '7'

Test #9:

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

input:

2 100000000

output:

100000002

result:

ok answer is '100000002'

Test #10:

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

input:

3 2

output:

8

result:

ok answer is '8'

Test #11:

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

input:

3 3

output:

14

result:

ok answer is '14'

Test #12:

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

input:

3 4

output:

22

result:

ok answer is '22'

Test #13:

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

input:

3 5

output:

32

result:

ok answer is '32'

Test #14:

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

input:

3 100000000

output:

446563791

result:

ok answer is '446563791'

Test #15:

score: 0
Accepted
time: 20ms
memory: 30968kb

input:

3000 2

output:

21292722

result:

ok answer is '21292722'

Test #16:

score: 0
Accepted
time: 39ms
memory: 30868kb

input:

3000 3

output:

172222927

result:

ok answer is '172222927'

Test #17:

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

input:

3000 100000000

output:

736503947

result:

ok answer is '736503947'

Test #18:

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

input:

2522 61077387

output:

857454425

result:

ok answer is '857454425'

Test #19:

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

input:

426 7215704

output:

799491736

result:

ok answer is '799491736'

Test #20:

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

input:

772 72289915

output:

848141383

result:

ok answer is '848141383'

Test #21:

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

input:

1447 83321470

output:

160422285

result:

ok answer is '160422285'

Test #22:

score: 0
Accepted
time: 32ms
memory: 25020kb

input:

2497 64405193

output:

355300540

result:

ok answer is '355300540'

Test #23:

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

input:

775 9385367

output:

470172346

result:

ok answer is '470172346'

Test #24:

score: 0
Accepted
time: 6ms
memory: 9128kb

input:

982 72596758

output:

7144187

result:

ok answer is '7144187'

Test #25:

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

input:

417 26177178

output:

776374896

result:

ok answer is '776374896'

Test #26:

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

input:

1932 19858856

output:

285834553

result:

ok answer is '285834553'

Test #27:

score: 0
Accepted
time: 31ms
memory: 27756kb

input:

2728 23009122

output:

433516287

result:

ok answer is '433516287'

Test #28:

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

input:

1857 22578508

output:

243488639

result:

ok answer is '243488639'

Test #29:

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

input:

2918 69623276

output:

546299707

result:

ok answer is '546299707'

Test #30:

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

input:

1679 21332149

output:

217000656

result:

ok answer is '217000656'

Test #31:

score: 0
Accepted
time: 10ms
memory: 12352kb

input:

1340 6251797

output:

267221018

result:

ok answer is '267221018'

Test #32:

score: 0
Accepted
time: 8ms
memory: 8372kb

input:

868 64770398

output:

652067665

result:

ok answer is '652067665'