QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209089#3680. 序列染色KHIN100 ✓31ms28096kbC++176.0kb2023-10-10 09:44:142023-10-10 09:44:14

Judging History

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

  • [2023-10-10 09:44:14]
  • 评测
  • 测评结果:100
  • 用时:31ms
  • 内存:28096kb
  • [2023-10-10 09:44:14]
  • 提交

answer

# include <bits/stdc++.h>

using namespace std;

namespace kh {
  constexpr int P(1'000'000'007);
  inline namespace src {
    template <typename T>
      constexpr auto cmin(T& a, T const& b) {
        if (b < a) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T>
      constexpr auto cmax(T& a, T const& b) {
        if (a < b) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T>
      constexpr auto cminmax(T& a, T& b) {
        bool const swp(b < a ? swap(a, b), true : false);
        return make_pair(pair<T&, T&>(a, b), swp);
      }
    template <typename T, class Compare>
      constexpr auto cmin(T& a, T const& b, Compare comp) {
        if (comp(b, a)) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T, class Compare>
      constexpr auto cmax(T& a, T const& b, Compare comp) {
        if (comp(a, b)) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T, class Compare>
      constexpr auto cminmax(T& a, T& b, Compare comp) {
        bool const swp(comp(b, a) ? swap(a, b), true : false);
        return make_pair(pair<T&, T&>(a, b), swp);
      }
    template <typename T>
      constexpr int sgn(T const x)
      { return (x > 0) - (x < 0); }
    template <typename T>
      struct frac {
        T num, den;
        constexpr frac(T const n = 0, T const d = 1)
          : num(n / __gcd(n, d)), den(d / __gcd(n, d))
        { assert(den), num *= sgn(den), den *= sgn(den); }
        constexpr frac& operator+=(frac const b) { return *this = *this + b; }
        constexpr frac& operator-=(frac const b) { return *this = *this - b; }
        constexpr frac& operator*=(frac const b) { return *this = *this * b; }
        constexpr frac& operator/=(frac const b) { return *this = *this / b; }
        constexpr frac& operator++() { return num += den, *this; }
        constexpr frac& operator--() { return num -= den, *this; }
        constexpr frac operator++(int) { return num += den, *this - 1; }
        constexpr frac operator--(int) { return num -= den, *this - 1; }
        constexpr frac operator+() const { return frac(+num, den); }
        constexpr frac operator-() const { return frac(-num, den); }
        friend constexpr frac operator+(frac const a, frac const b)
        { return frac(a.num * b.den + b.num * a.den, a.den * b.den); }
        friend constexpr frac operator-(frac const a, frac const b)
        { return frac(a.num * b.den - b.num * a.den, a.den * b.den); }
        friend constexpr frac operator*(frac const a, frac const b)
        { return frac(a.num * b.num, a.den * b.den); }
        friend constexpr frac operator/(frac const a, frac const b)
        { return frac(a.num * b.den, a.den * b.num); }
        friend constexpr bool operator==(frac const a, frac const b)
        { return a.num * b.den == b.num * a.den; }
        friend constexpr bool operator!=(frac const a, frac const b)
        { return a.num * b.den != b.num * a.den; }
        friend constexpr bool operator<(frac const a, frac const b)
        { return a.num * b.den < b.num * a.den; }
        friend constexpr bool operator>(frac const a, frac const b)
        { return a.num * b.den > b.num * a.den; }
        friend constexpr bool operator<=(frac const a, frac const b)
        { return a.num * b.den <= b.num * a.den; }
        friend constexpr bool operator>=(frac const a, frac const b)
        { return a.num * b.den >= b.num * a.den; }
      };
    constexpr int pow(int a, int n) {
      int r(1);
      while (n) {
        r = 1l * r * (n & 1 ? a : 1) % P;
        a = 1l * a * a % P, n >>= 1;
      }
      return r;
    }
  }
  constexpr int N(1'000'000);
  int n, k;
  char s[N + 2];
  int cb[N + 1];
  int cw[N + 1];
  int cx[N + 1];
  int f[N + 1];
  int g[N + 1];
  int t[N + 1];
  int ans;
  void main() {
    cin >> n >> k >> (s + 1);
    for (int i(1); i <= n; ++i) {
      cb[i] = cb[i - 1] + (s[i] == 'B');
      cw[i] = cw[i - 1] + (s[i] == 'W');
      cx[i] = cx[i - 1] + (s[i] == 'X');
    }
    t[0] = f[0] = 1;
    for (int i(1), j(0); i <= n; ++i) {
      j = max(s[i] == 'W' ? i : j, i - k + 1);
      t[i] = s[i] == 'B' ? 0 : f[i - 1];
      t[i] = (t[i - 1] + t[i]) % P;
      f[i] = (t[i] - (j ? t[j - 1] : 0)) % P;
    }
    for (int i(n); i >= 0; --i) {
      if (i < k) { f[i] = 0; continue; }
      if (cw[i] != cw[i - k]) { f[i] = 0; continue; }
      if (s[i - k] == 'B') { f[i] = 0; continue; }
      f[i] = i - k ? f[i - k - 1] : 1;
    }
    reverse(s + 1, s + n + 1);
    for (int i(1); i <= n; ++i) {
      cb[i] = cb[i - 1] + (s[i] == 'B');
      cw[i] = cw[i - 1] + (s[i] == 'W');
      cx[i] = cx[i - 1] + (s[i] == 'X');
    }
    t[0] = g[0] = 1;
    for (int i(1), j(0); i <= n; ++i) {
      j = max(s[i] == 'B' ? i : j, i - k + 1);
      t[i] = s[i] == 'W' ? 0 : g[i - 1];
      t[i] = (t[i - 1] + t[i]) % P;
      g[i] = (t[i] - (j ? t[j - 1] : 0)) % P;
    }
    for (int i(n); i >= 0; --i) {
      if (i < k) { g[i] = 0; continue; }
      if (cb[i] != cb[i - k]) { g[i] = 0; continue; }
      if (s[i - k] == 'W') { g[i] = 0; continue; }
      g[i] = i - k ? g[i - k - 1] : 1;
    }
    reverse(s + 1, s + n + 1);
    for (int i(1); i <= n; ++i) {
      cb[i] = cb[i - 1] + (s[i] == 'B');
      cw[i] = cw[i - 1] + (s[i] == 'W');
      cx[i] = cx[i - 1] + (s[i] == 'X');
    }
    for (int i(0), s(0); i <= n; ++i) {
      s = s * (kh::s[i] == 'X' ? 2 : 1) % P;
      s = (s + (i >= k && cw[i] == cw[i - k] ? f[i] : 0)) % P;
      if (i + k <= n && cb[i + k] == cb[i])
        ans = (ans + 1l * s * g[n - i]) % P;
    }
    cout << (ans = (ans + P) % P) << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t(1);
  // cin >> t;
  for (int i(1); i <= t; ++i) kh::main();
}

詳細信息

Test #1:

score: 10
Accepted
time: 1ms
memory: 7856kb

input:

1 1000000
X


output:

0

result:

ok single line: '0'

Test #2:

score: 10
Accepted
time: 1ms
memory: 7772kb

input:

20 4
XXXXXXXXXXXXXXXXXXXX


output:

108155

result:

ok single line: '108155'

Test #3:

score: 10
Accepted
time: 1ms
memory: 9856kb

input:

2000 200
BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...

output:

590565731

result:

ok single line: '590565731'

Test #4:

score: 10
Accepted
time: 1ms
memory: 7760kb

input:

2000 100
WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...

output:

313979285

result:

ok single line: '313979285'

Test #5:

score: 10
Accepted
time: 1ms
memory: 7828kb

input:

2000 100
XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...

output:

358862528

result:

ok single line: '358862528'

Test #6:

score: 10
Accepted
time: 15ms
memory: 25060kb

input:

765432 5000
WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...

output:

74325182

result:

ok single line: '74325182'

Test #7:

score: 10
Accepted
time: 26ms
memory: 26120kb

input:

876543 5000
WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...

output:

786550221

result:

ok single line: '786550221'

Test #8:

score: 10
Accepted
time: 19ms
memory: 28020kb

input:

1000000 10000
WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...

output:

627927296

result:

ok single line: '627927296'

Test #9:

score: 10
Accepted
time: 31ms
memory: 28096kb

input:

1000000 20000
XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...

output:

412860887

result:

ok single line: '412860887'

Test #10:

score: 10
Accepted
time: 26ms
memory: 28084kb

input:

1000000 50000
WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...

output:

773406112

result:

ok single line: '773406112'