QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#76908#5031. 核Chinese_zjc_60 1999ms160236kbC++143.1kb2023-02-12 16:43:322023-02-12 16:43:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-12 16:43:35]
  • 评测
  • 测评结果:60
  • 用时:1999ms
  • 内存:160236kb
  • [2023-02-12 16:43:32]
  • 提交

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
unsigned MOD;
struct mint
{
    unsigned v;
    mint(unsigned v_ = 0) : v(v_) {}
    mint operator-() const { return v ? MOD - v : *this; }
    mint &operator+=(const mint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
    mint &operator-=(const mint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
    mint &operator*=(const mint &X) { return v = 1llu * v * X.v % MOD, *this; }
    mint &operator/=(const mint &X) { return *this *= X.inv(); }
    mint pow(long long B) const
    {
        B %= MOD - 1;
        if (B < 0)
            B += MOD - 1;
        mint res = 1, A = *this;
        while (B)
        {
            if (B & 1)
                res *= A;
            B >>= 1;
            A *= A;
        }
        return res;
    }
    mint inv() const { return pow(MOD - 2); }
    friend mint operator+(const mint &A, const mint &B) { return mint(A) += B; }
    friend mint operator-(const mint &A, const mint &B) { return mint(A) -= B; }
    friend mint operator*(const mint &A, const mint &B) { return mint(A) *= B; }
    friend mint operator/(const mint &A, const mint &B) { return mint(A) /= B; }
    friend std::istream &operator>>(std::istream &A, mint &B) { return A >> B.v; }
    friend std::ostream &operator<<(std::ostream &A, const mint &B) { return A << B.v; }
    friend bool operator==(const mint &A, const mint &B) { return A.v == B.v; }
    explicit operator bool() const { return v; }
} pw3[32769], pW3[32769], pwq[32769], pWq[32769], fact[10000005], ifact[10000005], f[10000005], g[10000005], ans;
int n, q;
mint get3(long long p) { return p %= MOD - 1, pw3[p & 32767] * pW3[p >> 15]; }
mint getq(long long p) { return p %= MOD - 1, pwq[p & 32767] * pWq[p >> 15]; }
mint down(int n, int m) { return fact[m] * getq((n * 2ll - m - 1) * m / 2); }
mint C(int n, int m) { return 0 <= m && m <= n ? fact[n] * ifact[n - m] * ifact[m] : 0; }
void init()
{
    pw3[0] = 1;
    for (int i = 1; i <= 32768; ++i)
        pw3[i] = pw3[i - 1] * 3;
    pW3[0] = 1;
    for (int i = 1; i <= 32768; ++i)
        pW3[i] = pW3[i - 1] * pw3[32768];
    pwq[0] = 1;
    for (int i = 1; i <= 32768; ++i)
        pwq[i] = pwq[i - 1] * q;
    pWq[0] = 1;
    for (int i = 1; i <= 32768; ++i)
        pWq[i] = pWq[i - 1] * pwq[32768];
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
        fact[i] = fact[i - 1] * (getq(i) - 1);
    ifact[n] = fact[n].inv();
    for (int i = n; i; --i)
        ifact[i - 1] = ifact[i] * (getq(i) - 1);
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> q >> MOD;
    init();
    g[0] = 1;
    for (int i = 1; i <= n; ++i)
        g[i] = -getq(i - 1) * g[i - 1] * ifact[i] * fact[i - 1];
    f[0] = g[0];
    for (int i = 1; i <= n; ++i)
        f[i] = ((getq(n) - getq(i - 1)) * f[i - 1] + g[i]) * getq(MOD - 1 - i);
    int t = 1;
    for (int i = 1; i <= n; ++i)
        t = 1ll * t * q % (MOD - 1);
    for (int i = 0, j = 1; i <= n; ++i, j = 1ll * j * t % (MOD - 1))
        ans += get3(j) * f[n - i] * fact[n] * ifact[i];
    std::cout << ans << std::endl;
    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 29ms
memory: 160048kb

input:

1 2 540053233

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 24ms
memory: 160060kb

input:

2 2 156542707

output:

43046970

result:

ok 1 number(s): "43046970"

Test #3:

score: 0
Accepted
time: 23ms
memory: 160056kb

input:

1 2 186225229

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 45ms
memory: 160120kb

input:

3 3 109884329

output:

100602209

result:

ok 1 number(s): "100602209"

Test #5:

score: 0
Accepted
time: 25ms
memory: 160092kb

input:

1 2 144802297

output:

9

result:

ok 1 number(s): "9"

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 20
Accepted
time: 24ms
memory: 160236kb

input:

20 21992843 328859143

output:

110137213

result:

ok 1 number(s): "110137213"

Test #7:

score: 0
Accepted
time: 36ms
memory: 160108kb

input:

22 332524739 654888401

output:

410922781

result:

ok 1 number(s): "410922781"

Test #8:

score: 0
Accepted
time: 24ms
memory: 160028kb

input:

26 302215049 566649113

output:

221720840

result:

ok 1 number(s): "221720840"

Test #9:

score: 0
Accepted
time: 16ms
memory: 160120kb

input:

15 111009527 722130737

output:

648834664

result:

ok 1 number(s): "648834664"

Test #10:

score: 0
Accepted
time: 19ms
memory: 160096kb

input:

82 110032063 394529383

output:

111730592

result:

ok 1 number(s): "111730592"

Test #11:

score: 0
Accepted
time: 8ms
memory: 160108kb

input:

9 11172911 259650437

output:

68381774

result:

ok 1 number(s): "68381774"

Test #12:

score: 0
Accepted
time: 24ms
memory: 160128kb

input:

86 12016027 354886243

output:

263687778

result:

ok 1 number(s): "263687778"

Test #13:

score: 0
Accepted
time: 38ms
memory: 160032kb

input:

91 273689959 454097881

output:

114436127

result:

ok 1 number(s): "114436127"

Test #14:

score: 0
Accepted
time: 16ms
memory: 160124kb

input:

73 148878967 694206977

output:

176215101

result:

ok 1 number(s): "176215101"

Test #15:

score: 0
Accepted
time: 16ms
memory: 160172kb

input:

45 205982233 227598247

output:

156769598

result:

ok 1 number(s): "156769598"

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #16:

score: 10
Accepted
time: 28ms
memory: 160084kb

input:

2778 122825869 147297463

output:

43419574

result:

ok 1 number(s): "43419574"

Test #17:

score: 0
Accepted
time: 13ms
memory: 160000kb

input:

289 7729669 589652893

output:

552952137

result:

ok 1 number(s): "552952137"

Test #18:

score: 0
Accepted
time: 33ms
memory: 160060kb

input:

2281 35651417 203950963

output:

21659018

result:

ok 1 number(s): "21659018"

Test #19:

score: 0
Accepted
time: 16ms
memory: 160124kb

input:

1684 258745639 373223677

output:

355596229

result:

ok 1 number(s): "355596229"

Test #20:

score: 0
Accepted
time: 24ms
memory: 160060kb

input:

2107 86850989 455823859

output:

245960059

result:

ok 1 number(s): "245960059"

Test #21:

score: 0
Accepted
time: 12ms
memory: 160028kb

input:

1323 43290799 791120419

output:

509649562

result:

ok 1 number(s): "509649562"

Test #22:

score: 0
Accepted
time: 12ms
memory: 160096kb

input:

2401 34064903 185314627

output:

70571452

result:

ok 1 number(s): "70571452"

Test #23:

score: 0
Accepted
time: 34ms
memory: 160060kb

input:

1073 82288187 564447959

output:

168200843

result:

ok 1 number(s): "168200843"

Test #24:

score: 0
Accepted
time: 15ms
memory: 160008kb

input:

1926 29995039 129122281

output:

60921463

result:

ok 1 number(s): "60921463"

Test #25:

score: 0
Accepted
time: 36ms
memory: 160004kb

input:

3000 66915659 765705179

output:

222619979

result:

ok 1 number(s): "222619979"

Subtask #4:

score: 20
Accepted

Test #26:

score: 20
Accepted
time: 232ms
memory: 160092kb

input:

998818 198334853 998244353

output:

153251445

result:

ok 1 number(s): "153251445"

Test #27:

score: 0
Accepted
time: 211ms
memory: 160112kb

input:

914379 128814383 998244353

output:

477606145

result:

ok 1 number(s): "477606145"

Test #28:

score: 0
Accepted
time: 226ms
memory: 160080kb

input:

944474 478445339 998244353

output:

174204073

result:

ok 1 number(s): "174204073"

Test #29:

score: 0
Accepted
time: 205ms
memory: 160000kb

input:

948637 711592127 998244353

output:

178256114

result:

ok 1 number(s): "178256114"

Test #30:

score: 0
Accepted
time: 203ms
memory: 160096kb

input:

927564 14465663 998244353

output:

315244613

result:

ok 1 number(s): "315244613"

Test #31:

score: 0
Accepted
time: 218ms
memory: 160216kb

input:

934615 392799073 998244353

output:

892700270

result:

ok 1 number(s): "892700270"

Test #32:

score: 0
Accepted
time: 205ms
memory: 160052kb

input:

917196 124972031 998244353

output:

782017412

result:

ok 1 number(s): "782017412"

Test #33:

score: 0
Accepted
time: 205ms
memory: 160052kb

input:

957149 392606173 998244353

output:

159348443

result:

ok 1 number(s): "159348443"

Test #34:

score: 0
Accepted
time: 227ms
memory: 160208kb

input:

997042 184649453 998244353

output:

464643024

result:

ok 1 number(s): "464643024"

Test #35:

score: 0
Accepted
time: 214ms
memory: 160168kb

input:

953353 14071961 998244353

output:

391688875

result:

ok 1 number(s): "391688875"

Subtask #5:

score: 0
Time Limit Exceeded

Test #36:

score: 10
Accepted
time: 1999ms
memory: 160108kb

input:

9909956 720431399 720431401

output:

86883659

result:

ok 1 number(s): "86883659"

Test #37:

score: 0
Accepted
time: 1983ms
memory: 160032kb

input:

9924163 267052829 267052831

output:

75754681

result:

ok 1 number(s): "75754681"

Test #38:

score: 0
Accepted
time: 1961ms
memory: 160036kb

input:

9967885 197873129 197873131

output:

16653739

result:

ok 1 number(s): "16653739"

Test #39:

score: 0
Accepted
time: 1949ms
memory: 160208kb

input:

9952642 101872151 101872153

output:

0

result:

ok 1 number(s): "0"

Test #40:

score: 0
Accepted
time: 1949ms
memory: 160120kb

input:

9955909 167874431 167874433

output:

130012020

result:

ok 1 number(s): "130012020"

Test #41:

score: 0
Accepted
time: 1958ms
memory: 160084kb

input:

9994785 399509567 399509569

output:

153324498

result:

ok 1 number(s): "153324498"

Test #42:

score: -10
Time Limit Exceeded

input:

9954011 108819131 108819133

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%