QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19505 | #1423. Bin | qingaodong | TL | 480ms | 5480kb | C++20 | 5.1kb | 2022-02-02 10:55:14 | 2022-05-06 05:36:14 |
Judging History
answer
#pragma GCC optimize("O3")
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <climits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
const int M = 1e6 + 239;
const int MOD = 998244353;
const ll MOD2 = (ll)MOD * (ll)MOD;
int mul(long long a, int b) {
return a * b % MOD;
}
int power(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
b >>= 1;
}
return ans;
}
const int wp = power(3, 7 * 17); // w^(2^23) == 1
namespace fft {
int k;
vector<int> rev;
vector<int> st;
void fft(vector<int> &a) {
for (int i = 0; i < k; i++)
if (rev[i] < i)
swap(a[rev[i]], a[i]);
int w, wn, ai, aj;
for (int s = 1, it = 0; s < k; s <<= 1, it++) {
wn = st[it];
for (int l = 0; l < k; l += s + s) {
w = 1;
for (int i = l, j = l + s; i < l + s; i++, j++) {
ai = a[i];
aj = 1LL * w * a[j] % MOD; // or st[((1 << 22) / s) * (i - l)]
a[i] = ai + aj;
if (a[i] >= MOD)
a[i] -= MOD;
a[j] = ai - aj;
if (a[j] < 0)
a[j] += MOD;
w = 1LL * w * wn % MOD;
}
}
}
}
vector<int> mult(vector<int> a) {
k = 1;
while (k < (int)a.size() + (int)a.size() - 1)
k <<= 1;
if (st.size() != k)
{
st.clear();
st.push_back(power(wp, ((1 << 22) / k)));
for (int t = 1; t < k; t <<= 1)
st.push_back(1LL * st.back() * st.back() % MOD);
reverse(st.begin(), st.end());
rev.clear();
rev.resize(k);
rev[0] = 0;
for (int i = 1; i < k; i++)
{
if (i & 1)
rev[i] = rev[i - 1] + (k >> 1);
else
rev[i] = rev[i >> 1] >> 1;
}
}
a.resize(k);
fft(a);
//b.resize(k);
//fft(b);
vector<int> pr(k);
for (int i = 0; i < k; i++)
pr[i] = 1LL * a[i] * a[i] % MOD;
fft(pr);
reverse(pr.begin() + 1, pr.end());
int inv_k = power(k, MOD - 2);
for (int i = 0; i < k; i++)
pr[i] = 1LL * pr[i] * inv_k % MOD;
while (pr.back() == 0)
pr.pop_back(); // can be removed
return pr;
}
}
/*int func(int l1, int r1, int l2, int r2, int n)
{
if (n < l1 + l2)
return 0;
if (n >= r1 + r2 - 1)
return 0;
if (r1 - l1 == 1)
return 1LL * dp[l1] * dp[n - l1] % MOD;
if (r2 - l2 == 1)
return 1LL * dp[n - l2] * dp[l2] % MOD;
int ans = 0;
int m1 = (l1 + r1) / 2;
int m2 = (l2 + r2) / 2;
ans += func(l1, m1, l2, m2, n);
ans += func(m1, r1, l2, m2, n);
if (ans >= MOD)
ans -= MOD;
ans += func(l1, m1, m2, r2, n);
if (ans >= MOD)
ans -= MOD;
ans += func(m1, r1, m2, r2, n);
if (ans >= MOD)
ans -= MOD;
return ans;
}*/
vector<int> dp;
vector<int> pr;
int n, k;
const int MG = 15000;
int main() {
#ifdef ONPC
freopen("input", "r", stdin);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
dp.resize(2);
dp[0] = 0;
dp[1] = 1;
int g = 0;
for (int i = 2; i <= n; i++)
{
if (i % MG == 0)
{
//cerr << i << "!\n";
g = i;
pr = fft::mult(dp);
}
dp.push_back(0);
ll ci = 0;
if (i < (int)pr.size())
ci = pr[i];
for (int j = g; j < i; j++)
{
ll add = (ll)dp[j] * dp[i - j];
if (i - j < g)
{
add += add;
if (add >= MOD2)
add -= MOD2;
}
ci += add;
if (ci >= MOD2)
ci -= MOD2;
}
ll sum = 0;
for (int x = max(0, (i / 2) - k); x <= min(i - 1, (i / 2) + k); x++)
if (abs(x - (i - x)) <= k)
{
sum += (ll)dp[x] * dp[i - x];
if (sum >= MOD2)
sum -= MOD2;
}
dp[i] = ((ci % MOD) + (sum % MOD));
if (dp[i] >= MOD)
dp[i] -= MOD;
if (dp[i] & 1)
dp[i] += MOD;
dp[i] /= 2;
}
cout << dp[n] << "\n";
//cerr << TIME << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3616kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
3 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
4 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 1
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
4 2
output:
5
result:
ok 1 number(s): "5"
Test #7:
score: 0
Accepted
time: 3ms
memory: 3652kb
input:
6 2
output:
23
result:
ok 1 number(s): "23"
Test #8:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
7 42
output:
132
result:
ok 1 number(s): "132"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
10 1
output:
400
result:
ok 1 number(s): "400"
Test #10:
score: 0
Accepted
time: 3ms
memory: 3560kb
input:
13 4
output:
42003
result:
ok 1 number(s): "42003"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
239 17
output:
385818773
result:
ok 1 number(s): "385818773"
Test #12:
score: 0
Accepted
time: 480ms
memory: 5480kb
input:
50216 58
output:
744498776
result:
ok 1 number(s): "744498776"
Test #13:
score: -100
Time Limit Exceeded
input:
787788 78