Submission #729186

#	Time	Username	Problem	Language	Result	Execution time	Memory
729186		abcvuitunggio	Solitaire (JOI16_solitaire)	C++17	100 / 100	103 ms	77388 KiB

solitaire

#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,cnt,f[6001],f2[6001],dp[2001][6001][2],pre[2001][6001],suf[2001][6002];
string s[3];
pair <int, int> p;
vector <int> v;
int pw(int a, int b){
    if (!b)
        return 1;
    int t=pw(a,b>>1);
    t=(1LL*t*t)%mod;
    return (b&1?(1LL*t*a)%mod:t);
}
int C(int n, int k){
    return 1LL*f[n]*f2[k]%mod*f2[n-k]%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++){
            dp[i][j][0]=dp[i][j][1]=pre[i][j]=suf[i][j]=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]+suf[i-1][j])%mod;
                continue;
            }
            if (v[i]==1){
                dp[i][j][0]=1LL*((j>1?pre[i-1][j-2]:0)+suf[i-1][max(j-1,1)])%mod*(j-1)%mod;
                dp[i][j][1]=(dp[i][j][0]+1LL*pre[i-1][j-1]*(cnt-j)%mod)%mod;
                continue;
            }
            dp[i][j][0]=1LL*((j>2?pre[i-1][j-3]:0)+suf[i-1][max(j-2,1)])%mod*(j-1)%mod*(j-2)%mod;
            dp[i][j][1]=((dp[i][j][0]+1LL*pre[i-1][j-1]*(cnt-j)%mod*(cnt-j-1)%mod)%mod+1LL*pre[i-1][j-2]*(cnt-j)%mod*(j-1)*2%mod)%mod;
        }
        for (int j=1;j<=cnt;j++)
            pre[i][j]=(pre[i][j-1]+dp[i][j][0])%mod;
        for (int j=cnt;j;j--)
            suf[i][j]=(suf[i][j+1]+dp[i][j][1])%mod;
    }
    p.second+=cnt;
    p.first=1LL*p.first*suf[v.size()-1][1]%mod*C(p.second,p.second-cnt)%mod;
    v.clear();
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    f[0]=f2[0]=1;
    for (int i=1;i<=6000;i++){
        f[i]=1LL*f[i-1]*i%mod;
        f2[i]=pw(f[i],mod-2);
    }
    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={f[cnt],cnt};
    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: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0;i<v.size();i++){
      |                  ~^~~~~~~~~

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