QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340120#4812. Counting SequencetylAC ✓1983ms943528kbC++141.4kb2024-02-28 15:29:302024-02-28 15:29:30

Judging History

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

  • [2024-02-28 15:29:30]
  • 评测
  • 测评结果：AC
  • 用时：1983ms
  • 内存：943528kb
查看
  • [2024-02-28 15:29:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10, M = 800, mod = 998244353;
int n, c;
int dp[N][M], f[N], tmp[N], ans;
int inc(const int &a, const int &b) { return (a + b >= mod ? a + b - mod : a + b); }
int mul(const int &a, const int &b) { return 1ll * a * b % mod; }
void Inc(int &a, const int &b) { a = (a + b >= mod ? a + b - mod : a + b); }
int main() {
    cin>>n>>c;
    for(int i = 1; i <= min(n, M - 1); i++) dp[i][i] = 1;
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= min(i, M - 1); j++) {
            if(j > 1) Inc(dp[i][j], dp[i - j][j - 1]);
            if(j + 1 < M) Inc(dp[i][j], mul(dp[i - j][j + 1], c));
        }
    for(int i = 1; i < M; i++) Inc(ans, dp[n][i]);
    tmp[M] = 1;
    for(int i = M; i <= n; i++) Inc(tmp[i], dp[i - M][M - 1]);
    f[0] = 1;
    for(int k = 0; k < M; k++) {
        if(k) {
            for(int j = N - 1; j >= 0; j--) {
                f[j] = mul(f[j], c);
                if(j >= k) Inc(f[j], f[j - k]);
            }
        }
        for(int i = M; i <= n; i++) {
            for(int j = i; j <= (i == M ? n : i); j++) {
                int v = i == M ? tmp[j] : 1;
                int res = n - j - i * k + k * (k + 1) / 2;
                if(res >= 2 * N || res < 0 || (res & 1)) continue;
                res >>= 1;
                Inc(ans, mul(v, f[res]));
            }
        }
    }
    
    cout<<ans<<endl;
    return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 356ms
memory: 4744kb

input:

5 3

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 351ms
memory: 4704kb

input:

1 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 365ms
memory: 11160kb

input:

2022 39

output:

273239559

result:

ok 1 number(s): "273239559"

Test #4:

score: 0
Accepted
time: 355ms
memory: 4808kb

input:

1 998244352

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 364ms
memory: 4716kb

input:

1 12345678

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 355ms
memory: 4716kb

input:

20 998998

output:

643731701

result:

ok 1 number(s): "643731701"

Test #7:

score: 0
Accepted
time: 356ms
memory: 4856kb

input:

23 123

output:

947753998

result:

ok 1 number(s): "947753998"

Test #8:

score: 0
Accepted
time: 353ms
memory: 4944kb

input:

50 5555

output:

745339864

result:

ok 1 number(s): "745339864"

Test #9:

score: 0
Accepted
time: 355ms
memory: 4900kb

input:

60 6666

output:

690992218

result:

ok 1 number(s): "690992218"

Test #10:

score: 0
Accepted
time: 359ms
memory: 5076kb

input:

100 50

output:

169678588

result:

ok 1 number(s): "169678588"

Test #11:

score: 0
Accepted
time: 350ms
memory: 6388kb

input:

500 88888

output:

216149701

result:

ok 1 number(s): "216149701"

Test #12:

score: 0
Accepted
time: 372ms
memory: 7792kb

input:

1000 213456

output:

270989457

result:

ok 1 number(s): "270989457"

Test #13:

score: 0
Accepted
time: 362ms
memory: 11052kb

input:

2000 119988

output:

756425375

result:

ok 1 number(s): "756425375"

Test #14:

score: 0
Accepted
time: 364ms
memory: 14228kb

input:

3000 998244352

output:

71841227

result:

ok 1 number(s): "71841227"

Test #15:

score: 0
Accepted
time: 364ms
memory: 14168kb

input:

3000 555555555

output:

79880116

result:

ok 1 number(s): "79880116"

Test #16:

score: 0
Accepted
time: 377ms
memory: 18356kb

input:

4321 1234

output:

949603993

result:

ok 1 number(s): "949603993"

Test #17:

score: 0
Accepted
time: 377ms
memory: 20312kb

input:

5000 0

output:

5

result:

ok 1 number(s): "5"

Test #18:

score: 0
Accepted
time: 402ms
memory: 20312kb

input:

5000 88888777

output:

833064960

result:

ok 1 number(s): "833064960"

Test #19:

score: 0
Accepted
time: 374ms
memory: 20416kb

input:

5000 35557777

output:

696388498

result:

ok 1 number(s): "696388498"

Test #20:

score: 0
Accepted
time: 400ms
memory: 36092kb

input:

10000 123456

output:

434296902

result:

ok 1 number(s): "434296902"

Test #21:

score: 0
Accepted
time: 466ms
memory: 67432kb

input:

20000 555555

output:

34806915

result:

ok 1 number(s): "34806915"

Test #22:

score: 0
Accepted
time: 508ms
memory: 98728kb

input:

30000 777888999

output:

58443551

result:

ok 1 number(s): "58443551"

Test #23:

score: 0
Accepted
time: 611ms
memory: 161304kb

input:

50000 2

output:

90102905

result:

ok 1 number(s): "90102905"

Test #24:

score: 0
Accepted
time: 694ms
memory: 223692kb

input:

70000 77998866

output:

202638568

result:

ok 1 number(s): "202638568"

Test #25:

score: 0
Accepted
time: 847ms
memory: 317676kb

input:

100000 998244352

output:

360520717

result:

ok 1 number(s): "360520717"

Test #26:

score: 0
Accepted
time: 797ms
memory: 317768kb

input:

100000 555555555

output:

613886009

result:

ok 1 number(s): "613886009"

Test #27:

score: 0
Accepted
time: 1135ms
memory: 474132kb

input:

150000 233333

output:

381065878

result:

ok 1 number(s): "381065878"

Test #28:

score: 0
Accepted
time: 1116ms
memory: 474196kb

input:

150000 20050117

output:

269891864

result:

ok 1 number(s): "269891864"

Test #29:

score: 0
Accepted
time: 1381ms
memory: 630440kb

input:

200000 114514

output:

262861613

result:

ok 1 number(s): "262861613"

Test #30:

score: 0
Accepted
time: 1344ms
memory: 630588kb

input:

200000 1919810

output:

77872388

result:

ok 1 number(s): "77872388"

Test #31:

score: 0
Accepted
time: 1859ms
memory: 943528kb

input:

300000 0

output:

12

result:

ok 1 number(s): "12"

Test #32:

score: 0
Accepted
time: 1924ms
memory: 943448kb

input:

300000 1

output:

298803948

result:

ok 1 number(s): "298803948"

Test #33:

score: 0
Accepted
time: 1870ms
memory: 943384kb

input:

300000 2

output:

106751203

result:

ok 1 number(s): "106751203"

Test #34:

score: 0
Accepted
time: 1841ms
memory: 943392kb

input:

300000 1234

output:

427045479

result:

ok 1 number(s): "427045479"

Test #35:

score: 0
Accepted
time: 1905ms
memory: 943460kb

input:

300000 2345

output:

441593553

result:

ok 1 number(s): "441593553"

Test #36:

score: 0
Accepted
time: 1974ms
memory: 943508kb

input:

300000 20041115

output:

580367993

result:

ok 1 number(s): "580367993"

Test #37:

score: 0
Accepted
time: 1836ms
memory: 943448kb

input:

300000 20050117

output:

579859619

result:

ok 1 number(s): "579859619"

Test #38:

score: 0
Accepted
time: 1887ms
memory: 943480kb

input:

300000 22223333

output:

596066085

result:

ok 1 number(s): "596066085"

Test #39:

score: 0
Accepted
time: 1823ms
memory: 943504kb

input:

300000 175846372

output:

660364393

result:

ok 1 number(s): "660364393"

Test #40:

score: 0
Accepted
time: 1930ms
memory: 943328kb

input:

299999 9999999

output:

954865020

result:

ok 1 number(s): "954865020"

Test #41:

score: 0
Accepted
time: 1959ms
memory: 943448kb

input:

299998 55556666

output:

904862432

result:

ok 1 number(s): "904862432"

Test #42:

score: 0
Accepted
time: 1266ms
memory: 601500kb

input:

190733 31756136

output:

880544587

result:

ok 1 number(s): "880544587"

Test #43:

score: 0
Accepted
time: 1317ms
memory: 625916kb

input:

198497 463488298

output:

185220207

result:

ok 1 number(s): "185220207"

Test #44:

score: 0
Accepted
time: 1983ms
memory: 943468kb

input:

299997 0

output:

16

result:

ok 1 number(s): "16"

Test #45:

score: 0
Accepted
time: 1173ms
memory: 530904kb

input:

168168 296157813

output:

798716760

result:

ok 1 number(s): "798716760"

Test #46:

score: 0
Accepted
time: 940ms
memory: 363052kb

input:

114514 1919810

output:

783513290

result:

ok 1 number(s): "783513290"
English 繁體中文 简体中文

伺服器時間: 2024-11-30 05:00:58 | 開源專案