#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
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++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
125 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
