QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#757817 | #9553. The Hermit | ucup-team059 | AC ✓ | 80ms | 29416kb | C++20 | 3.8kb | 2024-11-17 13:47:28 | 2024-11-18 19:51:58 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define PIII pair<int,PII>
#define PI4 pair<int,array<int,3>>
#define endl '\n'
#define int long long
#define LL __int128
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N = 1e5 + 10,mod=998244353;
using i64 = long long;
template<class T> constexpr T mypow(T n, i64 k) {
T r = 1;
for (; k; k /= 2, n *= n) {
if (k % 2) {
r *= n;
}
}
return r;
}
template<int MOD> struct Zmod {
int x;
Zmod(int x = 0) : x(norm(x % MOD)) {}
// Zmod(i64 x) : x(norm(x % MOD)) {}
constexpr int norm(int x) const {
if (x < 0) {
x += MOD;
}
if (x >= MOD) {
x -= MOD;
}
return x;
}
constexpr int val() const {
return x;
}
constexpr Zmod operator-() const {
Zmod val = norm(MOD - x);
return val;
}
constexpr Zmod inv() const {
assert(x != 0);
return mypow(*this, MOD - 2);
}
friend constexpr auto &operator>>(istream &in, Zmod &j) {
int v;
in >> v;
j = Zmod(v);
return in;
}
friend constexpr auto &operator<<(ostream &o, const Zmod &j) {
return o << j.val();
}
constexpr Zmod &operator++() {
x = norm(x + 1);
return *this;
}
constexpr Zmod &operator--() {
x = norm(x - 1);
return *this;
}
constexpr Zmod &operator+=(const Zmod &i) {
x = norm(x + i.x);
return *this;
}
constexpr Zmod &operator-=(const Zmod &i) {
x = norm(x - i.x);
return *this;
}
constexpr Zmod &operator*=(const Zmod &i) {
x = i64(x) * i.x % MOD;
return *this;
}
constexpr Zmod &operator/=(const Zmod &i) {
return *this *= i.inv();
}
constexpr Zmod &operator%=(const int &i) {
return x %= i, *this;
}
friend constexpr Zmod operator+(const Zmod i, const Zmod j) {
return Zmod(i) += j;
}
friend constexpr Zmod operator-(const Zmod i, const Zmod j) {
return Zmod(i) -= j;
}
friend constexpr Zmod operator*(const Zmod i, const Zmod j) {
return Zmod(i) *= j;
}
friend constexpr Zmod operator/(const Zmod i, const Zmod j) {
return Zmod(i) /= j;
}
friend constexpr Zmod operator%(const Zmod i, const int j) {
return Zmod(i) %= j;
}
friend constexpr bool operator==(const Zmod i, const Zmod j) {
return i.val() == j.val();
}
friend constexpr bool operator!=(const Zmod i, const Zmod j) {
return i.val() != j.val();
}
friend constexpr bool operator<(const Zmod i, const Zmod j) {
return i.val() < j.val();
}
friend constexpr bool operator>(const Zmod i, const Zmod j) {
return i.val() > j.val();
}
};
constexpr int MOD[] = {998244353, 1000000007};
using Z = Zmod<MOD[0]>;
Z power(int n) {
return mypow(Z(2), n);
}
bool isprime[N];
int prime[N];
int cnt;
void euler(int n) {
memset(isprime, true, sizeof(isprime));
isprime[1] = false;
for (int i = 2; i <= n; ++i) {
if (isprime[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
isprime[i * prime[j]] = false;
if (i % prime[j] == 0) break;
}
}
}
Z fac[N], inv[N];
void fact(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * (i);
}
inv[n] = mypow(fac[n], mod - 2);
for (int i = n - 1; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1);
}
}
Z C(int n, int m) {
if (m > n)return 0;
return fac[n] * inv[m]* inv[n - m];
}
Z f[N][30];
void solve() {
int n, m;
cin>>m>>n;
fact(m);
Z ans;
for(int i=1;i<=m;i++){
f[i][1]=1;
}
for(int i=1;i<=m;i++){
for(int j=i*2;j<=m;j+=i){
for(int l=0;l<=20;l++){
f[j][l+1]+=f[i][l];
}
}
}
ans=C(m,n)*Z(n);
// cout<<ans<<endl;
for(int i=1;i<=m;i++){
for(int l=1;l<=20;l++){
ans-=f[i][l]*C(m/i-1,n-l);
}
}
cout<<ans<<endl;
}
signed main() {
// ios::sync_with_stdio(false), cin.tie(0);
ll t = 1;
// cin >> t;
// euler(1e3);
while (t--) {
solve();
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 28576kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 28744kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 59ms
memory: 28508kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 5ms
memory: 28524kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: 0
Accepted
time: 58ms
memory: 28576kb
input:
99998 12345
output:
936396560
result:
ok 1 number(s): "936396560"
Test #6:
score: 0
Accepted
time: 70ms
memory: 28840kb
input:
100000 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 66ms
memory: 29360kb
input:
100000 15
output:
190067060
result:
ok 1 number(s): "190067060"
Test #8:
score: 0
Accepted
time: 0ms
memory: 28772kb
input:
10 3
output:
299
result:
ok 1 number(s): "299"
Test #9:
score: 0
Accepted
time: 0ms
memory: 29388kb
input:
10 4
output:
743
result:
ok 1 number(s): "743"
Test #10:
score: 0
Accepted
time: 6ms
memory: 28580kb
input:
10 5
output:
1129
result:
ok 1 number(s): "1129"
Test #11:
score: 0
Accepted
time: 3ms
memory: 28640kb
input:
15 6
output:
28006
result:
ok 1 number(s): "28006"
Test #12:
score: 0
Accepted
time: 0ms
memory: 28636kb
input:
15 7
output:
42035
result:
ok 1 number(s): "42035"
Test #13:
score: 0
Accepted
time: 3ms
memory: 28672kb
input:
123 45
output:
214851327
result:
ok 1 number(s): "214851327"
Test #14:
score: 0
Accepted
time: 7ms
memory: 28564kb
input:
998 244
output:
964050559
result:
ok 1 number(s): "964050559"
Test #15:
score: 0
Accepted
time: 3ms
memory: 28528kb
input:
1919 810
output:
379720338
result:
ok 1 number(s): "379720338"
Test #16:
score: 0
Accepted
time: 0ms
memory: 28516kb
input:
1048 576
output:
216543264
result:
ok 1 number(s): "216543264"
Test #17:
score: 0
Accepted
time: 3ms
memory: 28576kb
input:
999 777
output:
635548531
result:
ok 1 number(s): "635548531"
Test #18:
score: 0
Accepted
time: 58ms
memory: 28660kb
input:
99999 77777
output:
448144614
result:
ok 1 number(s): "448144614"
Test #19:
score: 0
Accepted
time: 19ms
memory: 28964kb
input:
34527 6545
output:
748108997
result:
ok 1 number(s): "748108997"
Test #20:
score: 0
Accepted
time: 5ms
memory: 28500kb
input:
12345 12
output:
777496209
result:
ok 1 number(s): "777496209"
Test #21:
score: 0
Accepted
time: 3ms
memory: 28584kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 70ms
memory: 28572kb
input:
100000 10101
output:
855985819
result:
ok 1 number(s): "855985819"
Test #23:
score: 0
Accepted
time: 70ms
memory: 28572kb
input:
100000 91919
output:
92446940
result:
ok 1 number(s): "92446940"
Test #24:
score: 0
Accepted
time: 60ms
memory: 29296kb
input:
100000 77979
output:
106899398
result:
ok 1 number(s): "106899398"
Test #25:
score: 0
Accepted
time: 3ms
memory: 29032kb
input:
10000 11
output:
326411649
result:
ok 1 number(s): "326411649"
Test #26:
score: 0
Accepted
time: 67ms
memory: 28980kb
input:
100000 2
output:
15322970
result:
ok 1 number(s): "15322970"
Test #27:
score: 0
Accepted
time: 80ms
memory: 29416kb
input:
100000 3
output:
93355797
result:
ok 1 number(s): "93355797"
Test #28:
score: 0
Accepted
time: 68ms
memory: 29404kb
input:
100000 99998
output:
331850772
result:
ok 1 number(s): "331850772"
Test #29:
score: 0
Accepted
time: 67ms
memory: 29408kb
input:
100000 99996
output:
885066226
result:
ok 1 number(s): "885066226"
Test #30:
score: 0
Accepted
time: 7ms
memory: 29012kb
input:
13115 2964
output:
0
result:
ok 1 number(s): "0"
Test #31:
score: 0
Accepted
time: 68ms
memory: 28848kb
input:
100000 17
output:
425792977
result:
ok 1 number(s): "425792977"
Test #32:
score: 0
Accepted
time: 66ms
memory: 29104kb
input:
99991 16
output:
667323936
result:
ok 1 number(s): "667323936"
Test #33:
score: 0
Accepted
time: 60ms
memory: 28656kb
input:
99991 17
output:
627396741
result:
ok 1 number(s): "627396741"
Test #34:
score: 0
Accepted
time: 65ms
memory: 28572kb
input:
99991 18
output:
874158501
result:
ok 1 number(s): "874158501"
Test #35:
score: 0
Accepted
time: 61ms
memory: 28624kb
input:
100000 100000
output:
99999
result:
ok 1 number(s): "99999"
Test #36:
score: 0
Accepted
time: 52ms
memory: 28636kb
input:
94229 94229
output:
94228
result:
ok 1 number(s): "94228"
Test #37:
score: 0
Accepted
time: 51ms
memory: 28636kb
input:
94229 94223
output:
476599876
result:
ok 1 number(s): "476599876"
Test #38:
score: 0
Accepted
time: 0ms
memory: 29236kb
input:
2 1
output:
0
result:
ok 1 number(s): "0"
Test #39:
score: 0
Accepted
time: 3ms
memory: 28660kb
input:
2 2
output:
0
result:
ok 1 number(s): "0"
Test #40:
score: 0
Accepted
time: 0ms
memory: 28688kb
input:
3 1
output:
0
result:
ok 1 number(s): "0"
Test #41:
score: 0
Accepted
time: 0ms
memory: 28568kb
input:
3 2
output:
2
result:
ok 1 number(s): "2"
Test #42:
score: 0
Accepted
time: 0ms
memory: 28984kb
input:
3 3
output:
2
result:
ok 1 number(s): "2"
Test #43:
score: 0
Accepted
time: 3ms
memory: 29376kb
input:
9 2
output:
44
result:
ok 1 number(s): "44"
Test #44:
score: 0
Accepted
time: 0ms
memory: 28708kb
input:
9 3
output:
206
result:
ok 1 number(s): "206"
Test #45:
score: 0
Accepted
time: 0ms
memory: 28764kb
input:
9 4
output:
441
result:
ok 1 number(s): "441"
Test #46:
score: 0
Accepted
time: 0ms
memory: 29328kb
input:
9 7
output:
224
result:
ok 1 number(s): "224"
Test #47:
score: 0
Accepted
time: 32ms
memory: 28588kb
input:
70839 22229
output:
0
result:
ok 1 number(s): "0"
Test #48:
score: 0
Accepted
time: 33ms
memory: 29080kb
input:
65536 17
output:
698801006
result:
ok 1 number(s): "698801006"
Test #49:
score: 0
Accepted
time: 32ms
memory: 29212kb
input:
65535 17
output:
433312902
result:
ok 1 number(s): "433312902"
Test #50:
score: 0
Accepted
time: 57ms
memory: 29216kb
input:
99856 317
output:
932131332
result:
ok 1 number(s): "932131332"
Test #51:
score: 0
Accepted
time: 62ms
memory: 29240kb
input:
99856 318
output:
398997854
result:
ok 1 number(s): "398997854"
Test #52:
score: 0
Accepted
time: 69ms
memory: 29180kb
input:
99856 2
output:
984791559
result:
ok 1 number(s): "984791559"
Test #53:
score: 0
Accepted
time: 67ms
memory: 28600kb
input:
100000 50000
output:
309108799
result:
ok 1 number(s): "309108799"
Extra Test:
score: 0
Extra Test Passed