제출 #444160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444160		prvocislo	캥거루 (CEOI16_kangaroo)	C++17	0 / 100	1 ms	204 KiB

kangaroo

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

const ll mod = 1e9 + 7;
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }
void upd(int &a, int b) { a = (a + b) % mod; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, s, f;
    cin >> n >> s >> f; 
    vector<vector<int> > dp(n+1, vector<int>(n+1, 0)); // dp[number of vertices][number of components]
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
    {
        if (i == s || i == f)
        {
            upd(dp[i][j], dp[i-1][j-1]); // bud pridame jeden novy komponent
            int c = (j - (s < i) - (f < i));
            if (i == n) c++;
            upd(dp[i][j], mul(dp[i-1][j], c)); // alebo sa napojime na nejaky predosly
        }
        else 
        {
            upd(dp[i][j], dp[i-1][j-1]); // bud pridame jeden novy komponent
            // ideme spojit dva ine komponenty. s a f mozeme (dokonca musime) spojit len ak i == n.
            if (i == n)
            {
                upd(dp[i][j], dp[i-1][j+1]);
            }
            else
            {
                int c1 = (s < i) + (f < i), c2 = j - c1;
                int val = (c2 * (c2 - 1)) * 2 + c1 * c2 * 2;
                upd(dp[i][j], mul(dp[i-1][j+1], val));
            }
        }
    }
    cout << dp[n][1] << "\n";
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49