QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#478483#8487. Scooter numbersrania__#TL 622ms9400kbC++202.0kb2024-07-15 01:10:522024-07-15 01:10:53

Judging History

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

  • [2024-07-15 01:10:53]
  • 评测
  • 测评结果:TL
  • 用时:622ms
  • 内存:9400kb
  • [2024-07-15 01:10:52]
  • 提交

answer

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 7, P1 = 31, P2 = 37, mod = 1e9 + 7;

int mul(int a, int b) { return (1LL * a * b) % mod; }

int add(int a, int b) {
  a = (a + mod) % mod;
  b = (b + mod) % mod;
  return (a + b) % mod;
}

int fp(int b, int p) {
  if (b == 1 or p == 0) return 1;

  int ret = fp(b, p >> 1);
  ret = mul(ret, ret);

  if (p & 1) ret = mul(ret, b);

  return ret;
}

ll modInv(ll n) { return fp(n, mod - 2); }

ll fact[N], inv[N];

void pre() {
  fact[0] = inv[0] = 1;
  for (ll i = 1; i < N; i++)
    fact[i] = (fact[i - 1] * i) % mod, inv[i] = fp(fact[i], mod - 2);
}

ll nCr(ll n, ll r) { return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod; }

ll nPr(ll n, ll r) { return ((fact[n] * inv[n - r])) % mod; }
int dp[1001][1001], tmp;
int solve(int last, int rem) {
  if (rem == 0) {
    return (last + 1 >= tmp && last !=0);
  }
  int &ret = dp[last][rem];
  if (~ret) return ret;
  ret = 0;
  // take
  if (last >= tmp - 1) {
    for (int i = last; i <= rem; i++) {
      if (i == tmp) continue;
      if ( i == 0)
      continue;
      ret = add(ret, solve(i, rem - i));
    }
  }
  else
  {
  	for (int i = last; i <= min(rem , last+1); i++) {
      if(i == 0)
      continue;
      ret = add(ret, solve(i, rem - i));
    }
  }
  return ret;
}
void doWork() {
  int n;
  cin >> n;
  tmp = 46;
  ll ans = 0;
  while (tmp > 0) {
    memset(dp, -1, sizeof dp);
    ans = add(ans, mul(solve(0, n), tmp));
    //cout <<tmp  << " " << ans << endl;
    tmp--;
  }
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    doWork();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 8368kb

input:

1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3

output:

6

result:

ok 1 number(s): "6"

Test #3:

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

input:

2

output:

3

result:

ok 1 number(s): "3"

Test #4:

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

input:

5

output:

14

result:

ok 1 number(s): "14"

Test #5:

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

input:

7

output:

32

result:

ok 1 number(s): "32"

Test #6:

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

input:

10

output:

93

result:

ok 1 number(s): "93"

Test #7:

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

input:

15

output:

426

result:

ok 1 number(s): "426"

Test #8:

score: 0
Accepted
time: 622ms
memory: 7612kb

input:

431

output:

939569366

result:

ok 1 number(s): "939569366"

Test #9:

score: 0
Accepted
time: 264ms
memory: 8572kb

input:

339

output:

779167693

result:

ok 1 number(s): "779167693"

Test #10:

score: -100
Time Limit Exceeded

input:

619

output:


result: