QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#517820 | #8325. 重塑时光 | bribritt | 20 | 2ms | 3824kb | C++17 | 1.3kb | 2024-08-13 14:02:13 | 2024-08-13 14:02:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int exp(int a, int b) {
if(!b) return 1;
return (1LL*exp(1LL*a*a%MOD,b>>1)*(b&1?a:1))%MOD;
}
/*
int dp[15][14][14][1<<14]; // how many sequences of length i, j pairs, last guy k, bitmask l
main() {
for(int n=1;n<14;n++) {
dp[0][0][n-1][0]=1;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) for(int l=0;l<(1<<n);l++) for(int o=0;o<n;o++) if(!(l&(1<<o)) && j+(o==k+1)<n) {
dp[i+1][j+(o==k+1)][o][l|(1<<o)]+=dp[i][j][k][l];
if(dp[i+1][j+(o==k+1)][o][l|(1<<o)]>=MOD) dp[i+1][j+(o==k+1)][o][l|(1<<o)]-=MOD;
}
cout << "{";
int s = 0;
for(int j=0;j<n;j++)
for(int j=0;j<n;j++) cout<<dp[n][j]
}
}
main()
*/
vector<int> adj[15];
int fact[16];
main() {
fact[0]=1; for(int i=1;i<16;i++) fact[i]=(1LL*fact[i-1]*i)%MOD;
int n, m, k; cin >> n >> m >> k;
for(int i=0,x,y;i<m;i++) {cin>>x>>y;adj[x-1].push_back(y-1);}
int dp[1<<n]; fill(dp,dp+(1<<n),0); dp[0]=1;
for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) if(!(i&(1<<j))){
bool ok = 1;
for(auto k: adj[j]) if(!(i&(1<<k))) ok=0;
if(ok) if((dp[i|(1<<j)]+=dp[i])>=MOD) dp[i|(1<<j)]-=MOD;
}
cout << (1LL*dp[(1<<n)-1]*exp(fact[n],MOD-2))%MOD<<"\n";
}
详细
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3620kb
input:
3 2 0 1 2 1 3
output:
333333336
result:
ok single line: '333333336'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3616kb
input:
5 7 5 1 4 2 3 1 2 4 5 2 5 2 4 1 5
output:
425000003
result:
wrong answer 1st lines differ - expected: '895039689', found: '425000003'
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 3668kb
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:
153846155
result:
wrong answer 1st lines differ - expected: '76923078', found: '153846155'
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 3788kb
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:
71428572
result:
wrong answer 1st lines differ - expected: '535714290', found: '71428572'
Test #5:
score: 5
Accepted
time: 1ms
memory: 3632kb
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:
700595243
result:
ok single line: '700595243'
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 3716kb
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:
530784497
result:
wrong answer 1st lines differ - expected: '465070080', found: '530784497'
Test #7:
score: 5
Accepted
time: 0ms
memory: 3668kb
input:
13 0 13
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Wrong Answer
time: 2ms
memory: 3772kb
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:
320774361
result:
wrong answer 1st lines differ - expected: '4362623', found: '320774361'
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 3572kb
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:
862048066
result:
wrong answer 1st lines differ - expected: '426526937', found: '862048066'
Test #10:
score: 0
Wrong Answer
time: 0ms
memory: 3656kb
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:
438425929
result:
wrong answer 1st lines differ - expected: '214820829', found: '438425929'
Test #11:
score: 5
Accepted
time: 1ms
memory: 3740kb
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:
65784302
result:
ok single line: '65784302'
Test #12:
score: 0
Wrong Answer
time: 1ms
memory: 3600kb
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:
151688174
result:
wrong answer 1st lines differ - expected: '361557272', found: '151688174'
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 3712kb
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:
673280428
result:
wrong answer 1st lines differ - expected: '696132576', found: '673280428'
Test #14:
score: 0
Wrong Answer
time: 2ms
memory: 3760kb
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:
201182250
result:
wrong answer 1st lines differ - expected: '258614192', found: '201182250'
Test #15:
score: 0
Wrong Answer
time: 2ms
memory: 3756kb
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:
219194743
result:
wrong answer 1st lines differ - expected: '209616080', found: '219194743'
Test #16:
score: 0
Wrong Answer
time: 2ms
memory: 3640kb
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:
939640652
result:
wrong answer 1st lines differ - expected: '701202127', found: '939640652'
Test #17:
score: 0
Wrong Answer
time: 1ms
memory: 3672kb
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:
17857143
result:
wrong answer 1st lines differ - expected: '263013541', found: '17857143'
Test #18:
score: 0
Wrong Answer
time: 2ms
memory: 3824kb
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:
411111114
result:
wrong answer 1st lines differ - expected: '963180835', found: '411111114'
Test #19:
score: 0
Wrong Answer
time: 2ms
memory: 3696kb
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:
251163719
result:
wrong answer 1st lines differ - expected: '722208430', found: '251163719'
Test #20:
score: 0
Wrong Answer
time: 0ms
memory: 3756kb
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
output:
269108671
result:
wrong answer 1st lines differ - expected: '560801339', found: '269108671'