AC. 梦想

frank_c1

[NOI 2015] 寿司晚宴

发布于2016年05月24日 | 暂无评论 | 985阅读 | 动态规划,状态压缩

题目描述

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

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

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

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

输入格式

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

输出格式

输出一行包含1个整数,表示所求的方案模p的结果。

题目解析

转化一下题意,就是求小G和小W分别选择一个整数集合,使得不同集合间任意两数均互质的方案数。

考虑整数的质因数分解,两个整数互质当且仅当两者没有相同的质因子。如果我们将整数集合S内所有整数所含的质因子表示为一个新集合S',集合T内所有整数所含的质因子表示为一个新集合T'。可以知道若集合S,T满足题意,当且仅当S',T'没有交集。

我们发现,对于任何小于n的正整数,至多有一个\ge \sqrt{n}的质因子。如果有一个人选择了包含质因子p的整数,那么另一个人不能选取任何包含质因子p的整数。这启发我们将所有存在大质因子整数以它们的大质因子分类。同一类的整数只能被一个人选择。

因为\le n的质因子只有8个,所以在没有大质因子的情况下,我们可以把一个人选择的质因子集合表示为一个2 ^ 8的二进制数S。设选择到第i个整数时小G选择的集合为S,小W选择的集合为T的方案数为f(i,S,T)。则有

f(i,S|P(i),T) += f(i - 1,S,T) \\ f(i,S,T|P(i)) += f(i-1,S,T)

其中P(i)是整数i的质因子集合。上述方程显然是可以用滚动背包优化一维空间的。

考虑有大质因子的情况。假设我们现在考虑到质因子p,另设g(0,i,S,T)为大质因子分给小G,考虑到第i个整数时小G此时质因子集合为S,小W质因子集合为T的方案数,同理g(1,i,S,T)为大质因子分给小W的方案数。则有

g(0,i,S|P(i),T) += g(0,i-1,S,T) \\ g(1,i,S,T|P(i)) += g(1,i-1,S,T)

P(i)意义如上所述。同理,这个方程也可以优化掉一位空间。在开始一类数的DP时,我们先令

g(0,S,T) = f(S,T) \\ g(1,S,T) = f(S,T)

在DP完成后,再令

f(S,T) = g(0,S,T) + g(1,S,T) - f(S,T)

因为两个人均不选这类数的情况在g(0,S,T)g(1,S,T)中均出现了。

总时间复杂度O(n 2 ^ {16})