oj.uz

Submission #910943

# Submission time Handle Problem Language Result Execution time Memory
910943 2024-01-18T09:58:57 Z bachhoangxuan None (JOI16_solitaire) C++17
100 / 100
 143 ms 117088 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=2005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=131;

int fac[3*maxn],dfac[3*maxn],inv[3*maxn];
int C(int n,int k){
    if(k>n || k<0 || n<0) return 0;
    return fac[n]*dfac[k]%mod*dfac[n-k]%mod;
}
int P(int n,int k){
    if(k>n || k<0 || n<0) return 0;
    return fac[n]*dfac[n-k]%mod;
}

void combi(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    dfac[n]=power(fac[n],mod-2);
    for(int i=n;i>=1;i--){
        dfac[i-1]=dfac[i]*i%mod;
        inv[i]=dfac[i]*fac[i-1]%mod;
    }
}
/*
dp[i][j][k] first i columns position j and (k = vertical/horizontal)

0->0
dp[i][j][0] -> dp[i+1][0][0]+=dp[i][j][0]*P(sum[i+1],cnt[i+1]) if c[1][i+1] = 'o',
            -> dp[i+1][d][0]+=dp[i][j][0]*P(d-1,cnt[i+1]-1) if c[1][i+1] = 'x';

0->1
if c[1][i+1] = 'o' || cnt[i+1]==1) don't do anything
dp[i][j][0] -> (j<d<=sum[i]+1) g[i+1][d]+=dp[i][j][0]

if(cnt[i+1]==2) g[i+1][d] -> dp[i+1][d][1]+=g[i+1][d]*(sum[i+1]-d);
if(cnt[i+1]==3){
    1. g[i+1][d] -> dp[i+1][d+1][1]+=g[i+1][d]*d*(sum[i+1]-d-1)*2;
    2. g[i+1][d] -> dp[i+1][d][1]+=g[i+1][d]*P(sum[i+1]-d,2);
}

1->0
if c[1][i+1] = 'o' dp[i][j][1] -> dp[i+1][0][0]+=dp[i][j][1]*P(sum[i+1],cnt[i+1])
dp[i][j][1] -> (1<=d<=j) f[i+1][d]+=dp[i][j][1]

f[i+1][d] -> dp[i+1][d+cnt[i+1]-1][0]+=f[i+1][d]*P(d+cnt[i+1]-2,cnt[i+1]-1);

*/

int n,c[3][maxn],sum[maxn],cnt[maxn];
int dp[maxn][3*maxn][2],f[maxn][3*maxn],g[maxn][3*maxn];

void solve(){
    cin >> n;
    combi(3*n);
    for(int i=0;i<=2;i++) for(int j=1;j<=n;j++){
        char cc;cin >> cc;
        c[i][j]=(cc=='x');
        cnt[j]+=c[i][j];
    }

    bool check=true;
    if(c[0][1] || c[2][1] || c[0][n] || c[2][n]) check=false;
    for(int i=1;i<n;i++){
        if(c[0][i] && c[0][i+1]) check=false;
        if(c[2][i] && c[2][i+1]) check=false;
    }

    if(!check){
        cout << 0 << '\n';
        return;
    }

    for(int j=1;j<=n;j++){
        sum[j]=sum[j-1]+cnt[j];
        //cout << sum[j] << ' ' << cnt[j] << '\n';
    }
    dp[0][0][0]=1;
    for(int i=0;i<n;i++){
        {//0->0
            int total=0;
            for(int j=0;j<=sum[i];j++) total=(total+dp[i][j][0])%mod;
            if(c[1][i+1]){
                for(int j=1;j<=sum[i+1];j++) dp[i+1][j][0]=(dp[i+1][j][0]+total*P(j-1,cnt[i+1]-1))%mod;
            }
            else{
                total=total*P(sum[i+1],cnt[i+1])%mod;
                dp[i+1][0][0]=(dp[i+1][0][0]+total)%mod;
            }
        }
        if(c[1][i+1] && cnt[i+1]>1 && i){//0->1
            for(int j=0;j<=sum[i];j++) g[i+1][j+1]=(g[i+1][j+1]+dp[i][j][0])%mod;
            for(int j=1;j<=sum[i]+1;j++){
                g[i+1][j]=(g[i+1][j]+g[i+1][j-1])%mod;
                if(cnt[i+1]==2) dp[i+1][j][1]=(dp[i+1][j][1]+g[i+1][j]*(sum[i+1]-j))%mod;
                else{
                    dp[i+1][j+1][1]=(dp[i+1][j+1][1]+g[i+1][j]*j*(sum[i+1]-j-1)*2)%mod;
                    dp[i+1][j][1]=(dp[i+1][j][1]+g[i+1][j]*P(sum[i+1]-j,2))%mod;
                }
            }
        }
        {//1->0
            if(!c[1][i+1]){
                for(int j=0;j<=sum[i];j++) dp[i+1][0][0]=(dp[i+1][0][0]+dp[i][j][1]*P(sum[i+1],cnt[i+1]))%mod;
            }
            else{
                for(int j=0;j<=sum[i];j++) f[i+1][j]=(f[i+1][j]+dp[i][j][1])%mod;
                for(int j=sum[i];j>=1;j--){
                    f[i+1][j]=(f[i+1][j]+f[i+1][j+1])%mod;
                    dp[i+1][j+cnt[i+1]-1][0]=(dp[i+1][j+cnt[i+1]-1][0]+f[i+1][j]*P(j+cnt[i+1]-2,cnt[i+1]-1))%mod;
                    //if(i==2) cout << f[i+1][j] << ' ' << dp[i+1][j+cnt[i+1]-1][0] << '\n';
                }
            }
        }
        /*
        cout << '*' << i+1 << '\n';
        for(int j=0;j<=sum[i+1];j++) cout << dp[i+1][j][0] << ' ';
        cout << '\n';
        for(int j=0;j<=sum[i+1];j++) cout << dp[i+1][j][1] << ' ';
        cout << '\n';
        */
    }
    int res=0;
    for(int i=0;i<=sum[n];i++) res=(res+dp[n][i][0])%mod;
    cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4560 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4696 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17244 KB Output is correct
2 Correct 40 ms 38228 KB Output is correct
3 Correct 9 ms 12636 KB Output is correct
4 Correct 61 ms 56012 KB Output is correct
5 Correct 58 ms 51284 KB Output is correct
6 Correct 49 ms 48084 KB Output is correct
7 Correct 35 ms 30980 KB Output is correct
8 Correct 56 ms 56400 KB Output is correct
9 Correct 57 ms 57520 KB Output is correct
10 Correct 32 ms 29780 KB Output is correct
11 Correct 42 ms 40400 KB Output is correct
12 Correct 62 ms 57428 KB Output is correct
13 Correct 62 ms 67668 KB Output is correct
14 Correct 64 ms 67676 KB Output is correct
15 Correct 65 ms 67804 KB Output is correct
16 Correct 74 ms 67768 KB Output is correct
17 Correct 67 ms 67668 KB Output is correct
18 Correct 67 ms 67668 KB Output is correct
19 Correct 73 ms 67708 KB Output is correct
20 Correct 65 ms 67852 KB Output is correct
21 Correct 67 ms 67668 KB Output is correct
22 Correct 69 ms 67848 KB Output is correct
23 Correct 66 ms 67752 KB Output is correct
24 Correct 66 ms 67584 KB Output is correct
25 Correct 63 ms 67668 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 2 ms 4700 KB Output is correct
14 Correct 2 ms 4700 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 2 ms 4964 KB Output is correct
17 Correct 2 ms 4700 KB Output is correct
18 Correct 2 ms 4700 KB Output is correct
19 Correct 2 ms 4700 KB Output is correct
20 Correct 2 ms 4700 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct
23 Correct 1 ms 4820 KB Output is correct
24 Correct 1 ms 4696 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4560 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4696 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 2 ms 4564 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 2 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4700 KB Output is correct
20 Correct 2 ms 4700 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct
23 Correct 1 ms 4700 KB Output is correct
24 Correct 2 ms 4700 KB Output is correct
25 Correct 2 ms 4700 KB Output is correct
26 Correct 2 ms 4700 KB Output is correct
27 Correct 1 ms 4700 KB Output is correct
28 Correct 2 ms 4964 KB Output is correct
29 Correct 2 ms 4700 KB Output is correct
30 Correct 2 ms 4700 KB Output is correct
31 Correct 2 ms 4700 KB Output is correct
32 Correct 2 ms 4700 KB Output is correct
33 Correct 2 ms 4700 KB Output is correct
34 Correct 1 ms 4700 KB Output is correct
35 Correct 1 ms 4820 KB Output is correct
36 Correct 1 ms 4696 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 5724 KB Output is correct
39 Correct 2 ms 4956 KB Output is correct
40 Correct 5 ms 8148 KB Output is correct
41 Correct 3 ms 6748 KB Output is correct
42 Correct 3 ms 7004 KB Output is correct
43 Correct 5 ms 7640 KB Output is correct
44 Correct 3 ms 6744 KB Output is correct
45 Correct 4 ms 8028 KB Output is correct
46 Correct 4 ms 7260 KB Output is correct
47 Correct 4 ms 7516 KB Output is correct
48 Correct 4 ms 8284 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4560 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4696 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 14 ms 17244 KB Output is correct
14 Correct 40 ms 38228 KB Output is correct
15 Correct 9 ms 12636 KB Output is correct
16 Correct 61 ms 56012 KB Output is correct
17 Correct 58 ms 51284 KB Output is correct
18 Correct 49 ms 48084 KB Output is correct
19 Correct 35 ms 30980 KB Output is correct
20 Correct 56 ms 56400 KB Output is correct
21 Correct 57 ms 57520 KB Output is correct
22 Correct 32 ms 29780 KB Output is correct
23 Correct 42 ms 40400 KB Output is correct
24 Correct 62 ms 57428 KB Output is correct
25 Correct 62 ms 67668 KB Output is correct
26 Correct 64 ms 67676 KB Output is correct
27 Correct 65 ms 67804 KB Output is correct
28 Correct 74 ms 67768 KB Output is correct
29 Correct 67 ms 67668 KB Output is correct
30 Correct 67 ms 67668 KB Output is correct
31 Correct 73 ms 67708 KB Output is correct
32 Correct 65 ms 67852 KB Output is correct
33 Correct 67 ms 67668 KB Output is correct
34 Correct 69 ms 67848 KB Output is correct
35 Correct 66 ms 67752 KB Output is correct
36 Correct 66 ms 67584 KB Output is correct
37 Correct 63 ms 67668 KB Output is correct
38 Correct 1 ms 4700 KB Output is correct
39 Correct 1 ms 4700 KB Output is correct
40 Correct 2 ms 4564 KB Output is correct
41 Correct 1 ms 4700 KB Output is correct
42 Correct 2 ms 4700 KB Output is correct
43 Correct 1 ms 4700 KB Output is correct
44 Correct 1 ms 4700 KB Output is correct
45 Correct 2 ms 4700 KB Output is correct
46 Correct 2 ms 4700 KB Output is correct
47 Correct 1 ms 4700 KB Output is correct
48 Correct 1 ms 4700 KB Output is correct
49 Correct 2 ms 4700 KB Output is correct
50 Correct 2 ms 4700 KB Output is correct
51 Correct 2 ms 4700 KB Output is correct
52 Correct 1 ms 4700 KB Output is correct
53 Correct 2 ms 4964 KB Output is correct
54 Correct 2 ms 4700 KB Output is correct
55 Correct 2 ms 4700 KB Output is correct
56 Correct 2 ms 4700 KB Output is correct
57 Correct 2 ms 4700 KB Output is correct
58 Correct 2 ms 4700 KB Output is correct
59 Correct 1 ms 4700 KB Output is correct
60 Correct 1 ms 4820 KB Output is correct
61 Correct 1 ms 4696 KB Output is correct
62 Correct 2 ms 4956 KB Output is correct
63 Correct 2 ms 5724 KB Output is correct
64 Correct 2 ms 4956 KB Output is correct
65 Correct 5 ms 8148 KB Output is correct
66 Correct 3 ms 6748 KB Output is correct
67 Correct 3 ms 7004 KB Output is correct
68 Correct 5 ms 7640 KB Output is correct
69 Correct 3 ms 6744 KB Output is correct
70 Correct 4 ms 8028 KB Output is correct
71 Correct 4 ms 7260 KB Output is correct
72 Correct 4 ms 7516 KB Output is correct
73 Correct 4 ms 8284 KB Output is correct
74 Correct 48 ms 44184 KB Output is correct
75 Correct 13 ms 15964 KB Output is correct
76 Correct 22 ms 22288 KB Output is correct
77 Correct 83 ms 70392 KB Output is correct
78 Correct 81 ms 72884 KB Output is correct
79 Correct 43 ms 39360 KB Output is correct
80 Correct 77 ms 68688 KB Output is correct
81 Correct 62 ms 56516 KB Output is correct
82 Correct 77 ms 69792 KB Output is correct
83 Correct 51 ms 40580 KB Output is correct
84 Correct 41 ms 34644 KB Output is correct
85 Correct 69 ms 59400 KB Output is correct
86 Correct 124 ms 116564 KB Output is correct
87 Correct 122 ms 116300 KB Output is correct
88 Correct 126 ms 115104 KB Output is correct
89 Correct 122 ms 116176 KB Output is correct
90 Correct 123 ms 115212 KB Output is correct
91 Correct 143 ms 117088 KB Output is correct
92 Correct 119 ms 116900 KB Output is correct
93 Correct 119 ms 116196 KB Output is correct
94 Correct 123 ms 116320 KB Output is correct
95 Correct 128 ms 116500 KB Output is correct
96 Correct 128 ms 116064 KB Output is correct
97 Correct 118 ms 115040 KB Output is correct