QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113921 | #6637. Perfect Strings | ITMO_pengzoo | AC ✓ | 190ms | 120312kb | C++20 | 8.0kb | 2023-06-20 02:19:41 | 2023-06-20 02:19:41 |
Judging History
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"