QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440005#6740. Functionsuibian_xiaozhao#WA 757ms3864kbC++174.2kb2024-06-12 22:48:142024-06-12 22:48:15

Judging History

你现在查看的是最新测评结果

  • [2024-06-12 22:48:15]
  • 评测
  • 测评结果:WA
  • 用时:757ms
  • 内存:3864kb
  • [2024-06-12 22:48:14]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <cassert>
#include <cctype>
#include <ciso646>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <random>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#endif

#define FAST ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15)
#define Tsolve() int T; cin >> T; while (T --) solve()
#define endl '\n'
#define em(x) (x.empty())
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define Fill(x,a) memset(x,a,sizeof(x))
#define cpy(a,b) memcpy(a,b,sizeof(a))
#define pbk push_back
#define mpr make_pair
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define fi first
#define se second
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
//-----------------------precompiler--------------------
using ll = long long;
using i64 = long long;
using pii = std::pair<int,int>;
using VI = std::vector<int>;
using namespace std;
template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const pair<typC,typD> &a) { return cout<<a.first<<' '<<a.second; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const vector<pair<typC,typD>> &a) { for (auto &x:a) cout<<x<<'\n'; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
//-----------------------debug-----------------------
#ifndef ONLINE_JUDGE
#include "D:/OneDrive-Personal/OneDrive/my-acm-template/my_header/debug.h"
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dbg(...) {}
#endif
//-----------------------constant-----------------------
const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const int mod = 998244353;
ll gcd(ll a,ll b) { return b?gcd(b, a%b):a;}
//-----------------------variable-----------------------
int n;

//-----------------------function-----------------------

ll get(int st, int ed, int p) {
    st += (p - st % p) % p;
    if (st > ed) return 0;
    return (ed - st) / p + 1;
}

void solve() {
    cin >> n;
    int m = min(n, 1000);
    vector<ll> f(m + 1, 0);
    f[1] = 1;
    for (int i = 2; i <= m; i ++) {
        for (int k = 2; k <= i; k ++) {
            int t = (i / k);
            f[i] = (f[i] + f[t]) % mod;
        }
        f[i] = (f[i] + 1) % mod;
    }
    
    if (m == n) {
        cout << f[n] << endl;
        return;
    }
    
    vector<ll> g(n / 1001 + 10, -1);
    
    function<ll(int)> dfs = [&](int u) {
        if (u >= n / 1001 + 1) {
            return f[n / u];
        }
        if (g[u] >= 0) return g[u];
        ll res = 1;
        for (int k = 2; (ll)k * u <= n / 1001; k ++) {
            res = (res + dfs(k * u)) % mod;
        }
        for (int i = 1000; i >= 1; i --) {
            if (n / i <= 20210926) {
                res = (res + get(n / (i + 1) + 1, n / i, u) * f[i]) % mod;
            }
            else {
                res = (res + get(n / (i + 1) + 1, 20210926, u) * f[i]) % mod;
                break;
            }
        }
        return g[u] = res;
    };
    cout << dfs(1) << endl;
}
int main() {
    FAST;
    // Tsolve();
    solve();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3588kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

100

output:

949

result:

ok 1 number(s): "949"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

10

output:

19

result:

ok 1 number(s): "19"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

1000

output:

48614

result:

ok 1 number(s): "48614"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10000

output:

2602393

result:

ok 1 number(s): "2602393"

Test #7:

score: 0
Accepted
time: 3ms
memory: 3604kb

input:

100000

output:

139804054

result:

ok 1 number(s): "139804054"

Test #8:

score: 0
Accepted
time: 10ms
memory: 3764kb

input:

1000000

output:

521718285

result:

ok 1 number(s): "521718285"

Test #9:

score: 0
Accepted
time: 78ms
memory: 3864kb

input:

10000000

output:

503104917

result:

ok 1 number(s): "503104917"

Test #10:

score: -100
Wrong Answer
time: 757ms
memory: 3828kb

input:

100000000

output:

762331250

result:

wrong answer 1st numbers differ - expected: '198815604', found: '762331250'