Description
给你一个有 $n$ 个节点， $m$ 条边的 DAG 。
要求你在途中选择一条路径，可以只包含一个点，求有多少条路径满足路径上的点的编号积为平方数。
Solution
发现一个数若是完全平方数则它的每一个质因子的次数都是偶数。
于是我们可以对于每一个数分解质因数，然后 状压 DP 即可。
但是 90 以内的质数有 24 个，但是不要紧，因为因子里含有大于 45 的质数的数最多只有一个，就是它本身。
因为 45 以内的质数只有 14 个，我们就可以进行状压 DP 了。
设 $f[i][S]$ 表示当前在第 $i$ 个点，质因子状态为 $S$ 的路径条数。
对于次数大于 2 的，我们显然只需要记录下它的次数模 2 的值即可，因此 $S$ 是一个 01 串。
用 BFS 转移即可，起点选取所有入度为 0 的节点。
注意建边的时候不要建起点或终点的编号为大于 45 的质数的边。
时间复杂度 $O(2^{14} n^2)$ ，具体细节见代码部分。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| #include <cstdio>
#define maxN 100
#define maxM 8010
struct node{ long long x, y, g; } b[maxM];
long long f[maxN][1 << 15], val[maxN], dl[maxN], rd[maxN], h[maxN], a[maxN];
long long prime[15];
long long len = 0, n = 0, m = 0;
void ins (long long x, long long y)
{
len++;
b[len].x = x;
b[len].y = y;
b[len].g = h[x];
h[x] = len;
}
bool pd (long long x)
{
if(x < 2)
{
return false;
}
for(long long i = 2;i <= x - 1; i++)
{
if(!(x % i))
{
return false;
}
}
return true;
}
void bfs ()
{
long long ma = (1 << 14) - 1;
long long tou = 1, wei = 1;
for(long long i = 1;i <= n; i++)
{
if(!rd[i])
{
dl[wei] = i;
wei++;
}
}
while(tou != wei)
{
long long x = dl[tou];
for(long long i = h[x];i;i = b[i].g)
{
long long y = b[i].y;
if(a[y])
{
continue;
}
for(long long j = 0;j <= ma; j++)
{
f[y][j ^ val[y]] += f[x][j];
}
rd[y]--;
if(!rd[y])
{
dl[wei] = y;
wei++;
if(wei >= maxN)
{
wei = 1;
}
}
}
tou++;
if(tou >= maxN)
{
tou = 1;
}
}
}
int main ()
{
scanf("%lld %lld", &n, &m);
for(long long i = 1;i <= n / 2; i++)
{
if(pd(i))
{
prime[++prime[0]] = i;
}
}
for(long long i = n / 2 + 1;i <= n; i++)
{
if(pd(i))
{
a[i] = 1;
}
}
for(long long i = 1;i <= n; i++)
{
if(a[i])
{
continue;
}
long long now = i;
for(long long j = 1;j <= prime[0]; j++)
{
long long cc = 0;
while(!(now % prime[j]))
{
cc ^= 1;
now /= prime[j];
}
if(cc)
{
val[i] |= (1 << (j - 1));
}
}
}
for(long long i = 1;i <= m; i++)
{
long long x = 0, y = 0;
scanf("%lld %lld", &x, &y);
if(a[x] || a[y])
{
continue;
}
rd[y]++;
ins(x, y);
}
for(long long i = 1;i <= n; i++)
{
if(!a[i])
{
f[i][val[i]] = 1;
}
}
bfs();
long long ans = 0;
for(long long i = 1;i <= n; i++)
{
ans += f[i][0];
}
printf("%lld", ans);
return 0;
}
|