QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141001#6740. FunctionUFRJ#TL 866ms3704kbC++20736b2023-08-17 05:23:522023-08-17 05:23:56

Judging History

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

  • [2023-08-17 05:23:56]
  • 评测
  • 测评结果:TL
  • 用时:866ms
  • 内存:3704kb
  • [2023-08-17 05:23:52]
  • 提交

answer

#include<bits/stdc++.h>

using lint = int64_t;
using namespace std;
const int mod = 998244353;
const int lim = 20210926;

int main(void) {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  cin>>n;
  vector<pair<int, int>>v;
  for(int a = 1, b; a <= n; a = b + 1) {
    b = n / (n  /  a);
    v.push_back({a, b});
  }
  reverse(v.begin(), v.end());
  int m = int(v.size());
  vector<lint>dp(m, 1);
  for(int i=0;i<m;i++){
    auto [a, b] = v[i];
    for(int j=i+1;j<m;j++){
      auto [c, d] = v[j];
      int l = (a + c - 1) / c, r = (b / c);
      int cnt = (l > lim) ? 0 : min(r, lim) - l + 1;
      dp[j] += cnt * dp[i] % mod;
      dp[j] %= mod;
    }
  }
  cout<<dp[m-1]<<"\n";

  return 0;
}

详细

Test #1:

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

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

100

output:

949

result:

ok 1 number(s): "949"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

10

output:

19

result:

ok 1 number(s): "19"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

1000

output:

48614

result:

ok 1 number(s): "48614"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

10000

output:

2602393

result:

ok 1 number(s): "2602393"

Test #7:

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

input:

100000

output:

139804054

result:

ok 1 number(s): "139804054"

Test #8:

score: 0
Accepted
time: 7ms
memory: 3560kb

input:

1000000

output:

521718285

result:

ok 1 number(s): "521718285"

Test #9:

score: 0
Accepted
time: 84ms
memory: 3580kb

input:

10000000

output:

503104917

result:

ok 1 number(s): "503104917"

Test #10:

score: 0
Accepted
time: 866ms
memory: 3704kb

input:

100000000

output:

198815604

result:

ok 1 number(s): "198815604"

Test #11:

score: -100
Time Limit Exceeded

input:

1000000000

output:


result: