QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357366#404. Solitaireewrilan0 207ms136848kbC++145.9kb2024-03-18 20:45:582024-03-18 20:46:00

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 20:46:00]
  • 评测
  • 测评结果:0
  • 用时:207ms
  • 内存:136848kb
  • [2024-03-18 20:45:58]
  • 提交

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], (rs[i] == 3 ? 2 : 1)};
        // 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: 203ms
memory: 136848kb

input:

21
ooooxoooooxoooooxoooo
oooxooooooooxxxxxooxo
ooxooooooooooooooooxo

output:

237167788

result:

wrong answer 1st lines differ - expected: '319334400', found: '237167788'

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 207ms
memory: 136764kb

input:

880
ooxooooooxoxoooxoxoooooxooxooooxoxooooooooooooooxooooooxoxooooxooooxoxooooooxoxooooooooooxoxooooxooxooxoooooooooooxoxoooooxoooooxoxoxooxoooxooxooooxooooxoxoxoooxoooooxoooxooxoxoooooooxooooxooooooxooooxoxooxoooooxoxooooxooxooooooooooooooxoooooooooooxooooooooooooooxooooxoxoxooooooxooooooooxooooxoo...

output:

741322233

result:

wrong answer 1st lines differ - expected: '934647418', found: '741322233'

Subtask #3:

score: 0
Wrong Answer

Test #38:

score: 0
Wrong Answer
time: 191ms
memory: 136820kb

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%