QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#517689 | #8325. 重塑时光 | kymmykym | 0 | 418ms | 136100kb | C++14 | 864b | 2024-08-13 13:14:31 | 2024-08-13 13:14:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1'000'000'007;
int qexp(int a, int b){
int res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
int inv(int x){
return qexp(x,mod-2);
}
int F[20];
int32_t main(){
F[0]=1;
for(int i=1;i<20;i++){
F[i]=F[i-1]*i%mod;
}
int n,m,k;cin>>n>>m>>k;
int S=n+k;
vector<int>choices;
for(int i=0;i<1<<S;i++){
if(__builtin_popcount(i) == k){ // cuts
choices.push_back(i);
}
}
int tot=choices.size();
int ans=0;
for(auto x:choices){
int ways=0;
for(int j=0;j<S;j++){
if(x & (1<<j) == 0){//not a cut
if(j == 0 || (x & (1<<(j-1)))){ // previous guy was cut
++ways;
}
}
}
ways=ways*F[n-1]%mod;
ans=(ans+ways%mod)%mod;
}
cout<<ans*inv(F[n])%mod*inv(tot)%mod;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3508kb
input:
3 2 0 1 2 1 3
output:
0
result:
wrong answer 1st lines differ - expected: '333333336', found: '0'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3444kb
input:
5 7 5 1 4 2 3 1 2 4 5 2 5 2 4 1 5
output:
0
result:
wrong answer 1st lines differ - expected: '895039689', found: '0'
Test #3:
score: 0
Wrong Answer
time: 418ms
memory: 136008kb
input:
13 12 13 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13
output:
0
result:
wrong answer 1st lines differ - expected: '76923078', found: '0'
Test #4:
score: 0
Time Limit Exceeded
input:
14 13 14 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14
output:
result:
Test #5:
score: 0
Wrong Answer
time: 1ms
memory: 3524kb
input:
14 13 0 2 9 1 2 1 3 3 8 6 11 2 7 1 5 5 12 2 13 3 14 3 10 3 6 2 4
output:
0
result:
wrong answer 1st lines differ - expected: '700595243', found: '0'
Test #6:
score: 0
Time Limit Exceeded
input:
14 13 14 9 11 2 9 5 10 4 6 10 13 2 3 2 7 4 12 2 4 3 8 7 14 3 5 1 2
output:
result:
Test #7:
score: 0
Wrong Answer
time: 406ms
memory: 136080kb
input:
13 0 13
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Test #8:
score: 0
Time Limit Exceeded
input:
14 91 14 3 4 2 10 3 10 1 13 6 8 5 6 10 13 7 8 4 9 4 7 3 7 13 14 2 12 1 3 6 9 9 14 1 10 2 9 7 11 9 11 3 12 8 10 4 13 5 9 11 12 5 14 8 12 8 13 5 13 1 5 6 11 9 13 2 5 1 14 7 14 4 14 3 5 5 11 6 12 1 2 7 10 1 4 1 8 6 10 3 8 6 13 10 14 7 12 10 11 2 13 8 11 11 13 6 7 10 12 3 14 4 5 1 6 2 14 5 10 8 14 4 8 1...
output:
result:
Test #9:
score: 0
Wrong Answer
time: 2ms
memory: 3712kb
input:
9 15 9 1 2 3 5 2 8 4 8 1 4 2 5 2 7 4 5 1 9 6 8 6 9 1 3 3 7 5 9 5 8
output:
0
result:
wrong answer 1st lines differ - expected: '426526937', found: '0'
Test #10:
score: 0
Wrong Answer
time: 2ms
memory: 3928kb
input:
9 14 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 4 5 6 8 4 7 6 7 3 8 4 6
output:
0
result:
wrong answer 1st lines differ - expected: '214820829', found: '0'
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3756kb
input:
13 68 0 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 6 7 6 8 6 9 6 10 6 11 6 12 6 13 7 8 7 10 7 11 7 12 7 13 8 13 9 10 9 11 9 12 9 13...
output:
0
result:
wrong answer 1st lines differ - expected: '65784302', found: '0'
Test #12:
score: 0
Wrong Answer
time: 409ms
memory: 136100kb
input:
13 39 13 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 4 8 4 9 4 10 4 12 4 13 5 6 5 7 5 10 5 11 5 13 6 7 6 11 6 13 8 9 8 12 8 13 11 13
output:
0
result:
wrong answer 1st lines differ - expected: '361557272', found: '0'
Test #13:
score: 0
Time Limit Exceeded
input:
14 11 14 2 13 4 11 4 14 5 14 6 9 6 14 7 11 9 14 10 12 10 14 12 14
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
14 46 14 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 2 9 2 10 2 11 2 13 2 14 3 4 3 6 3 10 3 11 3 12 3 13 3 14 4 6 4 10 4 11 4 12 4 13 4 14 5 7 5 8 5 9 5 11 5 13 5 14 7 8 7 9 7 14 10 11 10 13 10 14 11 13 11 14 13 14
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
14 70 14 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 2 3 2 4 2 5 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 3 11 3 13 3 14 4 5 4 7 4 8 4 10 4 11 4 12 4 13 4 14 5 7 5 8 5 10 5 12 5 13 5 14 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 7 8 7 10 7 12 7 13 7 14 8 10 8 12 8 13 8 14 9 11 9 12 9 13 9 14 10 1...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
14 69 14 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 2 3 2 5 2 6 2 7 2 9 2 10 2 11 2 12 2 13 2 14 3 5 3 6 3 7 3 9 3 10 3 11 3 12 3 13 3 14 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 5 6 5 7 5 9 5 10 5 11 5 12 5 13 5 14 6 7 6 9 6 10 6 11 6 12 6 13 6 14 7 9 7 10 7 11 7 12 7 13 7 14 8 12 8 13 8 14 9 10 ...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
14 15 14 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 4 6 5 9
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
15 17 15 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 3 13 3 15 13 15
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
15 17 15 1 2 1 3 1 4 1 5 1 6 1 7 1 12 1 15 7 12 7 15 8 15 9 15 10 15 11 15 12 15 13 15 14 15
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
15 16 15 1 2 1 3 1 10 2 10 3 10 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 4 15