QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#937229#9614. 分治Str_ywr20 1ms3840kbC++144.6kb2025-03-16 12:40:592025-03-16 12:41:07

Judging History

This is the latest submission verdict.

  • [2025-03-16 12:41:07]
  • Judged
  • Verdict: 20
  • Time: 1ms
  • Memory: 3840kb
  • [2025-03-16 12:40:59]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    } return x * f;
}
const int N = 3e5 + 10, mod = 998244353, lm = 200; const ll inf = 1e18; 
int n; typedef pair<ll,ll> pll;
vector<vector<ll>> f[105]; int id[N], tot; 
void ck(ll &x, ll y) {
    if (y > x) x = y;
}
vector<ll> merge(vector<ll> a, vector<ll> b) {
    // return {}; //@@@@@@@@@@@@
    while (a.size() && a.back() < -1e17) a.pop_back();
    while (b.size() && b.back() < -1e17) b.pop_back();
    if (!a.size() || !b.size()) return {};
    for (int i = a.size() - 1; i >= 1; i--) a[i] -= a[i-1];
    for (int i = b.size() - 1; i >= 1; i--) b[i] -= b[i-1];
    for (int i = 2; i < a.size(); i++) assert(a[i-1] >= a[i]);
    for (int i = 2; i < b.size(); i++) assert(b[i-1] >= b[i]);
    vector<ll> c(a.size() + b.size(), -inf); c[0] = a[0] + b[0];
    merge(a.begin() + 1, a.end(), b.begin() + 1, b.end(), c.begin() + 1, greater<ll>());
    for (int i = 1; i < c.size(); i++) c[i] += c[i-1];
    return c;
}
int dfs(int x) {
    if (id[x]) return id[x];
    id[x] = ++tot; int nw = tot; f[nw].resize(x + 1);
    for (int i = 0; i <= x; i++) f[nw][i].resize(min(lm, i) + 2, -inf);
    assert(tot < 100);
    if (x == 1) {
        // f[nw][0] = {0,0}; f[nw][1] = {1,1};
        f[nw][0][0] = 0; f[nw][1][0] = 0; f[nw][1][1] = 1;
        return nw;  
    }
    int ln = (x + 1) >> 1, rn = x >> 1;
    int lc = dfs((x + 1) >> 1); int rc = dfs(x >> 1); 
    vector<vector<ll>> g; g.resize(x + 1);
    for (int i = 0; i <= x; i++) g[i].resize(min(lm, i) + 2, -inf);
    // for (int x = 0; x <= ln; x++) {
    //     ll mx = -inf;
    //     for (auto v : f[lc][x]) mx = max(mx, v);
    //   //  cerr << mx << ' ';
    //     for (int y = 0; y <= rn; y++) { 
    //         for (int i = 0; i <= min(lm, y) + 1; i++) {
    //             ck(g[x+y][i], mx + f[rc][y][i]);
    //         }
    //     }
    // } //cerr << '\n';
vector<ll> a;
    a.clear(); a.resize(rn + 1, -inf);
    for (int y = 0; y <= rn; y++) {
        ll mx = -inf;
        for (auto v : f[rc][y]) mx = max(mx, v);
        a[y] = mx;
        // cerr << mx << ' ';
    } //cerr << '\n';
    for (int i = 0; i <= min(ln, lm) + 1; i++) {
        vector<ll> b; 
        int st = max(0, i - 1); 
        b.resize(ln + 1 - st, -inf); 
        for (int x = st; x <= ln; x++) {
            b[x-st] = f[lc][x][i]; //!!!前面的-inf会影响凸性
        } 
        vector<ll> c = merge(a, b);//{};
        // assert(c.size() <= x);
        for (int j = st; j < min(x + 1, int(c.size())+st); j++) ck(g[j][i], c[j-st]);
    }
    // for (int y = 0; y <= rn; y++) {
    //     ll mx = -inf;
    //     for (auto v : f[rc][y]) mx = max(mx, v);
    //     for (int x = 0; x <= ln; x++) { 
    //         for (int i = 0; i <= min(lm, x) + 1; i++) {
    //             ck(g[x+y][i], mx + f[lc][x][i]);
    //         }
    //     }
    // }
    for (int a = 0; a <= x; a++) {
        for (int b = 0; b <= min(lm, a) + 1; b++){
            for (int k = 0; k <= min(a, b); k++) {
                ck(f[nw][a][b], g[a-k][b-k] + b);
            }
        }
    }
    return nw;
}
ll jc[N], jcn[N];
ll qpow(ll x, ll y) {
	ll ans = 1;
	while (y) {
		if (y & 1) ans = (ans * x) % mod;
		x = (x * x) % mod; y >>= 1;
	} return ans;
} string s;
namespace sub1{
	int n;
	ll C(int n, int m) {
		if (n < 0 || m < 0 || m > n) return 0;
		return jc[n] * jcn[m] % mod * jcn[n-m] % mod;
	}
	void solve() {
		n = s.size(); jc[0] = jcn[0] = 1;
		for (int i = 1; i < N; i++) jc[i] = (jc[i-1] * i) % mod;
		jcn[N-1] = qpow(jc[N-1], mod - 2);
		for (int i = N - 2; i >= 1; i--) {
			jcn[i] = (jcn[i+1] * (i + 1)) % mod;
		}
		ll sum = 0; n--;
		for (int m = 1; m <= n; m++) {
			for (int i = 0; i <= n; i++) {
				for (int j = 1; j <= i + 1 && j * m <= n; j++) {
					sum = (sum + ((j & 1) ? 1 : -1) * C(i + 1, j) * C(n - j * m, i)) % mod; 
				}
			}
		} sum += qpow(2, n);
		sum = (sum % mod + mod) % mod;
		cout << sum;
	}
}
int main() {
     cin >> s; bool fl = 1;
    for (int i = 0; i < s.size(); i++) {
        n = (n << 1) | (s[i] - '0');
        fl &= (!i || s[i] == '0');
    }
    if ((fl && n > 128)) {
    	sub1::solve(); return 0;
	}
    int rt = dfs(n);
    ll ans = -inf;
    for (int i = 0; i <= min(lm, n); i++) ck(ans, f[rt][n][i]);
    ans = (ans % mod + mod) % mod;
    cout << 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: 0ms
memory: 3712kb

input:

110

output:

15

result:

ok 1 number(s): "15"

Test #2:

score: 10
Accepted
time: 1ms
memory: 3712kb

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: 3584kb

input:

111110

output:

198

result:

ok 1 number(s): "198"

Test #4:

score: 10
Accepted
time: 1ms
memory: 3840kb

input:

1001001

output:

253

result:

ok 1 number(s): "253"

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #5:

score: 0
Time Limit Exceeded

input:

10100011000100111

output:


result:


Subtask #4:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

output:

282173455

result:

wrong answer 1st numbers differ - expected: '412796008', found: '282173455'

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #5:

0%

Subtask #8:

score: 0
Skipped

Dependency #6:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%