QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #67499 | #4692. 解锁屏幕 | alpha1022 | 100 ✓ | 579ms | 124576kb | C++23 | 1.7kb | 2022-12-10 16:39:45 | 2022-12-10 16:39:45 |
Judging History
answer
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define mod 100000007
using namespace std;
int n,full,g[30][30][30],d[30][30];
long long f[(1 << 20) + 10][30],ans;
struct node
{
int x,y;
inline bool operator<(const node &a) const
{
if(x == a.x)
return y < a.y;
return x < a.x;
}
} a[30];
inline bool check(int s,int f,int t)
{
for(register int i = 1;i <= d[f][t];++i)
if(!((s >> g[f][t][i] - 1) & 1))
return 0;
return 1;
}
int main()
{
scanf("%d",&n);
full = (1 << n) - 1;
for(register int i = 1;i <= n;++i)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a + 1,a + n + 1);
for(register int i = 1;i <= n;++i)
{
f[1 << i - 1][i] = 1;
for(register int j = i + 1;j < n;++j)
for(register int k = j + 1;k <= n;++k)
if((double)(a[k].y - a[i].y) / (a[k].x - a[i].x) == (double)(a[k].y - a[j].y) / (a[k].x - a[j].x))
g[i][k][++d[i][k]] = j,g[k][i][++d[k][i]] = j;
}
for(register int i = 0;i <= full;++i)
for(register int j = 1;j <= n;++j)
if((i >> j - 1) & 1)
for(register int k = 1;k <= n;++k)
{
if((i >> k - 1) & 1)
continue;
if(check(i,j,k))
f[i | (1 << k - 1)][k] = (f[i | (1 << k - 1)][k] + f[i][j]) % mod;
}
for(register int i = 0;i <= full;++i)
if(__builtin_popcount(i) >= 4)
for(register int j = 1;j <= n;++j)
ans = (ans + f[i][j]) % mod;
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 1732kb
input:
7 100 200 120 240 -60 -1 100 100 200 100 10 -10 200 200
output:
13440
result:
ok 1 number(s): "13440"
Test #2:
score: 10
Accepted
time: 1ms
memory: 1776kb
input:
9 30 60 40 0 60 30 30 200 30 300 60 90 30 90 60 60 30 30
output:
346800
result:
ok 1 number(s): "346800"
Test #3:
score: 10
Accepted
time: 0ms
memory: 1888kb
input:
10 50 10 -30 0 9 0 30 10 10 0 40 10 -31 -1 -10 0 10 10 20 10
output:
3074686
result:
ok 1 number(s): "3074686"
Test #4:
score: 10
Accepted
time: 226ms
memory: 63108kb
input:
18 8 8 24 8 16 16 8 16 32 32 16 8 8 32 16 24 16 32 17 17 24 16 32 24 24 24 8 24 32 8 20 20 24 32 32 16
output:
99864133
result:
ok 1 number(s): "99864133"
Test #5:
score: 10
Accepted
time: 520ms
memory: 124476kb
input:
19 8 16 16 48 16 24 16 16 8 32 16 8 24 48 -8 16 24 40 16 32 16 40 8 40 8 8 8 24 24 16 24 8 8 48 24 24 24 32
output:
55200645
result:
ok 1 number(s): "55200645"
Test #6:
score: 10
Accepted
time: 472ms
memory: 124492kb
input:
19 24 0 -8 -15 0 0 56 8 48 8 -8 16 32 8 40 0 32 0 -8 15 16 0 48 0 8 0 16 8 40 8 0 8 24 8 8 8 56 0
output:
38087218
result:
ok 1 number(s): "38087218"
Test #7:
score: 10
Accepted
time: 547ms
memory: 124472kb
input:
19 6 0 0 -7 7 0 0 -8 0 -5 0 -4 8 0 1 0 2 0 9 0 0 -6 2 -2 0 -3 0 -2 5 0 0 0 3 0 4 0 0 -1
output:
19472496
result:
ok 1 number(s): "19472496"
Test #8:
score: 10
Accepted
time: 475ms
memory: 124460kb
input:
19 0 0 -100 0 100 0 0 100 0 -100 70 -70 70 70 -70 70 -70 -70 9 0 0 -9 -9 0 0 9 23 33 34 56 77 88 91 -3 4 0 0 -1
output:
32547904
result:
ok 1 number(s): "32547904"
Test #9:
score: 10
Accepted
time: 579ms
memory: 124528kb
input:
19 2 0 10 0 4 0 7 0 13 0 11 0 3 0 6 0 12 0 -2 2 -2 -2 0 0 2 -2 8 0 1 0 9 0 5 0 2 2 14 0
output:
24080827
result:
ok 1 number(s): "24080827"
Test #10:
score: 10
Accepted
time: 498ms
memory: 124576kb
input:
19 8 2 4 1 8 1 0 1 0 2 10 0 12 1 -8 1 4 2 8 0 16 1 0 0 -4 1 4 0 6 0 2 2 6 2 10 2 2 0
output:
60679719
result:
ok 1 number(s): "60679719"