글 읽기 - naive dp 질문

jinhan814 3년 전 0

아래처럼 n^2 풀이를 짠 뒤에 아래 블로그의 코드를 통해서 recurrence를 찾아서 풀려고 했는데 WA가 나옵니다. 혹시 n^2 풀이에 오류가 있는 건가요??

https://min-25.hatenablog.com/...

n^2 풀이를 통해서 얻은 초항은 아래와 같습니다..

n = 3 : 1
n = 4 : 2
n = 5 : 9
n = 6 : 30
n = 7 : 106
n = 8 : 364
n = 9 : 1253
n = 10 : 4302
n = 11 : 14794
n = 12 : 50996
n = 13 : 176430
n = 14 : 613084
n = 15 : 2141120
n = 16 : 7518144
n = 17 : 26548513
n = 18 : 94293878
n = 19 : 336857590
n = 20 : 212059251
n = 21 : 379833146
n = 22 : 910099373
n = 23 : 93077906
n = 24 : 121897595
n = 25 : 408576993
n = 26 : 674016394
n = 27 : 392347125
n = 28 : 645114595
n = 29 : 497249380
n = 30 : 720559443
n = 31 : 45903958
n = 32 : 332927473
n = 33 : 791401852
n = 34 : 809783807
n = 35 : 402328421
n = 36 : 191122747
n = 37 : 204703354
n = 38 : 744422336
n = 39 : 990050622
n = 40 : 977681706
n = 41 : 763017613
n = 42 : 99836725
n = 43 : 556975496
n = 44 : 760276501
n = 45 : 98942614
n = 46 : 367743795
n = 47 : 574835618
n = 48 : 955693286
n = 49 : 985536261
n = 50 : 45051710

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

typedef long long ll;

const ll MOD = 998244353;
ll cache[200 + 1][2]; //cache[n][state] : 현재 칠할 삼각형이 state인 n각형 (단, state는 1일때 red)
ll cache2[200 + 1]; //cache2[n] : n각형을 삼각분할하는 경우의 수

//카탈란 수열 C(n)에 대해 n각형을 삼각분할하는 경우의 수는 C(n - 2)
ll f(int n) {
	ll& ret = cache2[n];
	if (ret != -1) return ret;
	if (n <= 1) return ret = 1;
	ret = 0;
	for (int i = 0; i <= n - 1; i++) ret = (ret + f(i) * f(n - 1 - i)) % MOD;
	return ret;
}

//n각형에서 P1, P2를 포함하는 삼각형을 현재 state로 칠할 때 가능한 삼각분할의 red의 개수 합을 반환
ll sol(int n, bool isRed) {
	ll& ret = cache[n][isRed];
	if (ret != -1) return ret;
	if (n < 3) return ret = 0;
	if (n == 3) return ret = isRed;
	ret = 0;
	for (int i = 2; i <= n - 1; i++) {
		int left = i;
		int right = n - i + 1;
		ret = (ret + sol(left, !isRed)) % MOD;
		ret = (ret + sol(right, !isRed)) % MOD;
		if (isRed) ret = (ret + f(left - 2) * f(right - 2)) % MOD;
	}
	return ret;
}

namespace linear_rec {
    int mod_inv(int a, int mod) {
        int b = mod, s = 1, t = 0, old_a = a;
        while (b) {
            int q = a / b;
            swap(a %= b, b);
            swap(s -= t * q, t);
        }
        if (a != 1) {
            fprintf(stderr,
                "Error: %d^{-1} mod %d does not exist.\n\n", old_a, mod);
            assert(0);
        }
        return s < 0 ? s + mod : s;
    }
    vector<int> extended(int n,
        const vector<vector<int>>& coeffs, const vector<int>& terms, int mod) {
        vector<int> ret(max<int>(n + 1, terms.size()));
        copy(terms.begin(), terms.end(), ret.begin());
        const int order = coeffs.size() - 1;
        const int deg = coeffs[0].size() - 1;
        assert((int)terms.size() >= order);
        for (int m = terms.size(); m <= n; ++m) {
            int s = 0;
            for (int i = 1; i <= order; ++i) {
                int k = m - i, t = ret[k];
                for (int d = 0; d <= deg; ++d) {
                    s = (s + ll(t) * coeffs[i][d]) % mod;
                    t = ll(t) * k % mod;
                }
            }
            int denom = 0, mpow = 1;
            for (int d = 0; d <= deg; ++d) {
                denom = (denom + ll(mpow) * coeffs[0][d]) % mod;
                mpow = ll(mpow) * m % mod;
            }
            ret[m] = ll(mod - s) * mod_inv(denom, mod) % mod;
        }
        return ret;
    }
    vector<vector<int>> find_recurrence_relation(
        const vector<int>& terms, const int deg, const int mod, bool verify = true) {
        const int n = terms.size();
        const int B = (n + 2) / (deg + 2); // number of blocks
        const int C = B * (deg + 1); // number of columns
        const int R = n - (B - 1); // number of rows
        assert(B >= 2); assert(R >= C - 1);
        auto mul = [mod](int a, int b) { return ll(a) * b % mod; };
        auto fixed = [mod](int a) { return (a %= mod) < 0 ? a + mod : a; };
        auto error = [](int order, int deg) {
            fprintf(stderr,
                "Error: Could not find a recurrence relation "
                "of order <= %d and degree <= %d.\n\n",
                order, deg);
            assert(0);
        };
        vector<vector<int>> mat(R, vector<int>(C));
        for (int y = 0; y < R; ++y) {
            for (int b = 0; b < B; ++b) {
                for (int d = 0, v = fixed(terms[y + b]); d <= deg; ++d) {
                    mat[y][b * (deg + 1) + d] = v;
                    v = mul(v, y + b);
                }
            }
        }
        int rank = 0;
        for (int x = 0; x < C; ++x) {
            int pivot = -1;
            for (int y = rank; y < R; ++y) if (mat[y][x] != 0) {
                pivot = y; break;
            }
            if (pivot < 0) break;
            if (pivot != rank) swap(mat[rank], mat[pivot]);
            int inv = mod_inv(mat[rank][x], mod);
            for (int x2 = x; x2 < C; ++x2) mat[rank][x2] = mul(mat[rank][x2], inv);
            for (int y = rank + 1; y < R; ++y) if (mat[y][x]) {
                int c = mod - mat[y][x];
                for (int x2 = x; x2 < C; ++x2) {
                    mat[y][x2] = (ll(mat[y][x2]) + ll(c) * mat[rank][x2]) % mod;
                }
            }
            ++rank;
        }
        if (rank == C) error(B - 1, deg);
        for (int y = rank - 1; y >= 0; --y) if (mat[y][rank]) {
            assert(mat[y][y] == 1);
            int c = mod - mat[y][rank];
            for (int y2 = 0; y2 < y; ++y2) {
                mat[y2][rank] = (mat[y2][rank] + ll(c) * mat[y2][y]) % mod;
            }
        }
        int order = rank / (deg + 1);
        vector<vector<int>> ret(order + 1, vector<int>(deg + 1));
        ret[0][rank % (deg + 1)] = 1;
        for (int y = rank - 1; y >= 0; --y) {
            int k = order - y / (deg + 1), d = y % (deg + 1);
            ret[k][d] = (mod - mat[y][rank]) % mod;
        }
        if (verify) {
            auto extended_terms = extended(n - 1, ret,
                vector<int>(terms.begin(), terms.begin() + order), mod);
            for (int i = 0; i < (int)terms.size(); ++i) {
                if (fixed(terms[i] - extended_terms[i]) != 0) error(B - 1, deg);
            }
        }
        return ret;
    }
    vector<int> seq(int n, const vector<int>& terms, int degree, int mod) {
        auto coeffs = find_recurrence_relation(terms, degree, mod);
        auto extended_terms = extended(n, coeffs, terms, mod);
        return extended_terms;
    }
}

int main() {
	fastio;
	memset(cache, -1, sizeof(cache));
	memset(cache2, -1, sizeof(cache2));
	vector<int> v;
    for (int i = 3; i <= 200; i++) v.push_back(sol(i, 1));
    int n; cin >> n;
    vector<int> ans = linear_rec::seq(n, v, 20, MOD);
    cout << ans[n - 3] << '\n';
}

leinad2 3년 전 2

네 초항이 틀리셨네요.

jinhan814 3년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

naive dp 질문

jinhan814 3년 전 0

leinad2 3년 전 2

jinhan814 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말