Submission #849509

#	Time	Username	Problem	Language	Result	Execution time	Memory
849509		mickey080929	Solitaire (JOI16_solitaire)	C++17	100 / 100	85 ms	150876 KiB

solitaire

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

ll modpow(ll a, ll b) {
    ll ret = 1;
    while (b > 0) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

ll C(ll a, ll b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    return a * (a+1) % mod;
}

ll n;
char a[2010][3];
ll dp1[2010][6010];
ll dp2[2010][6010];
ll fac[6010];

int main() {
    fac[0] = 1;
    for (ll i=1; i<=6000; i++) fac[i] = fac[i-1] * i % mod;
    scanf("%lld", &n);
    ll cnt = 0;
    for (ll j=0; j<3; j++) {
        for (ll i=1; i<=n; i++) {
            scanf(" %c", &a[i][j]);
            if (a[i][j] == 'x') cnt ++;
        }
    }
    if (a[1][0] == 'x' || a[1][2] == 'x' || a[n][0] == 'x' || a[n][2] == 'x') {
        printf("0");
        return 0;
    }
    for (ll i=1; i<=n-1; i++) {
        if (a[i][0] == 'x' && a[i+1][0] == 'x') {
            printf("0");
            return 0;
        }
        if (a[i][2] == 'x' && a[i+1][2] == 'x') {
            printf("0");
            return 0;
        }
    }
    ll ans = fac[cnt];
    ll p = 0;
    for (ll i=1; i<=n; i++) {
        if (a[i][1] == 'o') {
            if (p == 0) continue;
            ll sum = 0;
            for (ll j=1; j<=p; j++) {
                sum += dp1[i-1][j] + dp2[i-1][j];
                sum %= mod;
            }
            ans = ans * modpow(fac[p], mod-2) % mod * sum % mod;
            p = 0;
            continue;
        }
        ll t = (a[i][0] == 'x') + (a[i][2] == 'x');
        if (p > 0) {
            ll sum = 0;
            for (ll j=1; j<=p; j++) sum = (sum + dp1[i-1][j]) % mod;
            for (ll j=1; j<=p+1; j++) {
                dp1[i][j+t] = sum * C(j, t) % mod;
            }
            sum = 0;
            for (ll j=p; j>=1; j--) {
                sum += dp2[i-1][j];
                sum %= mod;
                dp1[i][j+t] = (dp1[i][j+t] + sum * C(j, t)) % mod;
            }
            sum = 0;
            for (ll j=2; j<=p+1; j++) {
                sum += dp1[i-1][j-1];
                sum %= mod;
                for (ll k=0; k<=t-1; k++) {
                    dp2[i][j+k] += sum * C(j, k) % mod * C(p-j+2, t-k) % mod * C(t, k);
                    dp2[i][j+k] %= mod;
                }
            }
        }
        else {
            dp1[i][t+1] = fac[t];
            if (i != 1) {
                if (t >= 1) dp2[i][1] = fac[t];
                if (t == 2) dp2[i][2] = 2;
            }
        }
        p += t + 1;
    }
    if (p != 0) {
        ll sum = 0;
        for (ll j=1; j<=p; j++) {
            sum += dp1[n][j];
            sum %= mod;
        }
        ans = ans * modpow(fac[p], mod-2) % mod * sum % mod;
    }
    printf("%lld", ans);
}

Compilation message (stderr)

solitaire.cpp: In function 'int main()':
solitaire.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
solitaire.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |             scanf(" %c", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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