QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#230448 | #7634. Cards | ucup-team1191# | AC ✓ | 2914ms | 24780kb | C++20 | 6.3kb | 2023-10-28 18:47:47 | 2023-10-28 19:30:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
// если модуль подается на вход, убрать все <> и раскомментировать нужные строки
using uint = unsigned int;
using ull = unsigned long long;
template <uint MD> struct ModInt {
using M = ModInt;
// static int MD;
uint v;
ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
M& set_v(uint _v) {
v = (_v < MD) ? _v : _v - MD;
return *this;
}
explicit operator bool() const { return v != 0; }
M operator-() const { return M() - *this; }
M operator+(const M& r) const { return M().set_v(v + r.v); }
M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
M operator*(const M& r) const { return M().set_v(uint((ull)v * r.v % MD)); }
M operator/(const M& r) const { return *this * r.inv(); }
M& operator+=(const M& r) { return *this = *this + r; }
M& operator-=(const M& r) { return *this = *this - r; }
M& operator*=(const M& r) { return *this = *this * r; }
M& operator/=(const M& r) { return *this = *this / r; }
bool operator==(const M& r) const { return v == r.v; }
bool operator!=(const M& r) const { return v != r.v; }
M inv() const;
friend istream& operator>>(istream& is, M& r) { ll x; is >> x; r = M(x); return is; }
friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
template<uint MD>
ModInt<MD> pow(ModInt<MD> x, ll n) {
ModInt<MD> r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
template<uint MD>
ModInt<MD> ModInt<MD>::inv() const { return pow(*this, MD - 2); }
// or copy egcd and {return egcd(MD, v, 1).second;}
// if MD is from input
// this line is necessary, read later as you wish
// int ModInt::MD;
const int MOD = 998'244'353;
using Mint = ModInt<MOD>;
// using Mint = double;
#define V vector
void nft(bool type, V<Mint>& a) {
Mint G = 3;
int n = int(a.size()), s = 0;
while ((1 << s) < n) s++;
assert(1 << s == n);
static V<Mint> ep, iep;
while (int(ep.size()) <= s) {
ep.push_back(pow(G, Mint(-1).v / (1 << ep.size())));
iep.push_back(ep.back().inv());
}
V<Mint> b(n);
for (int i = 1; i <= s; i++) {
int w = 1 << (s - i);
Mint base = type ? iep[i] : ep[i], now = 1;
for (int y = 0; y < n / 2; y += w) {
for (int x = 0; x < w; x++) {
auto l = a[y << 1 | x];
auto r = now * a[y << 1 | x | w];
b[y | x] = l + r;
b[y | x | n >> 1] = l - r;
}
now *= base;
}
swap(a, b);
}
}
V<Mint> multiply_nft(const V<Mint>& a, const V<Mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (min(n, m) <= 50) {
V<Mint> ans(n + m - 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) ans[i + j] += a[i] * b[j];
return ans;
}
int lg = 0;
while ((1 << lg) < n + m - 1) lg++;
int z = 1 << lg;
auto a2 = a, b2 = b;
a2.resize(z);
b2.resize(z);
nft(false, a2);
nft(false, b2);
for (int i = 0; i < z; i++) a2[i] *= b2[i];
nft(true, a2);
a2.resize(n + m - 1);
Mint iz = Mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
return a2;
}
struct rval {
vector<Mint> values;
};
const int M = 1e5 + 239;
vector<Mint> base;
vector<Mint> pw[M];
void obtain(int s) {
if (!pw[s].empty()) {
return;
}
obtain(s / 2);
obtain((s + 1) / 2);
pw[s] = multiply_nft(pw[s / 2], pw[(s + 1) / 2]);
}
vector<Mint> func(int x1, int y1, int x2, int y2, vector<Mint>& val) {
vector<Mint> ans(y2 + 1, 0);
if (x2 == x1 + 1) {
for (int y = 0; y <= y2; y++) {
for (int dy = -2; dy <= 2; dy++) {
if (y + dy >= 0 && y + dy <= y1) {
ans[y] += val[y + dy] * base[2 - dy];
}
}
}
return ans;
}
int len = (x2 - x1);
if (y2 >= 2 * len) {
obtain(len);
auto res = multiply_nft(val, pw[len]);
for (int i = 2 * len; i <= y2; i++) {
if (i + 2 * len < (int)res.size()) {
ans[i] = res[i + 2 * len];
}
}
}
int mid = (x1 + x2) / 2;
int r_len = min(y2, 2 * len - 1);
int mid_len = r_len + 2 * (x2 - mid);
int l_len = min(y1, mid_len + 2 * (mid - x1));
val.resize(l_len + 1);
auto midvals = func(x1, l_len, mid, mid_len, val);
auto rvals = func(mid, mid_len, x2, r_len, midvals);
for (int i = 0; i <= r_len; i++) {
ans[i] = rvals[i];
}
return ans;
}
Mint slow(int n, int m) {
vector<Mint> dp(n + 2 * m + 1, 0);
dp[n] = 1;
for (int it = 0; it < m; it++) {
vector<Mint> new_dp(dp.size(), 0);
for (int y = 0; y < (int)dp.size(); y++) {
for (int dy = -2; dy <= 2; dy++) {
if (y + dy >= 0 && y + dy < (int)new_dp.size()) {
new_dp[y + dy] += dp[y] * base[2 + dy];
}
}
}
swap(dp, new_dp);
}
Mint ans = 0;
for (const auto& t : dp) {
ans += t;
}
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
if (m == 0) {
cout << "1\n";
return;
}
base.resize(5);
Mint s = 0;
for (int i = 0; i < 5; i++) {
cin >> base[i];
s += base[i];
}
for (int i = 0; i < 5; i++) {
base[i] /= s;
}
#ifdef ONPC
if ((ll)(n + 2 * m) * (n + 2 * m) <= 1000000) {
cout << slow(n, m) << "\n";
}
#endif
pw[1] = base;
vector<Mint> vals(n + 1, 0);
vals[n] = 1;
auto res = func(0, n, m, n + 2 * m, vals);
Mint ans = 0;
for (const auto& t : res) {
ans += t;
}
cout << ans << "\n";
}
int main() {
#ifdef ONPC
freopen("input", "r", stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
cerr << TIME << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6328kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 2801ms
memory: 22420kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 2805ms
memory: 22312kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 2801ms
memory: 22248kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 1ms
memory: 6388kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1304ms
memory: 13364kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 2ms
memory: 6244kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 2765ms
memory: 22296kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 2904ms
memory: 24752kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 2848ms
memory: 23752kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 2909ms
memory: 24780kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 2835ms
memory: 22240kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 2914ms
memory: 24772kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 1ms
memory: 6336kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 172ms
memory: 7368kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 186ms
memory: 7692kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 155ms
memory: 7632kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed