题意可以转化为：有多少个数不能通过题目中给出的操作使得自己的值变得比最开始更小。
然后考虑如果前一位填了 ，而且前面部分全都是合法的，那么后一位可以填哪些数字。假设这里填写了数字 ，则：
- 如果 之间不能互相交换，那么很显然可以填写 。
- 如果 之间可以互相交换，且 ，那么很显然不能填写 。
- 否则考虑交换 两个位置后， 可能可以和 之前的数继续发生交换，因此 能填写当且仅当在 的位置填写 合法。
然后就可以 dp 了。设 表示当前考虑了 集合，上一次可以填写的数的集合是 ，有多少个合法的前缀数。转移直接枚举下一个位置填的是什么数字即可。最终时间复杂度为 ，其中 。
namespace Loyalty
{
inline void init() {}
int mp[10][10], f[50010][1024], mark[10], mark2[10];
inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
{
int n, m;
cin >> n >> m;
while (m--)
{
int a, b;
cin >> a >> b;
mp[a][b] = mp[b][a] = 1;
}
f[0][0] = 1;
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j)
if (mp[i][j])
mark[i] |= (1 << j);
for (int i = 0; i < 10; ++i)
for (int j = i + 1; j < 10; ++j)
if (mp[i][j])
mark2[i] |= (1 << j);
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 1024; ++j)
for (int k = 0; k < 10; ++k)
if (~j >> k & 1)
add(f[i][j & mark[k] | mark2[k]], f[i - 1][j]);
int s = 0;
for (int i = 0; i < 1024; ++i)
add(s, f[n][i]);
cout << s << '\n';
}
} // namespace Loyalty
喜欢的话，留下你的评论吧～