oj.uz

Submission #729182

# Submission time Handle Problem Language Result Execution time Memory
729182 2023-04-23T15:21:19 Z abcvuitunggio None (JOI16_solitaire) C++17
10 / 100
 4 ms 500 KB 
#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+1LL*pre[i-1][j-2]*(cnt-j)%mod*(j-1)*2%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.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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 292 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 368 KB Output is correct
12 Correct 3 ms 340 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Incorrect 2 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 292 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 368 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 4 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Incorrect 2 ms 340 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 292 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 368 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Incorrect 2 ms 500 KB Output isn't correct
14 Halted 0 ms 0 KB -