Submission #1217432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217432		duckindog	Solitaire (JOI16_solitaire)	C++20	100 / 100	96 ms	34888 KiB

solitaire

#include <bits/stdc++.h>

using namespace std;

const int N = 2000 + 10,
            M = 1'000'000'007;
int n;
int a[4][N];

inline void add(auto& x, const auto& y) { 
    x += y;
    if (x >= M) x -= M;
}

inline int powder(int a, int b) { 
    int ret = 1;
    for (; b; b /= 2, a = 1ll * a * a % M) { 
        if (b & 1) ret = 1ll * ret * a % M;
    }
    return ret;
}
inline int distribute(int n, int m) { 
    int ret = 1;
    for (int i = 1; i <= n; ++i, ++m) ret = 1ll * ret * m % M;
    return ret;
}

int f[N][N * 3][2], prefDP[N * 3][2];
int pref[N], cnt[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= 3; ++i) { 
        for (int j = 1; j <= n; ++j) { 
            char ch; cin >> ch;
            a[i][j] = (ch == 'x');
        }
    }

    { // check can form answer
        bool isValid = true;
        if (a[1][1] || a[1][n] || a[3][1] || a[3][n]) isValid = false;
        for (int i = 1; i <= 3; i += 2) { 
            int cnt0 = 0;
            for (int j = 1; j <= n; ++j) {
                if (a[i][j]) cnt0 += 1;
                else cnt0 = 0;
                if (cnt0 >= 2) isValid = false;
            }
        }

        if (!isValid) { 
            cout << 0 << "\n";
            return 0;
        }
    }

    for (int i = 1; i <= n; ++i) { 
        cnt[i] = a[1][i] + a[3][i];
        pref[i] = pref[i - 1] + a[1][i] + a[2][i] + a[3][i];
    }

    for (int j = 0; j <= pref[1]; ++j) { 
        if (a[2][1]) { 
            if (j > cnt[1]) f[1][j][0] = (cnt[1] <= 1 ? 1 : 2);
        } else { 
            if (!j) f[1][j][0] = (cnt[1] <= 1 ? 1 : 2);
        }
    }
    
    const int m = pref[n];
    for (int i = 2; i <= n; ++i) { 
        prefDP[0][0] = f[i - 1][0][0];
        prefDP[0][1] = f[i - 1][0][1];
        for (int j = 1; j <= m; ++j) {
            prefDP[j][0] = (prefDP[j - 1][0] + f[i - 1][j][0]) % M;
            prefDP[j][1] = (prefDP[j - 1][1] + f[i - 1][j][1]) % M;
        }
        auto getDP = [&](int l, int r, int type) { 
            return !l ? prefDP[r][type] : (prefDP[r][type] - prefDP[l - 1][type] + M) % M;
        };
        
        if (a[2][i]) { 
            for (int j = 1; j <= pref[i]; ++j) { 
                if (j >= cnt[i]) { // up & down and previous is 0
                    auto& ret = f[i][j][0];
                    int value = 1ll * getDP(0, m, 0) * 
                                distribute(cnt[i], j - cnt[i]) % M;
                    add(ret, value);
                }
                if (j >= cnt[i]) { // up & down and previous is 1
                    auto& ret = f[i][j][0];
                    int value = 1ll * getDP(j - cnt[i], m, 1) * 
                                distribute(cnt[i], j - cnt[i]) % M;
                    add(ret, value);
                }

                { // left & right
                    auto& ret = f[i][j][1];

                    for (int k = 0; k < cnt[i] && k < j; ++k) { 
                        int value = 1ll * getDP(0, j - 1 - k, 0) * 
                                    distribute(k, j - k) % M * 
                                    distribute(cnt[i] - k, pref[i - 1] + 2 - (j - k)) % M;
                        if (k) value = 1ll * value * max(1, cnt[i]) % M;
                        add(ret, value);
                    }
                }
            }
        } else { 
            auto& ret = f[i][0][0];
            int value = 1ll * (getDP(0, m, 0) + getDP(0, m, 1)) % M * 
                        distribute(cnt[i], pref[i - 1] + 1) % M;
            add(ret, value);
        }
    }

    int answer = 0;
    for (int i = 0; i <= m; ++i) add(answer, f[n][i][0]);

    cout << answer << "\n";
}

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