QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104602 | #117. Asceticism | lmeowdn | 100 ✓ | 14ms | 10784kb | C++14 | 1.3kb | 2023-05-11 11:51:52 | 2023-05-11 11:51:55 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=3e5+9,mod=1e9+7;
int n,m,fac[N],ifac[N],inv[N],ans;
int ksm(int x,int y,int res=1) {
for(;y;y>>=1,x=x*x%mod) if(y%2==1) res=res*x%mod;
return res;
}
void pre(int n) {
inv[0]=inv[1]=fac[0]=ifac[0]=1;
rep(i,1,n) fac[i]=fac[i-1]*i%mod;
ifac[n]=ksm(fac[n],mod-2);
per(i,n-1,1) ifac[i]=ifac[i+1]*(i+1)%mod;
rep(i,2,n) inv[i]=ifac[i]*fac[i-1]%mod;
}
int C(int x,int y) {
if(x<0||y<0||x<y) return 0;
else return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
signed main() {
n=read(), m=read()-1;
pre(300000);
rep(i,0,n) {
int w=ksm(i,n)*C(n+1,m+i+1)%mod;
if((n+m+i)&1) ans=(ans+mod-w)%mod;
else ans=(ans+w)%mod;
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 2ms
memory: 10512kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 10512kb
input:
10 10
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 2ms
memory: 10500kb
input:
10 2
output:
1013
result:
ok single line: '1013'
Test #4:
score: 0
Accepted
time: 5ms
memory: 10784kb
input:
10 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 4ms
memory: 10656kb
input:
10 7
output:
455192
result:
ok single line: '455192'
Test #6:
score: 0
Accepted
time: 3ms
memory: 10528kb
input:
8 3
output:
4293
result:
ok single line: '4293'
Test #7:
score: 0
Accepted
time: 1ms
memory: 10484kb
input:
9 6
output:
88234
result:
ok single line: '88234'
Test #8:
score: 0
Accepted
time: 1ms
memory: 10580kb
input:
3 3
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 4ms
memory: 10492kb
input:
5 2
output:
26
result:
ok single line: '26'
Test #10:
score: 0
Accepted
time: 4ms
memory: 10512kb
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: 0ms
memory: 10508kb
input:
100 48
output:
491709703
result:
ok single line: '491709703'
Test #12:
score: 0
Accepted
time: 4ms
memory: 10660kb
input:
300 1
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 0ms
memory: 10580kb
input:
300 2
output:
322050458
result:
ok single line: '322050458'
Test #14:
score: 0
Accepted
time: 4ms
memory: 10708kb
input:
300 123
output:
562526258
result:
ok single line: '562526258'
Test #15:
score: 0
Accepted
time: 8ms
memory: 10708kb
input:
300 295
output:
713150320
result:
ok single line: '713150320'
Test #16:
score: 0
Accepted
time: 4ms
memory: 10616kb
input:
300 300
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 4ms
memory: 10624kb
input:
199 28
output:
168902681
result:
ok single line: '168902681'
Test #18:
score: 0
Accepted
time: 4ms
memory: 10784kb
input:
253 152
output:
68568956
result:
ok single line: '68568956'
Test #19:
score: 0
Accepted
time: 3ms
memory: 10468kb
input:
135 124
output:
736486204
result:
ok single line: '736486204'
Test #20:
score: 0
Accepted
time: 4ms
memory: 10464kb
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: 5ms
memory: 10784kb
input:
1000 1
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 9ms
memory: 10512kb
input:
1000 2
output:
688422209
result:
ok single line: '688422209'
Test #23:
score: 0
Accepted
time: 0ms
memory: 10608kb
input:
1000 452
output:
103920245
result:
ok single line: '103920245'
Test #24:
score: 0
Accepted
time: 2ms
memory: 10488kb
input:
1000 504
output:
359395606
result:
ok single line: '359395606'
Test #25:
score: 0
Accepted
time: 0ms
memory: 10588kb
input:
1000 952
output:
419943092
result:
ok single line: '419943092'
Test #26:
score: 0
Accepted
time: 4ms
memory: 10528kb
input:
1000 998
output:
945760313
result:
ok single line: '945760313'
Test #27:
score: 0
Accepted
time: 4ms
memory: 10584kb
input:
1000 1000
output:
1
result:
ok single line: '1'
Test #28:
score: 0
Accepted
time: 10ms
memory: 10488kb
input:
603 536
output:
797752199
result:
ok single line: '797752199'
Test #29:
score: 0
Accepted
time: 3ms
memory: 10500kb
input:
194 115
output:
19316534
result:
ok single line: '19316534'
Test #30:
score: 0
Accepted
time: 3ms
memory: 10468kb
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: 9ms
memory: 10704kb
input:
100000 1
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 7ms
memory: 10456kb
input:
100000 5
output:
979545239
result:
ok single line: '979545239'
Test #33:
score: 0
Accepted
time: 6ms
memory: 10624kb
input:
100000 4532
output:
464105997
result:
ok single line: '464105997'
Test #34:
score: 0
Accepted
time: 9ms
memory: 10468kb
input:
100000 15064
output:
85875203
result:
ok single line: '85875203'
Test #35:
score: 0
Accepted
time: 14ms
memory: 10468kb
input:
100000 82952
output:
171676250
result:
ok single line: '171676250'
Test #36:
score: 0
Accepted
time: 13ms
memory: 10580kb
input:
100000 92998
output:
252841334
result:
ok single line: '252841334'
Test #37:
score: 0
Accepted
time: 9ms
memory: 10468kb
input:
100000 100000
output:
1
result:
ok single line: '1'
Test #38:
score: 0
Accepted
time: 1ms
memory: 10704kb
input:
16203 12361
output:
474349653
result:
ok single line: '474349653'
Test #39:
score: 0
Accepted
time: 6ms
memory: 10652kb
input:
72194 31523
output:
417377353
result:
ok single line: '417377353'
Test #40:
score: 0
Accepted
time: 4ms
memory: 10464kb
input:
99254 39532
output:
188863122
result:
ok single line: '188863122'
Extra Test:
score: 0
Extra Test Passed