QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506305#9106. Zayin and DirichletWorldFinalEscapedAC ✓132ms54176kbC++204.5kb2024-08-05 16:34:162024-08-05 16:34:17

Judging History

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

  • [2024-08-05 16:34:17]
  • 评测
  • 测评结果:AC
  • 用时:132ms
  • 内存:54176kb
  • [2024-08-05 16:34:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int M = 105;
const int LIM = 100000;
const int mod = 998244353;
const int inf = 1e9;

inline int qpow(int a, int b = mod - 2) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

inline void addx(int &x, int y) {
    if ((x += y) >= mod) x -= mod;
}
inline int mul(int x, int y) { return 1ull * x * y % mod; }

int binom[LIM + M][M];
int a[N], n, m, c, d;

// dp[i][j][k]: consider id_i ~ id_m, [k^{-x}] f(p^j)
vector<vector<vector<int>>> dp;
int cnt[N];

vector<int> ans;
bool have;

void idk(int i) { // id_i
    if (cnt[i] == 0) {
        dp[i] = dp[i + 1];
    } else {
        for (int j = 0; j <= c; j++) {
            for (int k = 0; k <= n; k++) {
                for (int jj = 0; jj <= j && jj * i <= k; jj++)
                    addx(dp[i][j][k], mul(dp[i + 1][j - jj][k - jj * i], binom[cnt[i] - 1 + jj][jj]));
            }
        }
    }
}
void mu() { // mu
    for (int j = 0; j <= c; j++) {
        for (int k = 0; k <= n; k++) {
            for (int jj = 0, sgn = 1; jj <= j; jj++, sgn *= -1)
                addx(dp[0][j][k], mul(dp[1][j - jj][k], mul(sgn == 1 ? 1 : mod - 1, binom[-cnt[0]][jj])));
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> c >> d;
    for (int i = 0; i <= n; i++) cin >> a[i];
    
    if (n % c) {
        puts("-1");
        return 0;
    }

    m = n / c;
    for (int i = 0; i <= LIM + c; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i && j <= c; j++)
            binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod;
    }

    if (n == 0) {
        int ans = inf;
        // all use I
        for (int i = 0; i <= LIM; i++) {
            if (binom[i + c - 1][c] == a[0]) {
                ans = min(ans, binom[i + d - 1][d]);
            }
        }
        // all use mu
        int sgn = (c & 1 ? mod - 1 : 1);
        for (int i = 0; i <= LIM; i++) {
            if (mul(binom[i][c], sgn) == a[0]) {
                ans = min(ans, mul(binom[i][d], d & 1 ? mod - 1 : 1));
            }
        }
        if (ans != inf) printf("0\n%d\n", ans);
        else puts("-1");
        return 0;
    }

    for (int occ = 1; occ <= LIM; occ++) { // cnt[m]
        if (binom[c + occ - 1][c] != a[n]) continue;
        // printf("cnt = %d\n", occ);
        dp = vector(m + 2, vector(c + 1, vector<int> (n + 1, 0)));
        dp[m + 1][0][0] = 1;
        cnt[m] = occ, idk(m);

        // printf("predp\n");
        // for (int j = 0; j <= c; j++, puts(""))
        //     for (int k = 0; k <= n; k++)
        //         printf("%d ", dp[m][j][k]);
        
        int coef = qpow(binom[c + occ - 1 - 1][c - 1]);
        // printf("coef = %d\n", coef);
        for (int k = m - 1; k >= 1; k--) {
            int pos = m * (c - 1) + k;
            cnt[k] = 1ll * (a[pos] - dp[k + 1][c][pos] + mod) * coef % mod;
            // printf("cnt[%d] = %d\n", k, cnt[k]);
            if (cnt[k] > LIM) break;
            idk(k);
        }

        { // I or mu
            int pos = m * (c - 1);
            // printf("pos = %d, dp = %d\n", pos, dp[1][c][pos]);
            cnt[0] = 1ll * (a[pos] - dp[1][c][pos] + mod) * coef % mod;
            if (cnt[0] > LIM) cnt[0] -= mod;
            // printf("cnt[0] = %d\n", cnt[0]);
            if (cnt[0] >= 0) { // I
                if (cnt[0] <= LIM) {
                    idk(0);
                }
            } else {
                if (-cnt[0] <= LIM) {
                    mu();
                }
            }
        }

        int op = 0;
        for (int k = 0; k <= m; k++) {
            op += abs(cnt[k]);
            if (op > LIM) break;
        }
        if (op > LIM) continue;
        
        // for (int k = 0; k <= m; k++)
        //     printf("cnt[%d] = %d\n", k, cnt[k]);
        // printf("finaldp\n");
        // for (int j = 0; j <= c; j++, puts(""))
        //     for (int k = 0; k <= n; k++)
        //         printf("%d ", dp[0][j][k]);

        bool ok = 1;
        for (int k = 0; k <= n; k++) ok &= dp[0][c][k] == a[k];
        if (!ok) continue;

        if (!have || dp[0][d] < ans)
            have = 1, ans = dp[0][d];
    }

    if (!have) {
        puts("-1");
    } else {
        ans.resize(m * d + 1);
        printf("%d\n", ans.size() - 1);
        for (auto it: ans)
            printf("%d ", it);
        puts("");
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2 1
1 1 1

output:

1
1 1 

result:

ok 2 lines

Test #2:

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

input:

2 2 1
998244352 998244352 1

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

1 1 1
998244352 1

output:

1
998244352 1 

result:

ok 2 lines

Test #4:

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

input:

0 1 1
0

output:

0
0

result:

ok 2 lines

Test #5:

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

input:

0 4 1
0

output:

0
0

result:

ok 2 lines

Test #6:

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

input:

0 4 2
70

output:

0
15

result:

ok 2 lines

Test #7:

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

input:

0 5 4
998244297

output:

0
70

result:

ok 2 lines

Test #8:

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

input:

15 5 4
0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1

output:

12
0 0 0 0 1 0 1 0 1 0 1 0 1 

result:

ok 2 lines

Test #9:

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

input:

15 6 4
0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1

output:

-1

result:

ok single line: '-1'

Test #10:

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

input:

12 3 1
998244352 12 998244329 998244349 14 0 8 8 0 4 2 0 1

output:

4
998244350 4 2 0 1 

result:

ok 2 lines

Test #11:

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

input:

12 3 2
998244352 12 998244329 998244349 14 0 8 8 0 4 2 2 1

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0
Accepted
time: 132ms
memory: 49368kb

input:

1000 100 70
397336242 92739909 780072057 600841029 627493910 659101557 882669876 458983207 67031069 13413527 310825879 862928525 816773872 543497589 253744132 505049063 828998779 568174344 736294322 559341766 410905926 290290492 626151792 560829679 802493847 712006081 71952013 214789110 511143961 30...

output:

700
627257208 285548283 100330577 839600367 58036534 275511385 944723874 647706957 425578282 480923318 973823019 840620191 313954499 520834911 474712660 907187290 507361264 804539652 323329894 529585297 372831844 975644273 712274498 533586422 574594882 284290938 534494804 850217620 651057103 6374231...

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 127ms
memory: 49328kb

input:

1000 100 70
323805641 665837496 414001820 149269817 911814350 940351019 992832855 71233012 114776243 410536243 901917617 706208866 360724273 657193813 171969677 84174796 896926249 562608961 584748636 575262021 372660685 716953836 308349480 391759630 460296420 961701286 108955593 599857005 820089274 ...

output:

700
53395827 242217423 931410663 367645479 666177228 895124601 750930663 995184194 553795248 315128313 339693481 776499209 235176566 143434624 835548445 928137552 74529198 733058363 864533351 441560424 665858967 642808111 371316061 590329331 525385500 207028443 990101293 347431858 890798462 79817326...

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 108ms
memory: 49040kb

input:

996 83 66
888842388 765330198 4399494 327031092 55813003 589751376 130304204 140685350 884909667 916265091 766838922 769665291 859613776 18407573 544566241 358386282 561545233 613882077 284552765 627655961 301158809 345022252 389530833 562826424 728391553 227962236 768810930 666039656 688590136 1945...

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 3ms
memory: 52704kb

input:

1000 1 1
998244314 117 38 4 46 50 200 16 224 13 15 4 33 84 2 194 205 36 145 91 215 81 72 85 90 22 49 120 87 143 21 14 27 41 7 348 30 68 84 11 33 48 109 130 65 31 98 274 87 160 27 2 36 133 27 125 41 64 159 106 39 244 4 169 47 41 228 61 34 162 33 145 127 59 17 196 131 48 7 249 45 14 596 9 6 5 6 31 62 ...

output:

1000
998244314 117 38 4 46 50 200 16 224 13 15 4 33 84 2 194 205 36 145 91 215 81 72 85 90 22 49 120 87 143 21 14 27 41 7 348 30 68 84 11 33 48 109 130 65 31 98 274 87 160 27 2 36 133 27 125 41 64 159 106 39 244 4 169 47 41 228 61 34 162 33 145 127 59 17 196 131 48 7 249 45 14 596 9 6 5 6 31 62 5 27...

result:

ok 2 lines

Test #16:

score: 0
Accepted
time: 34ms
memory: 49056kb

input:

992 32 20
300828765 659356080 679612166 617895690 683119604 952319149 399114189 185990348 162080322 867588559 538485093 170462530 775280179 303152729 61890971 322121255 51915534 233706644 181625436 991647480 188142186 827678042 909357491 690662559 298003593 850224237 100654565 580819584 525019472 68...

output:

620
430496374 902518503 449855734 611915136 783363483 123922955 431204576 601769588 49306180 852595933 942931864 202679739 385791080 165407548 672085058 532950106 398219439 177142753 461644917 875005512 571342602 112519892 674339319 781024894 777901640 234073723 816659647 659111471 682186725 7069718...

result:

ok 2 lines

Test #17:

score: 0
Accepted
time: 37ms
memory: 48880kb

input:

990 30 17
71883948 23309701 992774089 762630173 924361188 752499250 853410921 171992256 356161591 45728890 430993017 927459941 721806069 104527814 930704562 237896419 496891384 685183239 543983517 456230473 959415081 180949923 971927545 963378838 961115000 146728207 488761612 376117998 171741098 773...

output:

561
102841658 961500703 501049465 304629572 516440666 117993810 20025158 263869931 332967514 98575847 381364327 57035416 665064055 75802784 810433488 977178560 548548957 235492415 192282113 717654089 693055852 366070238 536308310 213088519 645163514 445803951 85006207 300894858 9097082 705865287 313...

result:

ok 2 lines

Test #18:

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

input:

996 83 59
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

708
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 132ms
memory: 49272kb

input:

1000 100 98
319455718 671328746 124393862 667541501 280317271 76775371 48092239 203764029 84645105 417922386 836680977 310104170 812285448 132013070 671101034 764729245 543223038 588382653 789151736 308599709 774966467 561690267 21167599 839746652 488583454 411035025 3645695 887535097 404142810 1892...

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 25ms
memory: 49232kb

input:

996 83 66
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

792
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 2 lines

Test #21:

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

input:

1000 100 88
82742710 83000194 384570138 486333195 471971070 34486127 45897016 143913184 135955507 330649998 142921521 661631805 767463754 741636274 578460103 562076100 370857668 190664253 386032352 717085330 380359365 949353090 460517539 432187210 412223584 444473799 102081587 797719430 414793078 18...

output:

880
905517538 297056188 743459224 992406802 424140657 698777054 284527550 390433840 187622811 689095090 324180428 410416834 140760918 393982380 889761769 854358949 910057659 192974715 37907954 22323696 413758105 250585749 422544862 101783407 989283494 19377733 140339874 611307699 639279096 414396695...

result:

ok 2 lines

Test #22:

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

input:

988 26 19
801159004 191306788 873781921 344083468 931018059 489333954 296828605 200457636 553464426 87499604 462999956 79016434 139732156 602341138 101827791 185637278 111847301 396307500 479849331 162343080 23452524 707901804 682982591 363201960 513992837 777537315 589856965 506301269 71070154 6859...

output:

722
66951538 760716573 671222282 143416316 299272951 828463276 237885073 296420685 492725360 509218981 634121173 273766941 901185762 643266398 627274632 633078547 326100311 189774625 339785978 959586312 995035379 613762024 795206693 159779067 485903186 432553822 417106008 438858333 871694197 4537624...

result:

ok 2 lines