Submission #444164

#	Time	Username	Problem	Language	Result	Execution time	Memory
444164		prvocislo	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	52 ms	15948 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+2, vector<int>(n+2, 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 + 1 - c1;
                int val = (c2 * (c2 - 1)) + c1 * c2;
                upd(dp[i][j], mul(dp[i-1][j+1], val));
            }
        }
        //cout << dp[i][j] << " ";
        //if (j == n) cout << endl;
    }
    cout << dp[n][1] << "\n";
    return 0;
}

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