QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#757280 | #9553. The Hermit | ucup-team3099# | AC ✓ | 31ms | 12880kb | C++23 | 5.8kb | 2024-11-17 03:32:03 | 2024-11-17 03:32:04 |
Judging History
你现在查看的是测评时间为 2024-11-17 03:32:04 的历史记录
- [2024-11-18 19:43:48]
- hack成功,自动添加数据
- (/hack/1196)
- [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