QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127716 | #6678. Gem Island 2 | Energy_is_not_over | AC ✓ | 633ms | 369776kb | C++17 | 4.5kb | 2023-07-19 22:39:57 | 2023-07-19 22:40:01 |
Judging History
你现在查看的是测评时间为 2023-07-19 22:40:01 的历史记录
- [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:39:57]
- 提交
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, 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,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 241ms
memory: 312392kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 262ms
memory: 312324kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 264ms
memory: 312332kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 267ms
memory: 314412kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 252ms
memory: 312312kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 252ms
memory: 312404kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 253ms
memory: 312364kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 253ms
memory: 312372kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 250ms
memory: 312332kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 293ms
memory: 314384kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 263ms
memory: 312340kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 272ms
memory: 312400kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 517ms
memory: 369772kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 259ms
memory: 314384kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 255ms
memory: 312276kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 261ms
memory: 314484kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 269ms
memory: 316432kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 283ms
memory: 318552kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 270ms
memory: 318456kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 633ms
memory: 369776kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 630ms
memory: 369712kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 619ms
memory: 369668kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 256ms
memory: 312436kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 489ms
memory: 369740kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"