QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127717 | #6678. Gem Island 2 | Energy_is_not_over | AC ✓ | 865ms | 428684kb | C++17 | 4.5kb | 2023-07-19 22:40:11 | 2024-04-23 17:45:25 |
Judging History
你现在查看的是最新测评结果
- [2024-04-23 17:43:38]
- hack成功,自动添加数据
- (/hack/600)
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-19 22:40:11]
- 提交
answer
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif
const int max_n = 15000474;
const int mod = 998244353;
inline void inc(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
inline void dec(int &x, int y) {
x -= y;
if (x < 0) {
x += mod;
}
}
inline int mul(int x) {
return x;
}
template<typename... Args>
inline int mul(int x, Args... args) {
return (1LL * x * mul(args...)) % mod;
}
int power(int a, int b) {
int res = 1 % mod;
while (b) {
if (b % 2) {
res = mul(res, a);
}
b /= 2;
a = mul(a, a);
}
return res;
}
int inv(int x) {
return power(x, mod - 2);
}
string str_fraction(int x, int n = 20) {
stringstream res;
pair<int, int> best(x, 1);
for (int j = 1; j < n; ++j) {
best = min(best, {mul(x, j), j});
best = min(best, {mod - mul(x, j), -j});
}
if (best.second < 0) {
best.first *= -1;
best.second *= -1;
}
res << best.first << "/" << best.second;
return res.str();
}
template<int max_f, int max_rf>
struct BCCalculator {
static_assert(max_f >= 1 && max_rf >= 1);
int f[max_f], rf[max_rf];
BCCalculator() {
f[0] = rf[0] = 1;
for (int i = 1; i < max_f; ++i) {
f[i] = mul(i, f[i - 1]);
}
int x = f[min(max_f, max_rf) - 1];
for (int i = max_f; i < max_rf; ++i) {
x = mul(x, i);
}
rf[max_rf - 1] = inv(x);
for (int i = max_rf - 2; i > 0; --i) {
rf[i] = mul(i + 1, rf[i + 1]);
}
}
int get_c(int n, int k) const {
if (n < k || k < 0) {
return 0;
}
assert(n < max_f && k < max_rf && n - k < max_rf);
return mul(f[n], mul(rf[k], rf[n - k]));
}
};
BCCalculator<2 * max_n, 47 + 2 * max_n> bc;
int inversed[max_n];
int get_ways(int ones,int poses)
{
if (ones<0){
return 0;
}
return bc.get_c(ones+poses-1,poses-1);
}
int magic[max_n];
int magic2[max_n];
bool not_is_prime[max_n];
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,d,r;
cin>>n>>d>>r;
// n=d=r=15000000;
for (int i=0;i<max_n;i++){
magic[i] = mul(bc.f[i+(n-1)], bc.rf[i]);
}
for (int i = 1; i < max_n; ++i) {
inversed[i] = mul(bc.f[i - 1], bc.rf[i]);
}
for (int i = 2; i * i < max_n; ++i) {
if (!not_is_prime[i]) {
for (int j = i * i; j < max_n; j += i) {
not_is_prime[j] = 1;
}
}
}
for (int i = 1; i <= d; ++i) {
magic2[i] = magic[d - i];
}
for (int i = 2; i <= d; ++i) {
if (!not_is_prime[i]) {
for (int j = d / i; j >= 0; --j) {
inc(magic2[j], magic2[j * i]);
}
}
}
int ans=0;
int sign = 1;
for (int k=1;k<=n;k++){
sign = mod - sign;
int sum1=0;
int sum2=0;
const int R1=min(k,r);
if (k==1) {
sum1= mod - 1;
} else if (k==R1) {
sum1=0;
} else {
sum1=mul(bc.rf[R1-1], inversed[k-1], bc.rf[k-R1-1]);
if (R1 % 2) {
sum1 = mod - sum1;
}
}
const int L1=min(k,r)+1;
if (L1>k){
sum2=0;
}
else{
sum2=mul(bc.rf[L1-1], inversed[k], bc.rf[k-L1]);
if (L1 % 2) {
sum2 = mod - sum2;
}
}
sum2 = mul(sum2, r);
int sum=sum1;
inc(sum, sum2);
sum = mul(sum, sign);
sum = mul(sum, bc.rf[n - k]);
inc(ans, mul(sum, magic2[k]));
}
ans=mul(ans, bc.rf[n-1], bc.f[n], inv(get_ways(d,n)));
inc(ans, r);
cout<<ans<<"\n";
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 319ms
memory: 373188kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 330ms
memory: 371936kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 337ms
memory: 371104kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 336ms
memory: 371340kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 315ms
memory: 371044kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 337ms
memory: 371332kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 330ms
memory: 373384kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 327ms
memory: 371084kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 347ms
memory: 371104kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 362ms
memory: 373160kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 365ms
memory: 373160kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 365ms
memory: 371336kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 629ms
memory: 428456kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 340ms
memory: 371984kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 318ms
memory: 371180kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 332ms
memory: 370992kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 336ms
memory: 374232kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 348ms
memory: 374524kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 331ms
memory: 374832kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 845ms
memory: 428456kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 865ms
memory: 428684kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 835ms
memory: 428392kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 325ms
memory: 370988kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 605ms
memory: 428352kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed