QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95973 | #117. Asceticism | tricyzhkx | 100 ✓ | 14ms | 5048kb | C++14 | 709b | 2023-04-12 19:16:41 | 2023-04-12 19:16:45 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
ll fac[100010],inv[100010];
ll C(int n,int m){return fac[n]*inv[n-m]%mod*inv[m]%mod;}
ll power(ll a,int b)
{
ll ans=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) ans=ans*a%mod;
return ans;
}
int calc(int n,int m)
{
int ans=0;
for(int i=0;i<m;i++) ans=(ans+(i&1?mod-C(n,i):C(n,i))*power(m-i,n))%mod;
return ans;
}
int main()
{
int n,m;
cin>>n>>m;
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++) fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%mod;
cout<<(calc(n,m)-calc(n,m-1)+mod)%mod<<endl;
return 0;
}
詳細信息
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 2ms
memory: 3312kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3240kb
input:
10 10
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
10 2
output:
1013
result:
ok single line: '1013'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3244kb
input:
10 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
10 7
output:
455192
result:
ok single line: '455192'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3380kb
input:
8 3
output:
4293
result:
ok single line: '4293'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3328kb
input:
9 6
output:
88234
result:
ok single line: '88234'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
3 3
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
5 2
output:
26
result:
ok single line: '26'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
7 5
output:
1191
result:
ok single line: '1191'
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #11:
score: 20
Accepted
time: 2ms
memory: 3344kb
input:
100 48
output:
491709703
result:
ok single line: '491709703'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
300 1
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3312kb
input:
300 2
output:
322050458
result:
ok single line: '322050458'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3248kb
input:
300 123
output:
562526258
result:
ok single line: '562526258'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
300 295
output:
713150320
result:
ok single line: '713150320'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3316kb
input:
300 300
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3332kb
input:
199 28
output:
168902681
result:
ok single line: '168902681'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
253 152
output:
68568956
result:
ok single line: '68568956'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3368kb
input:
135 124
output:
736486204
result:
ok single line: '736486204'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
13 11
output:
1479726
result:
ok single line: '1479726'
Subtask #3:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #21:
score: 25
Accepted
time: 2ms
memory: 3548kb
input:
1000 1
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
1000 2
output:
688422209
result:
ok single line: '688422209'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3448kb
input:
1000 452
output:
103920245
result:
ok single line: '103920245'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3384kb
input:
1000 504
output:
359395606
result:
ok single line: '359395606'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3264kb
input:
1000 952
output:
419943092
result:
ok single line: '419943092'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
1000 998
output:
945760313
result:
ok single line: '945760313'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3452kb
input:
1000 1000
output:
1
result:
ok single line: '1'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3316kb
input:
603 536
output:
797752199
result:
ok single line: '797752199'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3320kb
input:
194 115
output:
19316534
result:
ok single line: '19316534'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3364kb
input:
995 965
output:
79761626
result:
ok single line: '79761626'
Subtask #4:
score: 51
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #31:
score: 51
Accepted
time: 2ms
memory: 4988kb
input:
100000 1
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 4ms
memory: 4920kb
input:
100000 5
output:
979545239
result:
ok single line: '979545239'
Test #33:
score: 0
Accepted
time: 5ms
memory: 5048kb
input:
100000 4532
output:
464105997
result:
ok single line: '464105997'
Test #34:
score: 0
Accepted
time: 3ms
memory: 4864kb
input:
100000 15064
output:
85875203
result:
ok single line: '85875203'
Test #35:
score: 0
Accepted
time: 8ms
memory: 4864kb
input:
100000 82952
output:
171676250
result:
ok single line: '171676250'
Test #36:
score: 0
Accepted
time: 14ms
memory: 4864kb
input:
100000 92998
output:
252841334
result:
ok single line: '252841334'
Test #37:
score: 0
Accepted
time: 11ms
memory: 4988kb
input:
100000 100000
output:
1
result:
ok single line: '1'
Test #38:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
16203 12361
output:
474349653
result:
ok single line: '474349653'
Test #39:
score: 0
Accepted
time: 7ms
memory: 4472kb
input:
72194 31523
output:
417377353
result:
ok single line: '417377353'
Test #40:
score: 0
Accepted
time: 8ms
memory: 4868kb
input:
99254 39532
output:
188863122
result:
ok single line: '188863122'
Extra Test:
score: 0
Extra Test Passed