Submission #729171

#	Time	Username	Problem	Language	Result	Execution time	Memory
729171		abcvuitunggio	Solitaire (JOI16_solitaire)	C++17	0 / 100	125 ms	262144 KiB

solitaire

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,cnt,c[6001][6001],dp[2001][6001][2],pre[2001][6001][2],suf[2001][6002][2];
string s[3];
pair <int, int> p;
vector <int> v;
int C(int n, int k){
    if (n<k)
        return 0;
    if (!k)
        return 1;
    if (c[n][k]!=-1)
        return c[n][k];
    return c[n][k]=(C(n-1,k)+C(n-1,k-1))%mod;
}
void solve(){
    if (v.empty())
        return;
    int cnt=0;
    for (int i=0;i<v.size();i++){
        cnt+=v[i]+1;
        for (int j=1;j<=cnt+1;j++){
            for (int k=0;k<2;k++)
                dp[i][j][k]=pre[i][j][k]=suf[i][j][k]=0;
            if (!i){
                if (!v[i])
                    dp[i][j][0]=dp[i][j][1]=1;
                else if (v[i]==1){
                    dp[i][j][0]=j-1;
                    dp[i][j][1]=1;
                }
                else if (v[i]==2){
                    dp[i][j][0]=(j==3)*2;
                    dp[i][j][1]=2;
                }
                continue;
            }
            if (!v[i]){
                dp[i][j][0]=dp[i][j][1]=(pre[i-1][j-1][0]+suf[i-1][j][1])%mod;
                continue;
            }
            if (v[i]==1){
                dp[i][j][0]=((j>1?pre[i-1][j-2][0]:0)+suf[i-1][max(j-1,1LL)][1])%mod*(j-1)%mod;
                dp[i][j][1]=(dp[i][j][0]+pre[i-1][j-1][0]*(cnt-j)%mod)%mod;
                continue;
            }
            dp[i][j][0]=((j>2?pre[i-1][j-3][0]:0)+suf[i-1][max(j-2,1LL)][1])%mod*(j-1)%mod*(j-2)%mod;
            dp[i][j][1]=dp[i][j][0]+pre[i-1][j-1][0]*(cnt-j)%mod*(cnt-j-1)%mod+pre[i-1][j-2][0]*(cnt-j)%mod*(j-1)*2%mod;
        }
        for (int j=1;j<=cnt;j++){
            pre[i][j][0]=pre[i][j-1][0]+dp[i][j][0];
            pre[i][j][1]=pre[i][j-1][1]+dp[i][j][1];
        }
        for (int j=cnt;j;j--){
            suf[i][j][0]=suf[i][j+1][0]+dp[i][j][0];
            suf[i][j][1]=suf[i][j+1][1]+dp[i][j][1];
        }
    }
    p.second+=cnt;
    p.first=p.first*pre[v.size()-1][cnt][1]%mod*C(p.second,p.second-cnt)%mod;
    v.clear();
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    memset(c,-1,sizeof(c));
    cin >> n >> s[0] >> s[1] >> s[2];
    s[1]+='o';
    if (s[0][0]=='x'||s[0][n-1]=='x'||s[2][0]=='x'||s[2][n-1]=='x'){
        cout << 0;
        return 0;
    }
    for (int i=0;i<n-1;i++)
        if ((s[0][i]=='x'&&s[0][i+1]=='x')||(s[2][i]=='x'&&s[2][i+1]=='x')){
            cout << 0;
            return 0;
        }
    for (int i=0;i<n;i++){
        cnt+=(s[0][i]=='x'&&s[1][i]=='o');
        cnt+=(s[2][i]=='x'&&s[1][i]=='o');
    }
    p.second=cnt;
    p.first=1;
    for (int i=1;i<=cnt;i++)
        p.first=(p.first*i)%mod;
    for (int i=0;i<=n;i++){
        if (s[1][i]=='o'){
            solve();
            continue;
        }
        v.push_back((s[0][i]=='x')+(s[2][i]=='x'));
    }
    cout << p.first;
}

Compilation message (stderr)

solitaire.cpp: In function 'void solve()':
solitaire.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0;i<v.size();i++){
      |                  ~^~~~~~~~~

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