QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#757280#9553. The Hermitucup-team3099#AC ✓31ms12880kbC++235.8kb2024-11-17 03:32:032024-11-17 03:32:04

Judging History

你现在查看的是测评时间为 2024-11-17 03:32:04 的历史记录

  • [2024-11-18 19:51:42]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:31ms
  • 内存:12808kb
  • [2024-11-18 19:43:48]
  • hack成功,自动添加数据
  • (/hack/1196)
  • [2024-11-17 03:32:04]
  • 评测
  • 测评结果:100
  • 用时:31ms
  • 内存:12880kb
  • [2024-11-17 03:32:03]
  • 提交

answer

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

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

template <class T, class E>
constexpr T fexp(T x, E e) {
    T ans(1);
    for(; e > 0; e >>= 1) {
        if(e & 1) ans = ans * x;
        x = x * x;
    }
    return ans;
}

template <class LOW, class HIGH, const LOW mod>
struct modBase {
    using mint = modBase<LOW, HIGH, mod>;
    constexpr modBase() : val(0) {}
    // be careful of negative numbers!
    constexpr modBase(const LOW v) : val((v % mod + mod) % mod) {} 
    LOW val;

    #define add(a, b) a + b >= mod ? a + b - mod : a + b
    #define sub(a, b) a < b ? a + mod - b : a - b

    constexpr mint &operator += (const mint &o) { return val = add(val, o.val), *this; }
    constexpr mint &operator -= (const mint &o) { return val = sub(val, o.val), *this; }
    constexpr mint &operator *= (const mint &o) { return val = (LOW) ((HIGH) val * o.val % mod), *this; }
    constexpr mint &operator /= (const mint &o) { return *this *= o.inverse(); }

    constexpr mint operator + (const mint &b) const { return mint(*this) += b; }
    constexpr mint operator - (const mint &b) const { return mint(*this) -= b; }
    constexpr mint operator * (const mint &b) const { return mint(*this) *= b; }
    constexpr mint operator / (const mint &b) const { return mint(*this) /= b; }

    constexpr mint operator - () const { return mint() - mint(*this); }
    constexpr bool operator == (const mint &b) const { return val == b.val; }
    constexpr bool operator != (const mint &b) const { return val != b.val; }

    template<class E> constexpr mint pow (E e) const { return fexp(*this, e); }
    constexpr mint inverse() const { return pow(mod - 2); }
    constexpr LOW get() const { return val; }
    static constexpr LOW getMod() { return mod; }

    friend std::ostream& operator << (std::ostream &os, const mint &p) { return os << p.val; }
    friend std::istream& operator >> (std::istream &is, mint &p) { return is >> p.val; }
};

const int MOD = 998244353;
const int ms = 100100;
using mint = modBase<int, long long, MOD>;

mint fat[ms], ifat[ms];
void initComb() {
    fat[0] = 1;
    for(int i = 1; i < ms; i++) {
        fat[i] = fat[i-1] * i;
    }
    ifat[ms-1] = fexp(fat[ms-1], MOD - 2);
    for(int i = ms-1; i > 0; i--) {
        ifat[i-1] = ifat[i] * i;
    }
}
mint comb(int n, int a) { return a < 0 || a > n ? mint() : fat[n] * ifat[a] * ifat[n-a]; }

bool notPrime[ms];
int mobius[ms];

mint memo[ms][20];
bool visit[ms][20];

int m;

mint dp(int n, int used) {
    if(m - used <= 0) {
        return mint(0);
    }
    mint &ans = memo[n][used];
    if(visit[n][used]) {
        return ans;
    }
    ans = comb(n - 1, m-used) * (m - used);
    visit[n][used] = true;
    for(int i = 2; i <= n; i++) {
        ans += (comb(n / i, m-used)) * mobius[i] * (m - used);
        ans -= (dp(n / i, used) + dp(n / i, used+1)) * mobius[i];
    }
    return ans;
}

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    initComb();
    int n;
    std::cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        mobius[i] = 1;
    }
    for(int i = 2; i <= n; i++) {
        if(notPrime[i]) {
            continue;
        }
        for(int j = i; j <= n; j += i) {
            mobius[j] = -mobius[j];
            notPrime[j] = true;
            if(j / i % i == 0) {
                mobius[j] = 0;
            }
        }
    }
    mint ans(0);
    std::cout << dp(n, 1) + dp(n, 0) << '\n';
}

/*
NEVER FORGET TO:
    Look at the problem's constraints before coding.
How to cheese cf:
    Find a lower bound or upper bound for the problem. Have faith that it is the answer of the problem.
    If it isn't the answer, have more faith or change to another bound god by looking for a better bound.

    Trust guesses. Who has time to think? If people in div2 AC the problem it requires no proof since people don't prove things.

    You must draw cases. Thinking gets you nowhere, so draw cases and reach illogical conclusions from them.
    Sometimes drawing cases is bad because it takes too much time. Faster is to not think at all and just code a bruteforce solution.
    This is called "law of small numbers". If something works for small numbers, surely it works for big numbers.
    https://en.wikipedia.org/wiki/Faulty_generalization#Hasty_generalization don't mind the "faulty" part of it, in competitive programming mistakes are lightly punished
    Don't think about them being right or not, cf is a battle of intuition only.

    Be as stupid as possible in implementation. Trying to be smart is an easy way to get WA.

    Think about 2x2 cases for matrix problems and hope that everything works for the general case.

    Find a necessary condition and trust it to be sufficient. They're basically the same thing.

    Heuristics might speed up your code. Forget about complexity, it's only about ACing and not proving that your solution is good.

    For paths in a grid starting at (1, i) or something like that, assume that they never cross and do D&C

    Consider doing problems in reverse order of queries/updates

    For combinatorics problems, consider symmetry

    For problems that are similar to past problems, think about the differences betweem it and the current problem.
    Sometimes the difference makes no difference. Sometimes it does.

General strategy (MUST DO):
    Try to solve the problem with more restricted constraints.

About testing:
    Test n=1, a[i]=1, a[i]=n, etc. Basically, test low values. No need to test if pretests are strong, but if you get WA it's good.

This isn't a joke. Do it if you get stuck. It's shit practice in my opinion, but do it if you want AC.
*/

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 30ms
memory: 9420kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 5ms
memory: 10008kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: 0
Accepted
time: 26ms
memory: 10664kb

input:

99998 12345

output:

936396560

result:

ok 1 number(s): "936396560"

Test #6:

score: 0
Accepted
time: 9ms
memory: 11468kb

input:

100000 1

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 31ms
memory: 9424kb

input:

100000 15

output:

190067060

result:

ok 1 number(s): "190067060"

Test #8:

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

input:

10 3

output:

299

result:

ok 1 number(s): "299"

Test #9:

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

input:

10 4

output:

743

result:

ok 1 number(s): "743"

Test #10:

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

input:

10 5

output:

1129

result:

ok 1 number(s): "1129"

Test #11:

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

input:

15 6

output:

28006

result:

ok 1 number(s): "28006"

Test #12:

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

input:

15 7

output:

42035

result:

ok 1 number(s): "42035"

Test #13:

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

input:

123 45

output:

214851327

result:

ok 1 number(s): "214851327"

Test #14:

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

input:

998 244

output:

964050559

result:

ok 1 number(s): "964050559"

Test #15:

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

input:

1919 810

output:

379720338

result:

ok 1 number(s): "379720338"

Test #16:

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

input:

1048 576

output:

216543264

result:

ok 1 number(s): "216543264"

Test #17:

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

input:

999 777

output:

635548531

result:

ok 1 number(s): "635548531"

Test #18:

score: 0
Accepted
time: 30ms
memory: 11600kb

input:

99999 77777

output:

448144614

result:

ok 1 number(s): "448144614"

Test #19:

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

input:

34527 6545

output:

748108997

result:

ok 1 number(s): "748108997"

Test #20:

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

input:

12345 12

output:

777496209

result:

ok 1 number(s): "777496209"

Test #21:

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

input:

1 1

output:

0

result:

ok 1 number(s): "0"

Test #22:

score: 0
Accepted
time: 30ms
memory: 10848kb

input:

100000 10101

output:

855985819

result:

ok 1 number(s): "855985819"

Test #23:

score: 0
Accepted
time: 29ms
memory: 9520kb

input:

100000 91919

output:

92446940

result:

ok 1 number(s): "92446940"

Test #24:

score: 0
Accepted
time: 25ms
memory: 9584kb

input:

100000 77979

output:

106899398

result:

ok 1 number(s): "106899398"

Test #25:

score: 0
Accepted
time: 4ms
memory: 6652kb

input:

10000 11

output:

326411649

result:

ok 1 number(s): "326411649"

Test #26:

score: 0
Accepted
time: 23ms
memory: 10364kb

input:

100000 2

output:

15322970

result:

ok 1 number(s): "15322970"

Test #27:

score: 0
Accepted
time: 29ms
memory: 9556kb

input:

100000 3

output:

93355797

result:

ok 1 number(s): "93355797"

Test #28:

score: 0
Accepted
time: 29ms
memory: 10860kb

input:

100000 99998

output:

331850772

result:

ok 1 number(s): "331850772"

Test #29:

score: 0
Accepted
time: 29ms
memory: 9516kb

input:

100000 99996

output:

885066226

result:

ok 1 number(s): "885066226"

Test #30:

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

input:

13115 2964

output:

0

result:

ok 1 number(s): "0"

Test #31:

score: 0
Accepted
time: 31ms
memory: 10724kb

input:

100000 17

output:

425792977

result:

ok 1 number(s): "425792977"

Test #32:

score: 0
Accepted
time: 31ms
memory: 10492kb

input:

99991 16

output:

667323936

result:

ok 1 number(s): "667323936"

Test #33:

score: 0
Accepted
time: 27ms
memory: 10572kb

input:

99991 17

output:

627396741

result:

ok 1 number(s): "627396741"

Test #34:

score: 0
Accepted
time: 31ms
memory: 9352kb

input:

99991 18

output:

874158501

result:

ok 1 number(s): "874158501"

Test #35:

score: 0
Accepted
time: 25ms
memory: 9420kb

input:

100000 100000

output:

99999

result:

ok 1 number(s): "99999"

Test #36:

score: 0
Accepted
time: 28ms
memory: 10332kb

input:

94229 94229

output:

94228

result:

ok 1 number(s): "94228"

Test #37:

score: 0
Accepted
time: 24ms
memory: 10848kb

input:

94229 94223

output:

476599876

result:

ok 1 number(s): "476599876"

Test #38:

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

input:

2 1

output:

0

result:

ok 1 number(s): "0"

Test #39:

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

input:

2 2

output:

0

result:

ok 1 number(s): "0"

Test #40:

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

input:

3 1

output:

0

result:

ok 1 number(s): "0"

Test #41:

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

input:

3 2

output:

2

result:

ok 1 number(s): "2"

Test #42:

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

input:

3 3

output:

2

result:

ok 1 number(s): "2"

Test #43:

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

input:

9 2

output:

44

result:

ok 1 number(s): "44"

Test #44:

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

input:

9 3

output:

206

result:

ok 1 number(s): "206"

Test #45:

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

input:

9 4

output:

441

result:

ok 1 number(s): "441"

Test #46:

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

input:

9 7

output:

224

result:

ok 1 number(s): "224"

Test #47:

score: 0
Accepted
time: 21ms
memory: 12492kb

input:

70839 22229

output:

0

result:

ok 1 number(s): "0"

Test #48:

score: 0
Accepted
time: 14ms
memory: 12792kb

input:

65536 17

output:

698801006

result:

ok 1 number(s): "698801006"

Test #49:

score: 0
Accepted
time: 21ms
memory: 12880kb

input:

65535 17

output:

433312902

result:

ok 1 number(s): "433312902"

Test #50:

score: 0
Accepted
time: 30ms
memory: 9508kb

input:

99856 317

output:

932131332

result:

ok 1 number(s): "932131332"

Test #51:

score: 0
Accepted
time: 29ms
memory: 9580kb

input:

99856 318

output:

398997854

result:

ok 1 number(s): "398997854"

Test #52:

score: 0
Accepted
time: 23ms
memory: 9224kb

input:

99856 2

output:

984791559

result:

ok 1 number(s): "984791559"

Test #53:

score: 0
Accepted
time: 29ms
memory: 9452kb

input:

100000 50000

output:

309108799

result:

ok 1 number(s): "309108799"

Extra Test:

score: 0
Extra Test Passed