题解 - [Luogu P2150] [NOI2015] 寿司晚宴

发表于 更新于 分类于 ， 本文字数： 1.1k 阅读时长 ≈ 4 分钟

题目链接

原始题面

题目描述

为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴

在晚宴上，主办方为大家提供了 \(n−1\) 种不同的寿司，编号 \(1,2,3,\ldots,n-1\), 其中第 \(i\) 种寿司的美味度为 \(i+1\). (即寿司的美味度为从 \(2\) 到 \(n\))

现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 \(x\) 的寿司，小 W 品尝的寿司中存在一种美味度为 \(y\) 的寿司，而 \(x\) 与 \(y\) 不互质

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案 (对给定的正整数 \(p\) 取模). 注意一个人可以不吃任何寿司

输入格式

输入文件的第 \(1\) 行包含 \(2\) 个正整数 \(n, p\) 中间用单个空格隔开，表示共有 \(n\) 种寿司，最终和谐的方案数要对 \(p\) 取模

输出格式

输出一行包含 \(1\) 个整数，表示所求的方案模 \(p\) 的结果

样例 #1

样例输入 #1

1
3 10000

样例输出 #1

1
9

样例 #2

样例输入 #2

1
4 10000

样例输出 #2

1
21

样例 #3

样例输入 #3

1
100 100000000

样例输出 #3

1
3107203

提示

【数据范围】

测试点编号 n 的规模 约定
1 2 ≤ n ≤ 30
 0 < p ≤ 1,000,000,000
2
3
4 2 ≤ n ≤ 100
5
6 2 ≤ n ≤ 200
7
8 2 ≤ n ≤ 500
9
10

解题思路

显然方案合法的充要条件是二人选的质因数集合交集为空

当 \(n\leq 30\) 时，状压 DP 的做法不难得出:

设

  • 第 \(i\) 个数为 \(a_i\), 对应的质因数集合为 \(p_i\)
  • \(P=\bigcup_{i=1}^n p_i\)
  • \(f_i(S_1,S_2)\) 为在只考虑前 \(i\) 个数的前提下，两人取的质因数集合分别为 \(S_1\), \(S_2\) 时的情况数

则转移方式如下:

  • \[ f_i(S_1\cup p_i,S_2)\leftarrow f_i(S_1\cup p_i,S_2)+f_{i-1}(S_1,S_2)~(p_i\cap S_2=\varnothing) \]
  • \[ f_i(S_1,S_2\cup p_i)\leftarrow f_i(S_1,S_2\cup p_i)+f_{i-1}(S_1,S_2)~(p_i\cap S_1=\varnothing) \]

答案为

\[ \sum_{S_1,S_2\in P; S_1\cap S_2=\varnothing}f_n(S_1,S_2) \]

这个 \(f\) 可以滚动数组优化，时间复杂度为 \(O(n4^{\pi(n)})\)

对于本题的数据范围来说，\(\pi(500)=95\), 显然不能直接状压

但是我们不难发现：任意不超过 \(n\) 的数只能有至多一个大于 \(\sqrt{n}\) 的质因子

所以我们可以这样优化:

设

  • 第 \(i\) 个数为 \(a_i\), 对应的不超过 \(\sqrt{n}\) 的质因数集合为 \(p_i\), 对应的超过 \(\sqrt{n}\) 的大质数为 \(b_i\)
  • \(P=\bigcup_{i=1}^n p_i\)
  • \(f_i(S_1,S_2)\) 为在只考虑前 \(i\) 个数的前提下，两人取的质因数集合分别为 \(S_1\), \(S_2\) 时的情况数
  • \(g_i(S_1,S_2)\) 为在只考虑前 \(i\) 个数的前提下，两人取的质因数集合分别为 \(S_1\), \(S_2\) 且第二个人没选 \(b_i\) 时的情况数
  • \(h_i(S_1,S_2)\) 为在只考虑前 \(i\) 个数的前提下，两人取的质因数集合分别为 \(S_1\), \(S_2\) 且第一个人没选 \(b_i\) 时的情况数

先将 \(a\) 按 \(b\) 升序排序

则转移方式如下:

  • \[ g_i(S_1\cup p_i,S_2)\leftarrow g_i(S_1\cup p_i,S_2)+g_{i-1}(S_1,S_2)~(p_i\cap S_2=\varnothing) \]
  • \[ h_i(S_1,S_2\cup p_i)\leftarrow h_i(S_1,S_2\cup p_i)+h_{i-1}(S_1,S_2)~(p_i\cap S_1=\varnothing) \]

在 \(b_i\) 变动或到最后一个数时做如下转移

  • \[ f_i(S_1,S_2)\leftarrow g_i(S_1,S_2)+h_i(S_1,S_2)-f_i(S_1,S_2)~(S_1\cap S_2=\varnothing) \]
  • \[ g_i(S_1S_2)\leftarrow g_i(S_1,S_2)+f_i(S_1,S_2) \]
  • \[ h_i(S_1,S_2)\leftarrow h_i(S_1,S_2)+f_i(S_1,S_2) \]

答案为

\[ \sum_{S_1,S_2\in P; S_1\cap S_2=\varnothing}f_n(S_1,S_2) \]

复杂度

\(O(n4^{\pi(\sqrt{n})})\)

代码参考

Show code

Luogu_P2150view raw
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
using i64 = int64_t;
#define for_(i, l, r, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
#define rfor_(i, r, l, vars...)                                           \
  for (std::make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vars; \
       i >= i##end;                                                       \
       --i)
#define all_(a) (a).begin(), (a).end()
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
#define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>>
namespace tuple_detail_ {
template <std::size_t Begin, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) {
  return std::make_tuple(
    std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...);
}
}  // namespace tuple_detail_
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(Tuple &&t) {
  static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) &&
                  Begin + Len <= TPL_SIZE_(Tuple),
                "Out of range");
  return tuple_detail_::subtuple_impl_<Begin>(t,
                                              std::make_index_sequence<Len>());
}
template <std::size_t Pos, class Tp, class Tuple>
constexpr auto tuple_push(Tp &&v, Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        std::make_tuple(v),
                        subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t));
}
template <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_pop(Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t));
}
template <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) {
  return tuple_detail_::apply2_impl_(
    f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>());
}
#define OO_PTEQ_(op)                                                          \
  template <class Tp, class Up>                                               \
  constexpr auto operator op(std::pair<Tp, Up> lhs,                           \
                             const std::pair<Tp, Up> &rhs) {                  \
    return {lhs.first op rhs.first, lhs.second op rhs.second};                \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op(std::tuple<Ts...> const &lhs,                    \
                             std::tuple<Ts...> const &rhs) {                  \
    return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs);       \
  }                                                                           \
  template <class Tp, class Up>                                               \
  constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs,         \
                                              const std::pair<Tp, Up> &rhs) { \
    lhs.first op## = rhs.first;                                               \
    lhs.second op## = rhs.second;                                             \
    return lhs;                                                               \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op##=(std::tuple<Ts...> &lhs,                       \
                                const std::tuple<Ts...> &rhs) {               \
    return lhs = lhs op rhs;                                                  \
  }
OO_PTEQ_(+)
OO_PTEQ_(-)
OO_PTEQ_(*)
OO_PTEQ_(/)
OO_PTEQ_(%)
OO_PTEQ_(&)
OO_PTEQ_(|)
OO_PTEQ_(^)
OO_PTEQ_(<<)
OO_PTEQ_(>>)
#undef OO_PTEQ_
#undef TPL_SIZE_
template <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  return os << p.first << ' ' << p.second;
}
template <typename... Ts>
std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) {
  std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p);
  return is;
}
template <typename... Ts>
std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) {
  std::apply(
    [&](Ts const &...targs) {
      std::size_t n{0};
      ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...);
    },
    p);
  return os;
}
template <class Ch,
          class Tr,
          class Ct,
          std::enable_if_t<std::is_same_v<decltype(std::declval<Ct>().begin()),
                                          typename Ct::iterator> &&
                           std::is_same_v<decltype(std::declval<Ct>().end()),
                                          typename Ct::iterator>> * = nullptr>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Ct &x) {
  if (x.begin() == x.end()) return os;
  for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  return os;
}
using namespace std;
const int prime[] = {2, 3, 5, 7, 11, 13, 17, 19};
const int SP = sizeof(prime) / sizeof(prime[0]);
const int S = 1 << SP;
struct Node {
  i64 state, p;
  Node(): state(0), p(0) {}
  void reset(i64 x) {
    state = p = 0;
    for_(i, 0, SP - 1)
      if (x % prime[i] == 0) {
        state |= (1 << i);
        while (x % prime[i] == 0) x /= prime[i];
      }
    if (x > 1) p = x;
  }
  friend bool operator<(Node const &lhs, Node const &rhs) {
    return lhs.p == rhs.p ? lhs.state < rhs.state : lhs.p < rhs.p;
  }
};
i64 f[S][S], f1[S][S], f2[S][S];
auto solve([[maybe_unused]] int t_ = 0) -> void {
  i64 n, p;
  cin >> n >> p;
  f[0][0] = 1;
  vc<Node> a(n - 1);
  for_(i, 0, n - 2) a[i].reset(i + 2);
  sort(all_(a));
  i64 cnt = 0;
  for (auto &&[state, bigp] : a) {
    if (!bigp || !cnt || bigp != a[cnt - 1].p) {
      memcpy(f1, f, sizeof(f1));
      memcpy(f2, f, sizeof(f2));
    }
    rfor_(i, S - 1, 0)
      rfor_(j, S - 1, 0) {
        if (i & j) continue;
        if (!(j & state)) (f1[state | i][j] += f1[i][j]) %= p;
        if (!(i & state)) (f2[i][state | j] += f2[i][j]) %= p;
      }
    if (!bigp || cnt == n - 2 || bigp != a[cnt + 1].p)
      for_(i, 0, S - 1)
        for_(j, 0, S - 1) {
          if (i & j) continue;
          f[i][j] = (f1[i][j] + f2[i][j] + p - f[i][j]) % p;
        }
    ++cnt;
  }
  i64 ans = 0;
  for_(i, 0, S - 1)
    for_(j, 0, S - 1) {
      if (i & j) continue;
      ans += f[i][j];
    }
  cout << ans % p;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}