QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#506302#9106. Zayin and DirichletWorldFinalEscapedCompile Error//C++144.5kb2024-08-05 16:34:042024-08-05 16:34:04

Judging History

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

  • [2024-08-05 16:34:04]
  • 评测
  • [2024-08-05 16:34:04]
  • 提交

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("");
    }
}

详细

answer.code: In function ‘int main()’:
answer.code:97:20: error: missing template arguments before ‘(’ token
   97 |         dp = vector(m + 2, vector(c + 1, vector<int> (n + 1, 0)));
      |                    ^
answer.code:97:34: error: missing template arguments before ‘(’ token
   97 |         dp = vector(m + 2, vector(c + 1, vector<int> (n + 1, 0)));
      |                                  ^
answer.code:159:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wformat=]
  159 |         printf("%d\n", ans.size() - 1);
      |                 ~^     ~~~~~~~~~~~~~~
      |                  |                |
      |                  int              std::vector<int>::size_type {aka long unsigned int}
      |                 %ld