QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#141000#6740. FunctionUFRJ#WA 830ms3652kbC++20640b2023-08-17 05:18:292023-08-17 05:18:31

Judging History

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

  • [2023-08-17 05:18:31]
  • 评测
  • 测评结果:WA
  • 用时:830ms
  • 内存:3652kb
  • [2023-08-17 05:18:29]
  • 提交

answer

#include<bits/stdc++.h>

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

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];
      dp[j] += (b / c - ( (a + c - 1) / c ) + 1) * dp[i] % mod;
      dp[j] %= mod;
    }
  }
  cout<<dp[m-1]<<"\n";

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3488kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

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

input:

100

output:

949

result:

ok 1 number(s): "949"

Test #4:

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

input:

10

output:

19

result:

ok 1 number(s): "19"

Test #5:

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

input:

1000

output:

48614

result:

ok 1 number(s): "48614"

Test #6:

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

input:

10000

output:

2602393

result:

ok 1 number(s): "2602393"

Test #7:

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

input:

100000

output:

139804054

result:

ok 1 number(s): "139804054"

Test #8:

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

input:

1000000

output:

521718285

result:

ok 1 number(s): "521718285"

Test #9:

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

input:

10000000

output:

503104917

result:

ok 1 number(s): "503104917"

Test #10:

score: -100
Wrong Answer
time: 830ms
memory: 3652kb

input:

100000000

output:

388373010

result:

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