QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#563081	#5192. 赌徒问题	elegia	AC ✓	194ms	176952kb	C++23	3.2kb	2024-09-14 02:27:54	2024-09-14 18:35:14

Judging History

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

[2024-09-14 18:35:14]
评测

测评结果：AC
用时：194ms
内存：176952kb

查看

[2024-09-14 02:27:54]
提交

answer

/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int P = 1000000007;

int norm(int x) { return x >= P ? (x - P) : x; }

void add(int& x, int y) { if ((x += y - P) < 0) x += P; }

void sub(int& x, int y) { if ((x -= y) < 0) x += P; }

const int N = 11, M = 2010;

typedef int DP[N][M];

int n, m;
ll k;
DP f[M];
int tot[M];

int upd;
void add(DP& dp, int w) {
  ++upd;
  for (int i = 1; i <= n; ++i) for (int j = w; j <= m; ++j)
    add(dp[i][j], dp[i - 1][j - w]);
}
void sub(DP& dp, int w) {
  ++upd;
  for (int i = n; i; --i) for (int j = m; j >= w; --j)
    sub(dp[i][j], dp[i - 1][j - w]);
}

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) for (int j = 1; j <= m; ++j)
    tot[i] += i * k % j == 0;
  f[1][0][0] = 1;
  for (int i = 1; i <= m; ++i) if (k % i == 0)
    add(f[1], i);
  int ans = f[1][n][1];
  for (int i = 2; i <= m; ++i) {
    int p = 1;
    for (int j = 2; j != i; ++j) if (i % j == 0 && tot[j] > tot[p]) p = j;
    memcpy(f[i], f[p], sizeof(f[i]));
    for (int j = 1; j <= m; ++j) if ((i * k % j == 0) > (p * k % j == 0))
      add(f[i], j);
    add(ans, f[i][n][i]);
  }
  cout << ans << '\n';

  cerr << "total update: " << upd << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3732kb

input:

1 1 1

output:

result:

ok single line: '1'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3736kb

input:

1 1 20211123

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 12ms

memory: 61116kb

input:

1 666 65300

output:

result:

ok single line: '666'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3708kb

input:

9 1 12563478

output:

result:

ok single line: '0'

Test #5:

score: 0

Accepted

time: 92ms

memory: 176380kb

input:

8 2000 1

output:

result:

ok single line: '670025'

Test #6:

score: 0

Accepted

time: 149ms

memory: 176952kb

input:

10 2000 440000000

output:

406465496

result:

ok single line: '406465496'

Test #7:

score: 0

Accepted

time: 146ms

memory: 174892kb

input:

10 1983 994593600

output:

403639064

result:

ok single line: '403639064'

Test #8:

score: 0

Accepted

time: 133ms

memory: 176384kb

input:

9 2000 821620800

output:

280647604

result:

ok single line: '280647604'

Test #9:

score: 0

Accepted

time: 155ms

memory: 176468kb

input:

10 2000 908107200

output:

991344753

result:

ok single line: '991344753'

Test #10:

score: 0

Accepted

time: 140ms

memory: 176104kb

input:

10 1997 616215600

output:

957863888

result:

ok single line: '957863888'

Test #11:

score: 0

Accepted

time: 194ms

memory: 176316kb

input:

10 1999 898405200

output:

681280074

result:

ok single line: '681280074'

Test #12:

score: 0

Accepted

time: 155ms

memory: 176420kb

input:

10 2000 20210526

output:

100160322

result:

ok single line: '100160322'

Test #13:

score: 0

Accepted

time: 110ms

memory: 176416kb

input:

10 2000 950965721

output:

14040666

result:

ok single line: '14040666'

Test #14:

score: 0

Accepted

time: 123ms

memory: 176220kb

input:

10 1998 944303559

output:

394435476

result:

ok single line: '394435476'