제출 #518428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518428		blue	Calvinball championship (CEOI15_teams)	C++17	100 / 100	718 ms	884 KiB

teams

#include <iostream>
using namespace std;

using ll = long long;
const ll mod = 1'000'007LL;

ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll sq(ll a)
{
    return mul(a, a);
}

ll pow(ll b, ll e)
{
    if(e == 0) return 1;
    else if(e % 2 == 0) return sq(pow(b, e/2));
    else return mul(b, pow(b, e-1));
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    ll a[1+n];
    a[0] = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];

    ll* ch[1+n];
    ch[0] = new ll[1+n];
    ch[1] = new ll[1+n];
    for(int i = 2; i <= n; i++) ch[i] = ch[i-2];

    for(int i = 0; i <= n; i++) ch[0][i] = ch[1][i] = 0;
    ch[0][0] = 1;

    ll dp[1+n];
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        dp[i] = 0;
        for(int t = 1; t <= i; t++)
        {
            // dp[i] = (dp[i] + ((dp[i-t] * ch[i-1][t-1]) % mod)) % mod;
            dp[i] = (dp[i] + ((dp[i-t] * ch[i-1][t-1]) % mod)) % mod;
        }

        ch[i][0] = ch[i][i] = 1;
        for(int j = 1; j < i; j++) ch[i][j] = (ch[i-1][j] + ch[i-1][j-1]) % mod;
    }



    ll fact[1+n];
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = mul(i, fact[i-1]);


    ll ans = 1;

    // ll q = 0;


    ll q[1+n];
    q[0] = 0;
    for(int i = 1; i <= n; i++) q[i] = max(q[i-1], a[i-1]);

    for(int i = 0; i <= n; i++) ch[0][i] = ch[1][i] = 0;


    for(int i = n; i >= 1; i--)
    {
        ch[n-i][0] = ch[n-i][n-i] = 1;
        for(int j = 1; j < n-i; j++)
            ch[n-i][j] = (ch[n-i-1][j-1] + ch[n-i-1][j]) % mod;

        ll qp = 1;

        for(int c = 0; c <= n-i; c++)
        {
            // cerr << i << ' ' << c << '\n';
            ll curr = ((ch[n-i][c] * qp * dp[n-i-c]) % mod) * (a[i]-1);
            ans = (ans + curr) % mod;

            qp = (qp * q[i]) % mod;
        }
    }

    cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10