QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113921#6637. Perfect StringsITMO_pengzooAC ✓190ms120312kbC++208.0kb2023-06-20 02:19:412023-06-20 02:19:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-20 02:19:41]
  • 评测
  • 测评结果:AC
  • 用时:190ms
  • 内存:120312kb
  • [2023-06-20 02:19:41]
  • 提交

answer

//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#ifdef GOLIKOV
  #include "/Users/golikovnik/contests/debug.h"
#else
  #define debug(...) ;
#endif

template <class A, class B>
bool smin(A& x, B&& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A& x, B&& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

//  by https://codeforces.com/profile/Nyaan
//  example submission:
//  https://codeforces.com/contest/1603/submission/133688639
template <uint32_t mod>
struct LazyMontgomeryModInt {
  using mint = LazyMontgomeryModInt;
  using i32 = int32_t;
  using u32 = uint32_t;
  using u64 = uint64_t;
 
  static constexpr u32 get_r() {
    u32 ret = mod;
    for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
    return ret;
  }
 
  static constexpr u32 r = get_r();
  static constexpr u32 n2 = -u64(mod) % mod;
  static_assert(r * mod == 1, "invalid, r * mod != 1");
  static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
  static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
 
  u32 a;
 
  constexpr LazyMontgomeryModInt() : a(0) {}
  constexpr LazyMontgomeryModInt(const int64_t &b)
      : a(reduce(u64(b % mod + mod) * n2)){};
 
  static constexpr u32 reduce(const u64 &b) {
    return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
  }
 
  constexpr mint &operator+=(const mint &b) {
    if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }

  constexpr mint &operator++() {
    return *this += 1;
  }

  constexpr mint operator++(int) {
    auto ret = *this;
    *this += 1;
    return ret;
  }

  constexpr mint &operator-=(const mint &b) {
    if (i32(a -= b.a) < 0) a += 2 * mod;
    return *this;
  }

  constexpr mint &operator--() {
    return *this -= 1;
  }

  constexpr mint operator--(int) {
    auto ret = *this;
    *this -= 1;
    return ret;
  }
 
  constexpr mint &operator*=(const mint &b) {
    a = reduce(u64(a) * b.a);
    return *this;
  }
 
  constexpr mint &operator/=(const mint &b) {
    *this *= b.inv();
    return *this;
  }
 
  constexpr friend mint operator+(mint a, const mint &b) { return a += b; }
  constexpr friend mint operator-(mint a, const mint &b) { return a -= b; }
  constexpr friend mint operator*(mint a, const mint &b) { return a *= b; }
  constexpr friend mint operator/(mint a, const mint &b) { return a /= b; }
  constexpr friend bool operator==(mint const& a, const mint &b) {
    return (a.a >= mod ? a.a - mod : a.a) == (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr friend bool operator!=(mint const& a, const mint &b) {
    return (a.a >= mod ? a.a - mod : a.a) != (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr friend bool operator<(mint const& a, const mint &b) {
    return (a.a >= mod ? a.a - mod : a.a) < (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr mint operator-() const { return mint() - mint(*this); }
 
  constexpr mint power(u64 n) const {
    mint ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  
  constexpr mint inv() const { return power(mod - 2); }
 
  friend ostream &operator<<(ostream &os, const mint &b) {
    return os << b.get();
  }
 
  friend istream &operator>>(istream &is, mint &b) {
    int64_t t;
    is >> t;
    b = LazyMontgomeryModInt<mod>(t);
    return (is);
  }
  
  constexpr u32 get() const {
    u32 ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }

  constexpr explicit operator int() const {
    return int(get());
  }

  constexpr explicit operator bool() const {
    return bool(get());
  }
 
  static constexpr u32 get_mod() { return mod; }
};
 
template <typename T>
struct Binomial {
  vector<T> f, g, h;
  Binomial(int MAX = 0) : f(1, T(1)), g(1, T(1)), h(1, T(1)) {
    extend(MAX + 1);    
  }

  void extend(int m) {
    int n = f.size();

    if (n >= m) {
      return;
    }

    f.resize(m);
    g.resize(m);
    h.resize(m);
    for (int i = n; i < m; i++) f[i] = f[i - 1] * T(i);
    g[m - 1] = f[m - 1].inv();
    h[m - 1] = g[m - 1] * f[m - 2];
    for (int i = m - 2; i >= n; i--) {
      g[i] = g[i + 1] * T(i + 1);
      h[i] = g[i] * f[i - 1];
    } 
  }

  void extend() {
    extend(2 * f.size());
  }
 
  T fact(int i) {
    if (i < 0) return T(0);
    while (i >= (int)f.size()) extend();
    return f[i];
  }
 
  T ifact(int i) {
    if (i < 0) return T(0);
    while (i >= (int)g.size()) extend();
    return g[i];
  }
 
  T inv(int i) {
    if (i < 0) return -inv(-i);
    while (i >= (int)h.size()) extend();
    return h[i];
  }
 
  T C(int n, int r) {
    if (n < 0 || n < r || r < 0) return T(0);
    return fact(n) * ifact(n - r) * ifact(r);
  }
 
  inline T operator()(int n, int r) { return C(n, r); }
 
  template <typename I>
  T multinomial(const vector<I>& r) {
    static_assert(is_integral<I>::value == true);
    int n = 0;
    for (auto& x : r) {
      if(x < 0) return T(0);
      n += x;
    }
    T res = fact(n);
    for (auto& x : r) res *= ifact(x);
    return res;
  }
 
  template <typename I>
  T operator()(const vector<I>& r) {
    return multinomial(r);
  }
 
  T C_naive(int n, int r) {
    if (n < 0 || n < r || r < 0) return T(0);
    T ret = T(1);
    r = min(r, n - r);
    for (int i = 1; i <= r; ++i) ret *= inv(i) * (n--);
    return ret;
  }
 
  T A(int n, int r) {
    if (n < 0 || n < r || r < 0) return T(0);
    return fact(n) * ifact(n - r);
  }
 
  T CR(int n, int r) {
    if (n < 0 || r < 0) return T(0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
// int const MOD = 998244353;
int const MOD = int(1e9 + 7);
using mint = LazyMontgomeryModInt<MOD>;
Binomial<mint> CC;

vector<mint> mkpow(mint base, int mx) {
  vector<mint> res(mx + 1);
  res[0] = 1;
  for (int i = 1; i <= mx; ++i) {
    res[i] = res[i - 1] * base;
  }
  return res;
}

void solve() {
  int n, c;
  cin >> n >> c;
  if (c == 1) {
    cout << 1 << '\n';
    return;
  }

  // vector<mint> dp(n + 1);
  // dp[0] = 1;
  // for (int i = 1; i <= n; ++i) {
  //   for (int j = 1; j <= i; ++j) {
  //     dp[i] += C(2 * (j - 1), j - 1) / j * dp[i - j] * mint(c) / (c - 1);
  //   }
  // }
  // debug(dp);
  // cout << dp[n] * mint(c - 1).power(n) << '\n';
  // return;

  mint ans = 0;
  mint q = mint(c) / (c - 1) / 2;

  mint A = q - 1;
  mint B = -q;
  mint C = 2 * q - 1;
  mint D = 4 * q * q;
  // auto Choose2 = [&](int x) {
  //   mint cur = mint(1) / 2;
  //   mint res = 1;
  //   for (int i = 0; i < x; ++i) {
  //     res *= cur - i;
  //     res /= i + 1;
  //   }
  //   return res;
  // };
  vector<mint> c2(n + 1);
  vector<mint> p4(n + 1);
  c2[0] = 1;
  p4[0] = 1;
  mint H2 = mint(1) / 2;
  vector<mint> INV(n + 1);
  INV[1] = 1;
  for (int i = 2; i <= n; ++i) {
    INV[i] = -(MOD / i) * INV[MOD % i];
  }
  for (int i = 1; i <= n; ++i) {
    c2[i] = c2[i - 1] * (H2 - (i - 1)) * INV[i];
    p4[i] = p4[i - 1] * (-4);
  }
  mint curP = 1;
  mint DC = D / C;
  mint IC = C.inv();
  for (int coef = 0; coef <= n; ++coef) {
    // debug(coef, Choose2(coef));
    mint here = curP * IC;
    mint there = (n == coef ? 0 : -p4[n - coef] * B * c2[n - coef]);
    if (n == coef) {
      there += A - B;
    }
    ans += here * there;
    curP *= DC;
  }
  debug(ans);

  cout << ans * mint(c - 1).power(n) << '\n';
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t; cin >> t;
  while (t--) solve();

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3456kb

input:

2
3 1
2 2

output:

1
6

result:

ok 2 number(s): "1 6"

Test #2:

score: 0
Accepted
time: 45ms
memory: 3512kb

input:

100000
1 1
4 1
5 5
3 5
1 2
5 3
1 1
3 3
5 2
2 1
4 1
5 5
2 3
4 1
3 3
2 5
3 2
4 3
4 4
3 5
3 1
5 2
2 2
4 2
5 4
1 2
3 1
4 5
2 5
5 3
1 5
5 2
3 2
5 2
4 1
1 3
3 2
4 5
2 1
4 1
2 2
1 1
3 5
4 5
2 3
3 5
2 5
2 4
5 4
2 3
1 1
2 1
4 4
1 5
5 4
1 3
5 4
4 5
1 3
1 1
3 3
2 4
2 4
2 1
5 5
1 3
2 3
4 1
4 3
2 4
2 4
4 2
1 1
1...

output:

1
1
71445
485
2
3543
1
87
252
1
1
71445
15
1
87
45
20
543
2092
485
1
252
6
70
19864
2
1
5725
45
3543
5
252
20
252
1
3
20
5725
1
1
6
1
485
5725
15
485
45
28
19864
15
1
1
2092
5
19864
3
19864
5725
3
1
87
28
28
1
71445
3
15
1
543
28
28
70
1
1
71445
15
2092
3
1
2
15
87
2092
19864
71445
6
252
2092
252
15...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 135ms
memory: 3460kb

input:

100000
94 7867320
84 1294950
35 8570570
72 7050952
23 3907221
95 7482398
58 2363048
44 2234552
50 8809524
37 1061961
19 884367
38 3261675
59 1563189
61 7603994
83 3131714
19 6207284
64 5662457
2 6845951
84 4688192
13 7552675
38 3119650
84 6311084
10 5040332
53 5981961
46 7308176
43 679952
30 2922213...

output:

89775996
781446171
477730749
425095995
683480274
139962614
676040688
83128356
609223622
595772607
273248526
319532567
917638183
692265001
864029162
41269371
365591107
82686713
397805948
799200818
123574040
576607518
6430981
978266206
446712393
201799413
709622262
325465125
319418065
850111422
513285...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 160ms
memory: 3620kb

input:

18170
339 1623650
128 3200275
965 1829351
997 1547816
435 9138202
974 1806376
560 1011936
345 3813921
938 2229395
994 2411734
163 6603389
837 1133885
494 1068385
197 9254017
617 9553650
136 5850880
376 8616282
456 5759693
302 515509
293 2633903
703 7929747
205 5091361
303 5968505
740 872272
246 4106...

output:

461108227
93969714
967535558
286996770
439955818
513651814
367718117
70089455
537505709
989455211
600861203
892954232
899899624
825588888
536671357
118059202
325888233
146830823
953101687
974677182
364272875
482192182
565890497
657497852
297995102
797194699
322320804
744121644
399550079
576261681
42...

result:

ok 18170 numbers

Test #5:

score: 0
Accepted
time: 162ms
memory: 4660kb

input:

176
15130 5219515
54554 814733
69310 3225417
43446 3402232
76425 3330887
34830 2231162
47132 342177
79713 4699528
48406 1562867
21339 5382282
34946 1991698
15555 4141661
52222 2028547
46168 5336018
52551 3781122
23469 1309869
86778 5167485
91984 6969638
28587 3283991
61602 8233067
59908 7918245
6735...

output:

819064610
746619602
481292930
837614851
505712843
251469513
848664626
555419188
788141020
910120658
97942397
995461053
434307672
778837756
976339209
531426099
871529896
875150459
25421918
983527791
281476053
75045944
504006808
866398210
213458087
196306823
900182966
590704432
289412620
28788603
7631...

result:

ok 176 numbers

Test #6:

score: 0
Accepted
time: 148ms
memory: 14360kb

input:

13
931768 3882995
670768 6406509
941049 8590729
817046 5807892
779381 8981570
680279 9990918
396926 9134499
722228 9178753
561021 6110788
686746 6740122
458271 3748820
854144 5848248
548582 8566164

output:

268755962
578943126
92794411
444457165
169780513
804005790
351652199
721238566
102253686
200247655
716047991
465958249
717148868

result:

ok 13 numbers

Test #7:

score: 0
Accepted
time: 146ms
memory: 26352kb

input:

5
1921421 2863210
1611550 9114363
1800313 2824695
1973050 2501730
1312507 7997456

output:

398101698
182608998
453457939
585926383
479930575

result:

ok 5 number(s): "398101698 182608998 453457939 585926383 479930575"

Test #8:

score: 0
Accepted
time: 190ms
memory: 120312kb

input:

1
10000000 5350652

output:

694744897

result:

ok 1 number(s): "694744897"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

1
10000000 1

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 159ms
memory: 115356kb

input:

1
9587024 1628294

output:

983037582

result:

ok 1 number(s): "983037582"

Test #11:

score: 0
Accepted
time: 178ms
memory: 120244kb

input:

1
9994540 7861359

output:

145678106

result:

ok 1 number(s): "145678106"

Test #12:

score: 0
Accepted
time: 173ms
memory: 120304kb

input:

1
9993434 8756421

output:

980562657

result:

ok 1 number(s): "980562657"

Test #13:

score: 0
Accepted
time: 164ms
memory: 120308kb

input:

1
9999982 9427845

output:

977921308

result:

ok 1 number(s): "977921308"