QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357357 | #404. Solitaire | ewrilan | 0 | 190ms | 136816kb | C++14 | 5.9kb | 2024-03-18 20:39:13 | 2024-03-18 20:39:14 |
Judging History
answer
//
#ifndef __SIZEOF_INT128__
#define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
string name{""};
time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
duration<float, std::milli> dur;
Timer() = default;
Timer(string nm): name(nm) {}
~Timer() {
end = high_resolution_clock::now(); dur= end - start;
cout << "@" << name << "> " << dur.count() << " ms" << '\n';
}
};
template <typename T = int> inline T in()
{
static T x;
std::cin >> x;
return x;
}
std::string yn(bool b)
{
if(b) return "YES\n";
else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
for(const auto& i : wek)out << i << ' ';
return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
out << '{'<<par.first<<", "<<par.second<<"}";
return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
#include <assert.h>
constexpr int mod = 1e9 + 7;
class intm
{
int val;
public:
intm() = default;
intm(int a) : val{a} {}
explicit operator bool() {return val;}
explicit operator int() {return val;}
explicit operator long long() {return val;}
friend intm operator+(intm a, intm b){return ((long long)a + (long long)b) % mod;}
friend intm operator-(intm a, intm b){return (mod + (long long)a - (long long)b) % mod;}
friend intm operator*(intm a, intm b){return ((long long)a * (long long)b) % mod;}
friend intm operator-(intm a){return intm(0) - a;}
friend intm operator+(intm a){return a;}
friend intm operator!(intm a){return !a.val;}
intm operator++ () {return *this = *this+1;}
intm operator-- () {return *this = *this-1;}
template <typename T>
friend intm operator^(intm a, T b)
{
if(!b)return 1;
if(b & 1)return a*(a^(b-1));
intm p(a^(b/2));
return p*p;
}
intm operator~ () {assert(val); return *this ^ (mod - 2);}
friend intm operator/(intm a, intm b){return a * ~b;}
intm operator=(intm b){return val = b.val;}
intm operator+=(intm b){return *this = *this + b;}
intm operator-=(intm b){return *this = *this - b;}
intm operator*=(intm b){return *this = *this * b;}
intm operator/=(intm b){return *this = *this / b;}
intm operator^=(long long b){return *this = *this ^ b;}
friend std::ostream& operator<<(std::ostream& out, intm i){return out << i.val;}
friend std::istream& operator>>(std::istream& in, intm& i){return in >> i.val;}
friend bool operator==(intm a, intm b){return a.val == b.val;}
friend bool operator!=(intm a, intm b){return a.val != b.val;}
};
constexpr int ZAPAS = 1e6 + 3;
intm sil[ZAPAS], asil[ZAPAS];
intm nck(int n, int k){
if(k > n || k < 0)return 0;
return sil[n]*asil[k]*asil[n-k];
}
struct it{
int s; intm m;
it() : s(0), m(1) {}
it(int a, intm b) : s(a), m(b) {}
friend it operator+(it a, it b){ return {a.s+b.s, nck(a.s+b.s, a.s)*a.m*b.m}; }
void operator+=(it b){*this = *this + b;}
};
it mer(it a, it b){
assert(a.s == b.s);
return {a.s, a.m+b.m};
}
constexpr int MAXN = 2003;
bool ar[3][MAXN];
int rs[MAXN];
int n;
it odp_b[MAXN][MAXN][2][2];
it odp(int p, int k, bool jp, bool jk){
if(odp_b[p][k][jp][jk].s)return odp_b[p][k][jp][jk];
it r{};
if(p > k) r = it{};
else if(p == k){
if(jp && jk)r = {rs[p], sil[rs[p]]};
else r = {rs[p], sil[rs[p]]/rs[p]};
}
else{
int s(0);
rep(i, p, k+1)s += rs[i];
intm m = odp(p, p, jp, 1).m*odp(p+1, k, 0, jk).m + odp(k, k, 1, jk).m*odp(p, k-1, jp, 0).m;
rep(i, p+1, k)m += odp(p, i-1, jp, 0).m*odp(i, i, 1, 1).m*odp(i+1, k, 0, jk).m;
r = {s, m};
}
cerr << p << ' ' << k << ' ' << jp << ' ' << jk << ' ' << r.s << ' ' << r.m << '\n';
return odp_b[p][k][jp][jk] = r;
}
std::int32_t main()
{
sil[0] = 1;
rep(i, 1, ZAPAS)sil[i] = sil[i-1]*i;
rep(i, 0, ZAPAS)asil[i] = ~sil[i];
std::cout.tie(nullptr); //for luck
std::cin.tie(nullptr); std::ios_base::sync_with_stdio(0);
cin >> n;
rep(i, 1, 4)rep(j, 1, n+1) ar[i][j] = in<char>() == 'o';
if(!ar[1][1] || !ar[1][n] || !ar[3][1] || !ar[3][n]){
cout << "0\n";
return 0;
}
for(auto w: {1, 3})rep(i, 1, n)if(!ar[w][i] && !ar[w][i+1]){
cout << "0\n";
return 0;
}
rep(i, 1, n+1)rs[i] = !ar[1][i] + !ar[2][i] + !ar[3][i];
it s{};
int p(0), k(0);
while(k < n){
p = ++k;
if(ar[2][p]){
if(!ar[1][p])s += it{1, 1};
if(!ar[3][p])s += it{1, 1};
continue;
}
while(!ar[2][k+1])++k;
rep(i, p, k+1)s += it{rs[i], sil[rs[i]]/rs[i]};
// s += odp(p, k, p != 1, k != n);
}
cout << s.m << '\n';
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 190ms
memory: 136816kb
input:
21 ooooxoooooxoooooxoooo oooxooooooooxxxxxooxo ooxooooooooooooooooxo
output:
237167788
result:
wrong answer 1st lines differ - expected: '319334400', found: '237167788'
Subtask #2:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
880 ooxooooooxoxoooxoxoooooxooxooooxoxooooooooooooooxooooooxoxooooxooooxoxooooooxoxooooooooooxoxooooxooxooxoooooooooooxoxoooooxoooooxoxoxooxoooxooxooooxooooxoxoxoooxoooooxoooxooxoxoooooooxooooxooooooxooooxoxooxoooooxoxooooxooxooooooooooooooxoooooooooooxooooooooooooooxooooxoxoxooooooxooooooooxooooxoo...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #38:
score: 0
Wrong Answer
time: 189ms
memory: 136760kb
input:
27 oxooooxooooooxoooxoooooxoxo xxooxooooxxxoxoooxooxxxxxoo ooxoxoxoxoooxoxooooxoxooxoo
output:
800117529
result:
wrong answer 1st lines differ - expected: '106903779', found: '800117529'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%