QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#757280 | #9553. The Hermit | ucup-team3099# | AC ✓ | 31ms | 12808kb | C++23 | 5.8kb | 2024-11-17 03:32:03 | 2024-11-18 19:51:42 |
Judging History
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