BZOJ 4197: [Noi2015]寿司晚宴 状态压缩 + 01背包

4197: [Noi2015]寿司晚宴

Time Limit: 10 Sec  Memory Limit: 512 MB

Description

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

在晚宴上,主办方为大家提供了 n−1 种不同的寿司，编号 1,2,3,…,n−1，其中第 i 种寿司的美味度为 i+1 （即寿司的美味度为从 2 到 n）。

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

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

Input

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

Output

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

Sample Input

3 10000

Sample Output

9

HINT

2≤n≤500

0<p≤1000000000

题解：

　　前8个质因子，状压

　　这n<=500的数都最多包含一个大于根号n的质因子

　　跑01背包

#include<bits/stdc++.h>
using namespace std;
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N=+,M=1e6+,inf=;

int p[] = {,,,,,,,};
int dp[][(<<)+][(<<)+],pd[][(<<)+][(<<)+],n,P,f[N],has[(<<)+][(<<)+];
vector<int > fi,se[N];
int main() {
    scanf("%d%d",&n,&P);
    for(int i = ; i <= n; ++i) {
        int tmp = i,now = ;
        for(int j = ; j < ; ++j)
            while(tmp%p[j] == ) now|=(<<j),tmp/=p[j];
        if(tmp == )
            f[i] = now,fi.push_back(i);
        else
            f[i] = now,se[tmp].push_back(i);
    }
    int now = ;
    dp[][][] = ;
    for(int g = ; g < fi.size(); ++g) {
        int u = fi[g];
        now ^= ;
        memset(dp[now],,sizeof(dp[now]));
        for(int i = ; i < (<<); ++i)
            for(int j = ; j < (<<); ++j) {
                if((j&f[u])==) dp[now][i|f[u]][j] += dp[now^][i][j]%P,dp[now][i|f[u]][j]%=P;
                if((i&f[u])==) dp[now][i][j|f[u]] += dp[now^][i][j]%P,dp[now][i][j|f[u]]%=P;
                dp[now][i][j] += dp[now^][i][j]%P,dp[now][i][j]%=P;
            }
    }
    for(int S = ; S <= n; ++S) {
        if(se[S].size() == ) continue;
        int tmp = now;
        for(int i = ; i < (<<); ++i)
            for(int j = ; j < (<<); ++j) has[i][j] = pd[tmp][i][j] = dp[now][i][j];

        for(int g = ; g < se[S].size(); ++g) {
            now ^= ;
            memset(dp[now],,sizeof(dp[now]));
            for(int i = ; i < (<<); ++i)
            for(int j = ; j < (<<); ++j) {
                int u = se[S][g];
                if((i&f[u])==) dp[now][i][j|f[u]] += dp[now^][i][j]%P,dp[now][i][j|f[u]]%=P;
                dp[now][i][j] += dp[now^][i][j]%P,dp[now][i][j]%=P;
            }
        }
        for(int g = ; g < se[S].size(); ++g) {
            tmp ^= ;
            memset(pd[tmp],,sizeof(pd[tmp]));
            for(int i = ; i < (<<); ++i)
            for(int j = ; j < (<<); ++j) {
                int u = se[S][g];
                if((j&f[u])==) pd[tmp][i|f[u]][j] += pd[tmp^][i][j]%P,pd[tmp][i|f[u]][j]%=P;
                pd[tmp][i][j] += pd[tmp^][i][j]%P,pd[tmp][i][j]%=P;
            }
        }
        for(int i = ; i < (<<); ++i)
            for(int j = ; j < (<<); ++j) dp[now][i][j] += ((pd[tmp][i][j] - has[i][j])%P+P)%P,dp[now][i][j] %= P;
    }
    int ans = ;
    for(int i = ; i < (<<); ++i)
        for(int j = ; j < (<<); ++j) if((i&j) == )ans += dp[now][i][j],ans %= P;
    printf("%d\n",ans);
    return ;
}