제출 #1365002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365002		po_rag526	캥거루 (CEOI16_kangaroo)	C++20	0 / 100	0 ms	344 KiB

kangaroo

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int mod = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, cs, cf;
        cin >> n >> cs >> cf;

        vector<vector<int>> dp(n + 1, vector<int>(n + 1)); // index - cc
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                        if (i == cs || i == cf) {
                                // stick
                                dp[i][j] += dp[i - 1][j];
                                dp[i][j] %= mod;

                                // merge
                                if (j + 1 <= n) {
                                        dp[i][j] += dp[i - 1][j + 1] * (j + 1);
                                        dp[i][j] %= mod;
                                }
                        } else {
                                // new
                                dp[i][j] += dp[i - 1][j - 1];
                                dp[i][j] %= mod;

                                // stick
                                dp[i][j] += dp[i - 1][j] * 2 * j;
                                dp[i][j] %= mod;

                                // merge
                                if (j + 1 <= n) {
                                        dp[i][j] += dp[i - 1][j + 1] * (j + 1) % mod * j;
                                        dp[i][j] %= mod;
                                }
                        }
                }
        }

        cout << dp[n][1] << '\n'; // ye
        
        return 0;
}

• 서브태스크 1: 0 / 6
• 서브태스크 2: 0 / 30
• 서브태스크 3: 0 / 15
• 서브태스크 4: 0 / 49