QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673933#5274. IQ GameIllusionaryDominance#ML 5ms4140kbC++202.0kb2024-10-25 11:55:432024-10-25 11:55:44

Judging History

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

  • [2024-10-25 11:55:44]
  • 评测
  • 测评结果:ML
  • 用时:5ms
  • 内存:4140kb
  • [2024-10-25 11:55:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(x) (x).begin(), (x).end()

const int p=998244353;
int n, k, s;
int f[205][205];
int pw[205][205];
// int C[205][205];

int fpow(int x, int y)
{
    int r=1;
    for(;y;y>>=1,x=(ll)x*x%p) if(y&1) r=(ll)r*x%p;
    return r;
}


int main()
{
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    cin>>n>>k>>s;
    vector<int> a(k);
    for(int i=0;i<k;++i) cin>>a[i], a.push_back(a[i]);
    if(k==1)
    {
        cout<<"1\n";
        exit(0);
    }
    int I=lower_bound(a.begin(), a.begin()+k, s)-a.begin();
    vector<int> b(k), pre(k);
    b[0]=(s+n-a[I+k-1])%n;
    for(int i=1;i<k;++i) b[i]=(a[I+i]+n-a[I+i-1])%n;
    reverse(b.begin()+1, b.end());
    
    // for(int i=0;i<k;++i) cerr << b[i] << " ";
    //1 2 
    
    for(int i=0;i<k;++i)
    {
        pw[i][0]=1;
        for(int j=1;j<=k;++j) pw[i][j]=(ll)pw[i][j-1]*b[i]%p;
    }
    
    // for(int i=0;i<=200;++i)
    // {
    //     C[i][0]=C[i][i]=1;
    //     for(int j=1;j<i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    // }
    
    // for(int i=1;i<k;++i) pre[i]=pre[i-1]+b[i];
    
    f[0][0]=1;
    
    vector<int> fac(n+1), inv(n+1);
    fac[0]=1; inv[0]=inv[1]=1;
    for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%p;
    for(int i=2;i<=n;++i) inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    for(int i=1;i<=n;++i) inv[i]=(ll)inv[i-1]*inv[i]%p;
    
    for(int i=0;i<k-1;++i)
    for(int j=0;j<=i;++j)
    {
        for(int kk=0;kk<=i+1-j;++kk)
        {
            // cerr<<kk<<" "<<i+1-j<<"?\n";
            f[i+1][j+kk]=(f[i+1][j+kk]+(ll)f[i][j]*pw[i+1][kk]%p*inv[kk]%p)%p;
            // cerr<<i+1<<" "<<j<<" "<<j+kk<<" "<<f[i+1][j+kk]<<"\n";
        }
    }
    
    int ans=1;
    int invn=fpow(n, p-2);
    
    // cerr<<f[1][1]<<"\n";
    
    
    for(int i=1;i<k;++i)
    {
        // cerr << f[k-1][i] << " " << fpow(invn, i) << "\n";
        ans=(ans+(ll)f[k-1][i]*fpow(invn, i)%p*fac[i]%p)%p;
    }
    
    cout<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

input:

3 2 3
2 3

output:

665496237

result:

ok 1 number(s): "665496237"

Test #2:

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

input:

6 3 4
1 2 4

output:

582309208

result:

ok 1 number(s): "582309208"

Test #3:

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

input:

8 8 5
1 2 3 4 5 6 7 8

output:

499122181

result:

ok 1 number(s): "499122181"

Test #4:

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

input:

1 1 1
1

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 1 2
2

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

2 2 1
1 2

output:

499122178

result:

ok 1 number(s): "499122178"

Test #7:

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

input:

3 1 2
2

output:

1

result:

ok 1 number(s): "1"

Test #8:

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

input:

3 2 3
1 3

output:

332748119

result:

ok 1 number(s): "332748119"

Test #9:

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

input:

3 3 1
1 2 3

output:

2

result:

ok 1 number(s): "2"

Test #10:

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

input:

3 3 3
1 2 3

output:

2

result:

ok 1 number(s): "2"

Test #11:

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

input:

4 1 4
4

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

4 2 4
2 4

output:

499122178

result:

ok 1 number(s): "499122178"

Test #13:

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

input:

4 3 3
2 3 4

output:

935854083

result:

ok 1 number(s): "935854083"

Test #14:

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

input:

4 4 1
1 2 3 4

output:

499122179

result:

ok 1 number(s): "499122179"

Test #15:

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

input:

4 4 4
1 2 3 4

output:

499122179

result:

ok 1 number(s): "499122179"

Test #16:

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

input:

5 1 4
4

output:

1

result:

ok 1 number(s): "1"

Test #17:

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

input:

5 3 4
2 3 4

output:

199648873

result:

ok 1 number(s): "199648873"

Test #18:

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

input:

5 5 3
1 2 3 4 5

output:

3

result:

ok 1 number(s): "3"

Test #19:

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

input:

10 2 3
3 10

output:

99824437

result:

ok 1 number(s): "99824437"

Test #20:

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

input:

10 6 10
2 5 6 7 8 10

output:

146103047

result:

ok 1 number(s): "146103047"

Test #21:

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

input:

10 9 4
1 2 3 4 5 7 8 9 10

output:

463868913

result:

ok 1 number(s): "463868913"

Test #22:

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

input:

50 3 37
8 37 49

output:

411276675

result:

ok 1 number(s): "411276675"

Test #23:

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

input:

50 10 13
1 13 20 27 28 32 34 35 49 50

output:

221421997

result:

ok 1 number(s): "221421997"

Test #24:

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

input:

50 25 12
1 4 5 10 11 12 14 16 19 21 22 27 28 29 30 31 33 34 37 38 39 45 47 49 50

output:

754768470

result:

ok 1 number(s): "754768470"

Test #25:

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

input:

50 40 22
2 3 4 5 6 7 8 12 13 14 15 17 18 19 20 21 22 23 24 25 26 28 29 30 31 32 33 34 35 36 37 39 40 41 42 43 45 46 47 50

output:

16385632

result:

ok 1 number(s): "16385632"

Test #26:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

50 49 29
1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

output:

501281691

result:

ok 1 number(s): "501281691"

Test #27:

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

input:

200 1 28
28

output:

1

result:

ok 1 number(s): "1"

Test #28:

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

input:

200 2 66
66 143

output:

454201182

result:

ok 1 number(s): "454201182"

Test #29:

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

input:

200 2 133
107 133

output:

209631316

result:

ok 1 number(s): "209631316"

Test #30:

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

input:

200 5 96
60 86 96 121 130

output:

713590253

result:

ok 1 number(s): "713590253"

Test #31:

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

input:

200 14 89
3 7 30 42 54 64 80 82 89 105 133 160 176 184

output:

105441194

result:

ok 1 number(s): "105441194"

Test #32:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

200 42 152
4 9 17 20 35 40 43 49 52 71 74 76 81 83 85 92 93 97 98 104 111 113 124 132 134 139 140 141 144 148 149 151 152 153 157 164 172 181 192 195 199 200

output:

547988971

result:

ok 1 number(s): "547988971"

Test #33:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

200 132 98
2 3 6 7 8 15 16 17 18 20 22 23 26 27 28 30 31 32 34 35 36 38 39 41 44 45 46 48 50 53 54 55 56 57 58 59 60 61 64 68 69 72 73 76 77 78 79 81 82 83 84 85 86 87 88 89 92 95 96 97 98 100 102 103 104 105 106 107 108 109 110 112 114 115 116 119 120 121 122 123 124 125 127 130 131 133 134 135 136...

output:

697737806

result:

ok 1 number(s): "697737806"

Test #34:

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

input:

200 199 1
1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

544578651

result:

ok 1 number(s): "544578651"

Test #35:

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

input:

200 199 200
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 95 96 97 98 99 100...

output:

492091840

result:

ok 1 number(s): "492091840"

Test #36:

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

input:

200 200 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

499122277

result:

ok 1 number(s): "499122277"

Test #37:

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

input:

200 200 200
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

499122277

result:

ok 1 number(s): "499122277"

Test #38:

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

input:

1000000000 1 584008146
584008146

output:

1

result:

ok 1 number(s): "1"

Test #39:

score: -100
Memory Limit Exceeded

input:

1000000000 2 143634686
143634686 490248799

output:


result: