QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#757280#9553. The Hermitucup-team3099#AC ✓31ms12808kbC++235.8kb2024-11-17 03:32:032024-11-18 19:51:42

Judging History

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

  • [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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

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

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

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

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

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

input:

99998 12345

output:

936396560

result:

ok 1 number(s): "936396560"

Test #6:

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

input:

100000 1

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

100000 15

output:

190067060

result:

ok 1 number(s): "190067060"

Test #8:

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

input:

10 3

output:

299

result:

ok 1 number(s): "299"

Test #9:

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

input:

10 4

output:

743

result:

ok 1 number(s): "743"

Test #10:

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

input:

10 5

output:

1129

result:

ok 1 number(s): "1129"

Test #11:

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

input:

15 6

output:

28006

result:

ok 1 number(s): "28006"

Test #12:

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

input:

15 7

output:

42035

result:

ok 1 number(s): "42035"

Test #13:

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

input:

123 45

output:

214851327

result:

ok 1 number(s): "214851327"

Test #14:

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

input:

998 244

output:

964050559

result:

ok 1 number(s): "964050559"

Test #15:

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

input:

1919 810

output:

379720338

result:

ok 1 number(s): "379720338"

Test #16:

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

input:

1048 576

output:

216543264

result:

ok 1 number(s): "216543264"

Test #17:

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

input:

999 777

output:

635548531

result:

ok 1 number(s): "635548531"

Test #18:

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

input:

99999 77777

output:

448144614

result:

ok 1 number(s): "448144614"

Test #19:

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

input:

34527 6545

output:

748108997

result:

ok 1 number(s): "748108997"

Test #20:

score: 0
Accepted
time: 6ms
memory: 10152kb

input:

12345 12

output:

777496209

result:

ok 1 number(s): "777496209"

Test #21:

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

input:

1 1

output:

0

result:

ok 1 number(s): "0"

Test #22:

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

input:

100000 10101

output:

855985819

result:

ok 1 number(s): "855985819"

Test #23:

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

input:

100000 91919

output:

92446940

result:

ok 1 number(s): "92446940"

Test #24:

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

input:

100000 77979

output:

106899398

result:

ok 1 number(s): "106899398"

Test #25:

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

input:

10000 11

output:

326411649

result:

ok 1 number(s): "326411649"

Test #26:

score: 0
Accepted
time: 20ms
memory: 11288kb

input:

100000 2

output:

15322970

result:

ok 1 number(s): "15322970"

Test #27:

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

input:

100000 3

output:

93355797

result:

ok 1 number(s): "93355797"

Test #28:

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

input:

100000 99998

output:

331850772

result:

ok 1 number(s): "331850772"

Test #29:

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

input:

100000 99996

output:

885066226

result:

ok 1 number(s): "885066226"

Test #30:

score: 0
Accepted
time: 6ms
memory: 9932kb

input:

13115 2964

output:

0

result:

ok 1 number(s): "0"

Test #31:

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

input:

100000 17

output:

425792977

result:

ok 1 number(s): "425792977"

Test #32:

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

input:

99991 16

output:

667323936

result:

ok 1 number(s): "667323936"

Test #33:

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

input:

99991 17

output:

627396741

result:

ok 1 number(s): "627396741"

Test #34:

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

input:

99991 18

output:

874158501

result:

ok 1 number(s): "874158501"

Test #35:

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

input:

100000 100000

output:

99999

result:

ok 1 number(s): "99999"

Test #36:

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

input:

94229 94229

output:

94228

result:

ok 1 number(s): "94228"

Test #37:

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

input:

94229 94223

output:

476599876

result:

ok 1 number(s): "476599876"

Test #38:

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

input:

2 1

output:

0

result:

ok 1 number(s): "0"

Test #39:

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

input:

2 2

output:

0

result:

ok 1 number(s): "0"

Test #40:

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

input:

3 1

output:

0

result:

ok 1 number(s): "0"

Test #41:

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

input:

3 2

output:

2

result:

ok 1 number(s): "2"

Test #42:

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

input:

3 3

output:

2

result:

ok 1 number(s): "2"

Test #43:

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

input:

9 2

output:

44

result:

ok 1 number(s): "44"

Test #44:

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

input:

9 3

output:

206

result:

ok 1 number(s): "206"

Test #45:

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

input:

9 4

output:

441

result:

ok 1 number(s): "441"

Test #46:

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

input:

9 7

output:

224

result:

ok 1 number(s): "224"

Test #47:

score: 0
Accepted
time: 22ms
memory: 11024kb

input:

70839 22229

output:

0

result:

ok 1 number(s): "0"

Test #48:

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

input:

65536 17

output:

698801006

result:

ok 1 number(s): "698801006"

Test #49:

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

input:

65535 17

output:

433312902

result:

ok 1 number(s): "433312902"

Test #50:

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

input:

99856 317

output:

932131332

result:

ok 1 number(s): "932131332"

Test #51:

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

input:

99856 318

output:

398997854

result:

ok 1 number(s): "398997854"

Test #52:

score: 0
Accepted
time: 17ms
memory: 9524kb

input:

99856 2

output:

984791559

result:

ok 1 number(s): "984791559"

Test #53:

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

input:

100000 50000

output:

309108799

result:

ok 1 number(s): "309108799"

Extra Test:

score: 0
Extra Test Passed