QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#775498#9553. The Hermitguiyuan98#WA 458ms42084kbC++203.1kb2024-11-23 16:05:162024-11-23 16:05:16

Judging History

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

  • [2024-11-23 16:05:16]
  • 评测
  • 测评结果:WA
  • 用时:458ms
  • 内存:42084kb
  • [2024-11-23 16:05:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define linf 1e18
#define pb push_back
#define siz size()
#define int long long
#define ll long long
#define ld long double
#define PII pair<int, int>
const int mod = 998244353;
using i64 = long long;
using u64 = unsigned long long;
const int N = 1e5 + 10;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

namespace my128
{
  using i128 = __int128_t;
  i128 abs(const i128 &x) { return x > 0 ? x : -x; }
  auto &operator>>(istream &it, i128 &j)
  {
    string val;
    it >> val;
    i128 ans = 0;
    bool f = 0; // 负数标记
    for (char c : val)
    {
      if (c == '-')
        f = 1;
      else if (c >= '0' && c <= '9')
        ans = ans * 10 + c - '0';
    }
    j = f ? -ans : ans;
    return it;
  }

  auto &operator<<(ostream &os, const i128 &j)
  {
    string ans;
    function<void(i128)> write = [&](i128 x)
    { if (x < 0) ans += '-', x = -x; if (x > 9) write(x / 10); ans += x % 10 + '0'; };
    write(j);
    return os << ans;
  }
}
using namespace my128;
// my128::i128 a, b;
int qpow(int a, int b)
{
  int res = 1;
  while (b)
  {
    if (b & 1)
      res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
struct myhash
{
  static uint64_t hash(uint64_t x)
  {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const
  {
    static const uint64_t SEED =
        chrono::steady_clock::now().time_since_epoch().count();
    return hash(x + SEED);
  }
  size_t operator()(pair<uint64_t, uint64_t> x) const
  {
    static const uint64_t SEED =
        chrono::steady_clock::now().time_since_epoch().count();
    return hash(x.first + SEED) ^ (hash(x.second + SEED) >> 1);
  }
};
ll fac[N], invfac[N];
void init(int n)
{
  fac[0] = 1;
  for (int i = 1; i <= n; i++)
    fac[i] = fac[i - 1] * i % mod;
  invfac[n] = qpow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; i--)
    invfac[i] = invfac[i + 1] * (i + 1) % mod;
}

i64 C(int n, int m)
{ // 组合数
  if (m > n || m < 0)
    return 0;
  return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}

i64 A(int n, int m)
{ // 排列数
  if (m > n || m < 0)
    return 0;
  return fac[n] * invfac[n - m] % mod;
}

i64 catalan(int n)
{ // 卡特兰数
  if (n < 0)
    return 0;
  return C(2 * n, n) * qpow(n + 1, mod - 2) % mod;
}
void solve()
{
  int n, m;
  cin >> m >> n;
  unordered_map<int, unordered_map<int, int, myhash>, myhash> f;
  init(m);
  for (int i = 1; i <= m; i++)
    f[1][i] = 1;
  for (int i = 2; i <= n; i++)
    for (auto [x, y] : f[i - 1])
      for (int j = 2; j * x <= m; j++)
        f[i][j * x] = (f[i][j * x] + f[i - 1][x]) % mod;
  int ans = n * C(m, n) % mod;
  for (int i = 1; i <= n; i++)
    for (auto [x, y] : f[i])
      ans = ans - y * C(m / x - 1, n - i) % mod + mod % mod;
  cout << ans;
}
signed main()
{
  IOS;
  int t = 1;
  // cin >> t;
  while (t--)
    solve();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 458ms
memory: 42084kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: -100
Wrong Answer
time: 24ms
memory: 6708kb

input:

11451 1919

output:

-3147361259

result:

wrong answer 1st numbers differ - expected: '845616153', found: '-3147361259'