QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127717#6678. Gem Island 2Energy_is_not_overAC ✓865ms428684kbC++174.5kb2023-07-19 22:40:112024-04-23 17:45:25

Judging History

你现在查看的是最新测评结果

  • [2024-04-23 17:45:25]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:865ms
  • 内存:428684kb
  • [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:13]
  • 评测
  • 测评结果:100
  • 用时:703ms
  • 内存:428380kb
  • [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