QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #722525 | #9614. 分治 | TheZone | 100 ✓ | 1737ms | 20328kb | C++20 | 5.8kb | 2024-11-07 19:24:26 | 2024-11-07 19:24:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, mod = 998244353, B = 450;
struct qry
{
int m, n, c, a;
qry(int m0 = 0, int n0 = 0, int c0 = 0, int a0 = 0)
{
m = m0;
n = n0;
c = c0;
a = a0;
}
};
qry Q[N * 3];
int cnt;
char s[N];
int a[N], fac[N], inv[N], pw[N], len[N], qwq[N], pre[N];
int f[N], g[N];
int qpow(int x, int y)
{
int ans = 1;
while(y)
{
if(y & 1)
ans = (ll)ans * x % mod;
x = (ll)x * x % mod;
y >>= 1;
}
return ans;
}
void prep(int n)
{
int i;
fac[0] = 1;
for(i = 1; i <= n; i++)
fac[i] = (ll)fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for(i = n; i >= 1; i--)
inv[i - 1] = (ll)inv[i] * i % mod;
pw[0] = 1;
for(i = 1; i <= n; i++)
pw[i] = 2ll * pw[i - 1] % mod;
}
int C(int x, int y)
{
return (x < y || y < 0) ? 0 : ((ll)fac[x] * inv[y] % mod * inv[x - y] % mod);
}
int F(int m, int n)
{
int i, j, ans = 0, tmp;
for(i = m; i <= n; i++)
for(j = 1; j <= n / i; j++)
{
tmp = (ll)C(n - (i - 1) * j, j) * pw[n - i * j] % mod;
if(!(j & 1))
tmp = mod - tmp;
ans = (ans + tmp) % mod;
}
return ans;
}
int main()
{
int n, i, j, ans = 0, g, tmp, d, q;
scanf("%s", s + 1);
n = strlen(s + 1);
for(i = 1; i <= n; i++)
a[i] = s[n + 1 - i] - '0';
prep(n);
Q[++cnt] = qry(1, n, 1);
Q[++cnt] = qry(1, n - 1, mod - 1);
qwq[n] = len[n] = 1;
for(i = 1; i <= n; i++)
pre[i] = (a[i] ? i : pre[i - 1]);
if(pre[n - 1])
{
g = n - pre[n - 1] + 1;
ans = (ans + (ll)g * pw[pre[n - 1] - 1]) % mod;
d = n + 1;
q = pre[n - 1] - 1;
if(g < d)
Q[++cnt] = qry(g + 1, d, 1);
if(g < d - 1)
Q[++cnt] = qry(g + 1, d - 1, mod - 2);
if(g < q)
Q[++cnt] = qry(g + 1, q, 1);
}
for(i = n - 1; i >= 1; i--)
{
if(i < n - 1 && a[i + 1] && pre[i])
{
// calc
g = max(qwq[i + 1], i - pre[i] + 1) + 1;
ans = (ans + (ll)g * pw[pre[i] - 1]) % mod;
d = i + 1;
q = pre[i] - 1;
if(g < d)
Q[++cnt] = qry(g + 1, d, 1);
if(g < d - 1)
Q[++cnt] = qry(g + 1, d - 1, mod - 2);
if(g < q)
Q[++cnt] = qry(g + 1, q, 1);
}
len[i] = (a[i] ? 0 : len[i + 1] + 1);
qwq[i] = max(qwq[i + 1], len[i]);
}
// cerr << cnt << endl;
++n;
for(i = 1; i <= B; i++) // fixed i <= B, j > B
{
for(j = 1; j <= n; j++)
{
f[j] = 2ll * f[j - 1] % mod;
if(j > i)
f[j] = (f[j] + mod - f[j - i]) % mod;
if(j >= (B + 1) * i)
{
tmp = (ll)pw[j - i * (B + 1)] * C(j - i - (i - 1) * B, B) % mod;
if(B & 1)
tmp = mod - tmp;
f[j] = (f[j] + tmp) % mod;
}
}
for(j = 1; j <= cnt; j++)
if(i >= Q[j].m)
Q[j].a = (Q[j].a + f[Q[j].n]) % mod;
}
for(i = 1; i <= B; i++) // fixed j <= B
{
for(j = 1; j <= n; j++)
{
if(j < i)
{
f[j] = 0;
continue;
}
f[j] = ((ll)C(j, i) * pw[j - i] + f[j - i]) % mod;
}
if(!(i & 1))
for(j = 1; j <= n; j++)
f[j] = (mod - f[j]) % mod;
for(j = 1; j <= cnt; j++)
if((ll)i * Q[j].m <= Q[j].n)
Q[j].a = (Q[j].a + f[Q[j].n - i * (Q[j].m - 1)]) % mod;
}
for(i = 1; i <= cnt; i++)
ans = (ans + (ll)Q[i].a * Q[i].c) % mod;
printf("%d\n", ans);
return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, mod = 998244353, B = 450;
struct qry
{
int m, n, c, a;
qry(int m0 = 0, int n0 = 0, int c0 = 0, int a0 = 0)
{
m = m0;
n = n0;
c = c0;
a = a0;
}
};
qry Q[N * 3];
int cnt;
char s[N];
int a[N], fac[N], inv[N], pw[N], len[N], qwq[N], pre[N];
int f[N], g[N];
int qpow(int x, int y)
{
int ans = 1;
while(y)
{
if(y & 1)
ans = (ll)ans * x % mod;
x = (ll)x * x % mod;
y >>= 1;
}
return ans;
}
void prep(int n)
{
int i;
fac[0] = 1;
for(i = 1; i <= n; i++)
fac[i] = (ll)fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for(i = n; i >= 1; i--)
inv[i - 1] = (ll)inv[i] * i % mod;
pw[0] = 1;
for(i = 1; i <= n; i++)
pw[i] = 2ll * pw[i - 1] % mod;
}
int C(int x, int y)
{
return (x < y || y < 0) ? 0 : ((ll)fac[x] * inv[y] % mod * inv[x - y] % mod);
}
int F(int m, int n)
{
int i, j, ans = 0, tmp;
for(i = m; i <= n; i++)
for(j = 1; j <= n / i; j++)
{
tmp = (ll)C(n - (i - 1) * j, j) * pw[n - i * j] % mod;
if(!(j & 1))
tmp = mod - tmp;
ans = (ans + tmp) % mod;
}
return ans;
}
int main()
{
int n, i, j, ans = 0, g, tmp, d, q;
scanf("%s", s + 1);
n = strlen(s + 1);
for(i = 1; i <= n; i++)
a[i] = s[n + 1 - i] - '0';
prep(n);
Q[++cnt] = qry(1, n, 1);
Q[++cnt] = qry(1, n - 1, mod - 1);
qwq[n] = len[n] = 1;
for(i = 1; i <= n; i++)
pre[i] = (a[i] ? i : pre[i - 1]);
if(pre[n - 1])
{
g = n - pre[n - 1] + 1;
ans = (ans + (ll)g * pw[pre[n - 1] - 1]) % mod;
d = n + 1;
q = pre[n - 1] - 1;
if(g < d)
Q[++cnt] = qry(g + 1, d, 1);
if(g < d - 1)
Q[++cnt] = qry(g + 1, d - 1, mod - 2);
if(g < q)
Q[++cnt] = qry(g + 1, q, 1);
}
for(i = n - 1; i >= 1; i--)
{
if(i < n - 1 && a[i + 1] && pre[i])
{
// calc
g = max(qwq[i + 1], i - pre[i] + 1) + 1;
ans = (ans + (ll)g * pw[pre[i] - 1]) % mod;
d = i + 1;
q = pre[i] - 1;
if(g < d)
Q[++cnt] = qry(g + 1, d, 1);
if(g < d - 1)
Q[++cnt] = qry(g + 1, d - 1, mod - 2);
if(g < q)
Q[++cnt] = qry(g + 1, q, 1);
}
len[i] = (a[i] ? 0 : len[i + 1] + 1);
qwq[i] = max(qwq[i + 1], len[i]);
}
// cerr << cnt << endl;
++n;
for(i = 1; i <= B; i++) // fixed i <= B, j > B
{
for(j = 1; j <= n; j++)
{
f[j] = 2ll * f[j - 1] % mod;
if(j > i)
f[j] = (f[j] + mod - f[j - i]) % mod;
if(j >= (B + 1) * i)
{
tmp = (ll)pw[j - i * (B + 1)] * C(j - i - (i - 1) * B, B) % mod;
if(B & 1)
tmp = mod - tmp;
f[j] = (f[j] + tmp) % mod;
}
}
for(j = 1; j <= cnt; j++)
printf("%d\n", ans);
return 0;
}*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 3ms
memory: 19500kb
input:
110
output:
15
result:
ok 1 number(s): "15"
Test #2:
score: 10
Accepted
time: 0ms
memory: 18864kb
input:
101
output:
12
result:
ok 1 number(s): "12"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 10
Accepted
time: 0ms
memory: 18452kb
input:
111110
output:
198
result:
ok 1 number(s): "198"
Test #4:
score: 10
Accepted
time: 3ms
memory: 20012kb
input:
1001001
output:
253
result:
ok 1 number(s): "253"
Subtask #3:
score: 20
Accepted
Dependency #2:
100%
Accepted
Test #5:
score: 20
Accepted
time: 0ms
memory: 19648kb
input:
10100011000100111
output:
386882
result:
ok 1 number(s): "386882"
Test #6:
score: 20
Accepted
time: 2ms
memory: 18276kb
input:
111010011111010110
output:
1107742
result:
ok 1 number(s): "1107742"
Subtask #4:
score: 5
Accepted
Test #7:
score: 5
Accepted
time: 0ms
memory: 18388kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
412796008
result:
ok 1 number(s): "412796008"
Test #8:
score: 5
Accepted
time: 0ms
memory: 18728kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
818656648
result:
ok 1 number(s): "818656648"
Subtask #5:
score: 5
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #9:
score: 5
Accepted
time: 0ms
memory: 20144kb
input:
10000000100000010010011110111101101110000000000001100000011000111111010011010101010000101001110110010001100110000110111101000101001111101111001010001001011101011111010000100010111100110000001101111
output:
703266161
result:
ok 1 number(s): "703266161"
Test #10:
score: 5
Accepted
time: 0ms
memory: 19124kb
input:
110100000100001000101000010010101000110111101010110000101001001100100111000011100101110110010000001111010011101001111110110010001110011101001111010101100100010011101010101111111111010110001100100110
output:
330527406
result:
ok 1 number(s): "330527406"
Subtask #6:
score: 5
Accepted
Dependency #4:
100%
Accepted
Test #11:
score: 5
Accepted
time: 6ms
memory: 18900kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
340672883
result:
ok 1 number(s): "340672883"
Test #12:
score: 5
Accepted
time: 10ms
memory: 19748kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
555946758
result:
ok 1 number(s): "555946758"
Subtask #7:
score: 10
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #13:
score: 10
Accepted
time: 17ms
memory: 19468kb
input:
110011100110101000000110101010111111001101101011010110100100110010111110110110000111011001110000101111110111011111000110001011011011101100001100100011010010111111010110010000101001001000100001100100000001000111110100000101001011100001100011011110110101101111110011100111001010001010001111001110111100...
output:
324123594
result:
ok 1 number(s): "324123594"
Test #14:
score: 10
Accepted
time: 13ms
memory: 19964kb
input:
110100110100110110001011100000011010000010000101100100001101100100110000101000111001111100001110001001101010110010111101000100111010001011001110101010001101111010000011000010110011000011100101110100000001011100111000101111010100001101011010100101110000010001101001000100111001101101110000101101011011...
output:
209285599
result:
ok 1 number(s): "209285599"
Subtask #8:
score: 10
Accepted
Dependency #6:
100%
Accepted
Test #15:
score: 10
Accepted
time: 730ms
memory: 19768kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
468567454
result:
ok 1 number(s): "468567454"
Test #16:
score: 10
Accepted
time: 1269ms
memory: 19680kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12752860
result:
ok 1 number(s): "12752860"
Subtask #9:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Dependency #8:
100%
Accepted
Test #17:
score: 25
Accepted
time: 1737ms
memory: 19576kb
input:
101100010100101011010110001111101101001010000111001111000100110110010111101100011011011111010110000000011110000010100110111110110001101001101101001110101110011000010100100101000011000010000101011001011011000000100111011110100010000100001101011110100101110000100011000101100000111111100110000111010000...
output:
711712397
result:
ok 1 number(s): "711712397"
Test #18:
score: 25
Accepted
time: 1727ms
memory: 19636kb
input:
110101110100100010101100000110000110101101111100110011100111111110000101111001101001111000110111100111110111010001000010111111110000001001011110101110001011010010010011101000110110000110110101000100111000100110101111011101111101000010000101001001000010011011000011001100111111011000111000010000100111...
output:
171668334
result:
ok 1 number(s): "171668334"
Test #19:
score: 25
Accepted
time: 1335ms
memory: 19580kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
397846555
result:
ok 1 number(s): "397846555"
Test #20:
score: 25
Accepted
time: 1505ms
memory: 20328kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
592103795
result:
ok 1 number(s): "592103795"
Extra Test:
score: 0
Extra Test Passed