Submission #62686

#	Time	Username	Problem	Language	Result	Execution time	Memory
62686		SpaimaCarpatilor	Solitaire (JOI16_solitaire)	C++17	100 / 100	112 ms	1172 KiB

solitaire

#include<bits/stdc++.h>

using namespace std;

int N, x[2018];
char sir[3][2018];
const int mod = 1e9 + 7;

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int subtract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}
void adto (int &x, int y) {x += y; if (x >= mod) x -= mod;}

int power (int a, int b)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = mul (p, a);
        a = mul (a, a);
    }
    return p;
}

int inv[6009], fac[6009];
void Prec (int lim){fac[0] = inv[0] = 1;for (int i=1; i<=lim; i++)fac[i] = mul (fac[i - 1], i);
inv[lim] = power (fac[lim], mod - 2);for (int i=lim - 1; i>=0; i--)inv[i] = mul (inv[i + 1], i + 1);}
int comb (int N, int K){if (K > N || N < 0 || K < 0) return 0;
int ans = mul (fac[N], inv[N - K]);ans = mul (ans, inv[K]);return ans;}

void finish (int ans)
{
    printf ("%d\n", ans);
    exit (0);
}

void combine (int &cnt, int &l, int nc, int nl)
{
    l += nl;
    cnt = mul (cnt, mul (nc, comb (l, nl)));
}

int old[6009];
void shiftDp (int dp[], int sz, int type, int x)
{
    if (x == 0)
    {
        if (type == 0)
        {
            for (int i=1; i<=sz + 2; i++)
                dp[i] = 0;
        }
        return ;
    }
    for (int i=1; i<=sz; i++)
        old[i] = dp[i], dp[i] = 0;
    dp[sz + 1] = dp[sz + 2] = 0;
    if (type == 0)
    {
        ///I want to have at least one after
        for (int i=1; i<=sz; i++)
        if (old[i] > 0)
        {
            if (x == 1)
                adto (dp[i], mul (old[i], sz - i + 1));
            else
            {
                adto (dp[i], mul (old[i], (sz - i + 2) * (sz - i + 1)));
                adto (dp[i + 1], mul (old[i], 2 * i * (sz - i + 1)));
            }
        }
        return ;
    }
    ///I want them both before
    for (int i=1; i<=sz; i++)
        if (old[i] > 0)
        {
            if (x == 1)
                adto (dp[i + 1], mul (old[i], i));
            else
                adto (dp[i + 2], mul (old[i], (i + 1) * i));
        }
}

int s[2][6009];
void add (int line, int l, int r, int x)
{
    adto (s[line][l], x);
    s[line][r + 1] = subtract (s[line][r + 1], x);
}

void marsToDp (int s[], int v[], int sz)
{
    v[1] = 0;
    for (int i=1; i<=sz; i++)
        v[i] = add (v[i - 1], s[i]);
}

int dp[2][2][6009];
void solve (int l, int r, int &nc, int &nl)
{
    memset (dp[l & 1], 0, sizeof (dp[l & 1]));
    dp[l & 1][0][1] = (l != 1);
    dp[l & 1][1][1] = 1;
    shiftDp (dp[l & 1][0], 1, 0, x[l]);
    shiftDp (dp[l & 1][1], 1, 1, x[l]);
    int currL = x[l] + 1;
    for (int i=l; i<r; i++)
    {
        int nxt = (i & 1) ^ 1;
        memset (dp[nxt], 0, sizeof (dp[nxt]));
        for (int j=0; j<=currL + 2; j++)
            s[0][j] = s[1][j] = 0;
        for (int j=0; j<2; j++)
            for (int k=0; k<2; k++)
                if (j + k > 0)
                    for (int p1=1; p1<=currL; p1++)
                    {
                        if (j == 0) add (k, 1, p1, dp[i & 1][j][p1]);
                        else
                        if (k == 0) add (k, p1 + 1, currL + 1, dp[i & 1][j][p1]);
                        else add (k, 1, currL + 1, dp[i & 1][j][p1]);
                    }
        marsToDp (s[0], dp[nxt][0], currL + 1);
        marsToDp (s[1], dp[nxt][1], currL + 1);

        shiftDp (dp[nxt][0], currL + 1, 0, x[i + 1]);
        shiftDp (dp[nxt][1], currL + 1, 1, x[i + 1]);
        currL += x[i + 1] + 1;
    }
    if (r == N)
        memset (dp[r & 1][0], 0, sizeof (dp[r & 1][0]));
    int ans = 0;
    for (int i=0; i<2; i++)
        for (int j=1; j<=currL; j++)
            adto (ans, dp[r & 1][i][j]);
    nc = ans, nl = currL;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d\n", &N), Prec (3 * N + 1);
for (int i=0; i<3; i++)
{
    scanf ("%s", sir[i] + 1);
    for (int j=1; j<=N; j++)
        sir[i][j] = (sir[i][j] == 'o');
}
if (sir[0][1] == 0 || sir[0][N] == 0 || sir[2][1] == 0 || sir[2][N] == 0)
    finish (0);
for (int i=0; i<3; i+=2)
    for (int j=1; j<N; j++)
        if (sir[i][j] == 0 && sir[i][j + 1] == 0)
            finish (0);
for (int i=1; i<=N; i++)
    x[i] = (2 - sir[0][i] - sir[2][i]);
int extra = 0, cnt = 1, l = 0;
for (int j=1; j<=N; j++)
    if (sir[1][j] == 0)
    {
        int k = j;
        while (sir[1][k + 1] == 0 && k < N)
            k ++;
        int nc, nl;
        solve (j, k, nc, nl);
        combine (cnt, l, nc, nl);
        j = k;
    }
    else extra += x[j];
combine (cnt, l, fac[extra], extra);
printf ("%d\n", cnt);
return 0;
}

Compilation message (stderr)

solitaire.cpp: In function 'int main()':
solitaire.cpp:145:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d\n", &N), Prec (3 * N + 1);
 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
solitaire.cpp:148:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%s", sir[i] + 1);
     ~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 20 / 20
• Subtask 4: 38 / 38
• Subtask 5: 20 / 20