Submission #963866

#	Time	Username	Problem	Language	Result	Execution time	Memory
963866		danikoynov	Ruins 3 (JOI20_ruins3)	C++14	0 / 100	1 ms	2396 KiB

ruins3

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 120;
const ll mod = 1e9 + 7;

int n, a[maxn];
int b[2 * maxn];
ll dp[2 * maxn][maxn][maxn], comb[maxn][maxn];
ll fp[maxn][maxn], fac[maxn];

ll power(ll base, ll st)
{
    ll res = 1;
    while(st > 0)
    {
        if (st % 2 == 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        st /= 2;
    }
    return res;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        b[a[i]] = 1;
    }

    if (a[n] != 2 * n)
    {
        cout << 0 << endl;
        return;
    }

    comb[0][0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        comb[i][0] = 1;
        for (int j = 1; j <= n; j ++)
        {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
            if (comb[i][j] >= mod)
                comb[i][j] -= mod;
        }
    }


    fp[0][0] = fp[1][0] = 1;
    for (int i = 2; i <= n; i ++)
    {
        fp[i][0] = fp[i - 1][0];
        for (int j = 1; j <= i; j ++)
        {
            fp[i][j] = fp[i - 1][j] + fp[i - 2][j - 1];
            fp[i][j] %= mod;
        }
    }


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

    ll dv = power(2, mod - 2);
    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= i; j ++)
        {
            int lf = i - j;
            fp[i][j] *= fac[i];
            fp[i][j] %= mod;
            fp[i][j] *= power(dv, j);
            fp[i][j] %= mod;
        }


        //cout << "fp " << fp[2][1] << endl;
        //return;
    dp[2 * n][1][0] = 1;
    if (n != 1)
        dp[2 * n][0][0] = 1;

    int down = 0, up = 1;
    for (int i = 2 * n - 1; i > 0; i --)
    {
        if (b[i] == 0)
            down ++;
        else
            up ++;

        if (b[i] == 0)
        {
            for (int j = 0; j <= up; j ++)
            {
                for (int d = 0; d <= j; d ++)
                {
                    ll lf_to_start = (j - d) - (j + (down - 1) - 2 * d);
                    ll lf_to_fill = (j - d) - lf_to_start;

                    if (lf_to_fill < 0 || lf_to_start < 0)
                        continue;
                    dp[i][j][d + 1] += dp[i + 1][j][d] * lf_to_fill;
                    dp[i][j][d + 1] %= mod;
                    dp[i][j][d] += dp[i + 1][j][d] * lf_to_start;
                    dp[i][j][d] %= mod;
                }

            }
        }
        else
        {
            for (int j = 0; j <= up; j ++)
            {
                for (int t = j; t <= up; t ++)
                {
                    if (up == n && t != up)
                        continue;

                    for (int d = 0; d <= up; d ++)
                    {
                        for (int k = d; k <= up; k ++)
                        {
                            ll dt = t - j;
                            ll dk = k - d;

                            if (dt != 0)
                            {

                                /**ll ways = comb[up - j - 1][dt - 1] * fp[dt][dk];
                                ways %= mod;
                                   dp[i][t][k] += dp[i + 1][j][d] * ways;
                                dp[i][t][k] %= mod;*/
                                /**if (i == 3 && t == 3 && k == 1)
                                {
                                    cout << "from " << i + 1 << " " << j << " " << d << " ways " << ways << endl;
                                }*/

                                /// without bind

                                ll ways = comb[up - j - 1][dt - 1] * fp[dt - 1][dk];


                                ways %= mod;
                                ll no_band = (dt - dk) - ((dt - 1) - 2 * dk);
                                ways = (ways * no_band)  % mod;
                                dp[i][t][k] += dp[i + 1][j][d] * ways;
                                dp[i][t][k] %= mod;

                                if (dk > 0)
                                {
                                    ways = comb[up - j - 1][dt - 1] * fp[dt - 1][dk - 1];
                                    ways %= mod;
                                    ll with_band =  ((dt - 1) - 2 * (dk - 1));

                                    /**if (i == 3 && t == 3 && k == 2)
                                    {
                                        cout << "no band " << no_band << endl;
                                        cout << "with band " << with_band << endl;
                                        cout << "dt " << dt << endl;
                                        cout << i + 1 << " " << j << " " << d << " " << dp[i + 1][j][d] << " " << ways << endl;
                                    }*/
                                    ways *= with_band;
                                    ways %= mod;

                                    dp[i][t][k] += dp[i + 1][j][d] * ways;
                                    dp[i][t][k] %= mod;
                                }



                            }
                            else
                            {
                                if (k == d)
                                {
                                    dp[i][j][d] += dp[i + 1][j][d];
                                    dp[i][j][d] %= mod;
                                }
                            }
                        }
                    }
                }
            }
        }

        cout << "---------------" << endl;
        for (int j = 0; j <= up; j ++)
            for (int d = 0; d <= j; d ++)
        {
            cout << "state " << i << " " << j << " " << d << " = " << dp[i][j][d] << endl;
        }
    }

    ll res = dp[1][n][n];
    //res = (res * dv) % mod;
    cout << res << endl;
}

int main()
{
    speed();
    int t = 1;
    ///cin >> t;
    while(t --)
        solve();
    return 0;
}
/**
13
3 7 9 12 13 15 16 18 22 23 24 25 26

*/

Compilation message (stderr)

ruins3.cpp: In function 'void solve()':
ruins3.cpp:86:17: warning: unused variable 'lf' [-Wunused-variable]
   86 |             int lf = i - j;
      |                 ^~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 52
• Subtask 3: 0 / 42