QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72613#5031. 核Chinese_zjc_70 1997ms160344kbC++143.1kb2023-01-17 09:05:232023-01-17 09:06:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-17 09:06:00]
  • 评测
  • 测评结果:70
  • 用时:1997ms
  • 内存:160344kb
  • [2023-01-17 09:05:23]
  • 提交

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: 9ms
memory: 160204kb

input:

1 2 540053233

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 4ms
memory: 160100kb

input:

2 2 156542707

output:

43046970

result:

ok 1 number(s): "43046970"

Test #3:

score: 0
Accepted
time: 11ms
memory: 160200kb

input:

1 2 186225229

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 10ms
memory: 160100kb

input:

3 3 109884329

output:

100602209

result:

ok 1 number(s): "100602209"

Test #5:

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

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: 12ms
memory: 160164kb

input:

20 21992843 328859143

output:

110137213

result:

ok 1 number(s): "110137213"

Test #7:

score: 0
Accepted
time: 9ms
memory: 160200kb

input:

22 332524739 654888401

output:

410922781

result:

ok 1 number(s): "410922781"

Test #8:

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

input:

26 302215049 566649113

output:

221720840

result:

ok 1 number(s): "221720840"

Test #9:

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

input:

15 111009527 722130737

output:

648834664

result:

ok 1 number(s): "648834664"

Test #10:

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

input:

82 110032063 394529383

output:

111730592

result:

ok 1 number(s): "111730592"

Test #11:

score: 0
Accepted
time: 6ms
memory: 160152kb

input:

9 11172911 259650437

output:

68381774

result:

ok 1 number(s): "68381774"

Test #12:

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

input:

86 12016027 354886243

output:

263687778

result:

ok 1 number(s): "263687778"

Test #13:

score: 0
Accepted
time: 10ms
memory: 160164kb

input:

91 273689959 454097881

output:

114436127

result:

ok 1 number(s): "114436127"

Test #14:

score: 0
Accepted
time: 11ms
memory: 160316kb

input:

73 148878967 694206977

output:

176215101

result:

ok 1 number(s): "176215101"

Test #15:

score: 0
Accepted
time: 5ms
memory: 160164kb

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: 10ms
memory: 160096kb

input:

2778 122825869 147297463

output:

43419574

result:

ok 1 number(s): "43419574"

Test #17:

score: 0
Accepted
time: 14ms
memory: 160284kb

input:

289 7729669 589652893

output:

552952137

result:

ok 1 number(s): "552952137"

Test #18:

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

input:

2281 35651417 203950963

output:

21659018

result:

ok 1 number(s): "21659018"

Test #19:

score: 0
Accepted
time: 4ms
memory: 160164kb

input:

1684 258745639 373223677

output:

355596229

result:

ok 1 number(s): "355596229"

Test #20:

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

input:

2107 86850989 455823859

output:

245960059

result:

ok 1 number(s): "245960059"

Test #21:

score: 0
Accepted
time: 6ms
memory: 160288kb

input:

1323 43290799 791120419

output:

509649562

result:

ok 1 number(s): "509649562"

Test #22:

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

input:

2401 34064903 185314627

output:

70571452

result:

ok 1 number(s): "70571452"

Test #23:

score: 0
Accepted
time: 0ms
memory: 160164kb

input:

1073 82288187 564447959

output:

168200843

result:

ok 1 number(s): "168200843"

Test #24:

score: 0
Accepted
time: 6ms
memory: 160160kb

input:

1926 29995039 129122281

output:

60921463

result:

ok 1 number(s): "60921463"

Test #25:

score: 0
Accepted
time: 3ms
memory: 160156kb

input:

3000 66915659 765705179

output:

222619979

result:

ok 1 number(s): "222619979"

Subtask #4:

score: 20
Accepted

Test #26:

score: 20
Accepted
time: 206ms
memory: 160208kb

input:

998818 198334853 998244353

output:

153251445

result:

ok 1 number(s): "153251445"

Test #27:

score: 0
Accepted
time: 199ms
memory: 160160kb

input:

914379 128814383 998244353

output:

477606145

result:

ok 1 number(s): "477606145"

Test #28:

score: 0
Accepted
time: 186ms
memory: 160136kb

input:

944474 478445339 998244353

output:

174204073

result:

ok 1 number(s): "174204073"

Test #29:

score: 0
Accepted
time: 217ms
memory: 160204kb

input:

948637 711592127 998244353

output:

178256114

result:

ok 1 number(s): "178256114"

Test #30:

score: 0
Accepted
time: 200ms
memory: 160164kb

input:

927564 14465663 998244353

output:

315244613

result:

ok 1 number(s): "315244613"

Test #31:

score: 0
Accepted
time: 196ms
memory: 160200kb

input:

934615 392799073 998244353

output:

892700270

result:

ok 1 number(s): "892700270"

Test #32:

score: 0
Accepted
time: 187ms
memory: 160340kb

input:

917196 124972031 998244353

output:

782017412

result:

ok 1 number(s): "782017412"

Test #33:

score: 0
Accepted
time: 193ms
memory: 160148kb

input:

957149 392606173 998244353

output:

159348443

result:

ok 1 number(s): "159348443"

Test #34:

score: 0
Accepted
time: 204ms
memory: 160100kb

input:

997042 184649453 998244353

output:

464643024

result:

ok 1 number(s): "464643024"

Test #35:

score: 0
Accepted
time: 197ms
memory: 160164kb

input:

953353 14071961 998244353

output:

391688875

result:

ok 1 number(s): "391688875"

Subtask #5:

score: 10
Accepted

Test #36:

score: 10
Accepted
time: 1924ms
memory: 160160kb

input:

9909956 720431399 720431401

output:

86883659

result:

ok 1 number(s): "86883659"

Test #37:

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

input:

9924163 267052829 267052831

output:

75754681

result:

ok 1 number(s): "75754681"

Test #38:

score: 0
Accepted
time: 1956ms
memory: 160156kb

input:

9967885 197873129 197873131

output:

16653739

result:

ok 1 number(s): "16653739"

Test #39:

score: 0
Accepted
time: 1929ms
memory: 160204kb

input:

9952642 101872151 101872153

output:

0

result:

ok 1 number(s): "0"

Test #40:

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

input:

9955909 167874431 167874433

output:

130012020

result:

ok 1 number(s): "130012020"

Test #41:

score: 0
Accepted
time: 1936ms
memory: 160196kb

input:

9994785 399509567 399509569

output:

153324498

result:

ok 1 number(s): "153324498"

Test #42:

score: 0
Accepted
time: 1929ms
memory: 160344kb

input:

9954011 108819131 108819133

output:

101671540

result:

ok 1 number(s): "101671540"

Test #43:

score: 0
Accepted
time: 1942ms
memory: 160164kb

input:

9997570 213315827 213315829

output:

57441081

result:

ok 1 number(s): "57441081"

Test #44:

score: 0
Accepted
time: 1945ms
memory: 160144kb

input:

9995867 113028299 113028301

output:

67837072

result:

ok 1 number(s): "67837072"

Test #45:

score: 0
Accepted
time: 1917ms
memory: 160152kb

input:

9909335 247275617 247275619

output:

202966817

result:

ok 1 number(s): "202966817"

Subtask #6:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #46:

score: 30
Accepted
time: 1997ms
memory: 160160kb

input:

9921815 38466881 725310841

output:

601117286

result:

ok 1 number(s): "601117286"

Test #47:

score: -30
Time Limit Exceeded

input:

9919464 4830599 747345523

output:


result: