bzoj 4197 [Noi2015]壽司晚宴

​​http://www.elijahqi.win/archives/3867​​​

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

Source

考慮到質因數翻倍之後仍然<=500的質因數隻有8個

是以我們把這八個記錄下來 然後剩下的因為每次隻會出現一次單獨統計即可

考慮設dp[s1][s2]表示 在現在的所有狀态中第一個人 選了8個質因數中s1狀态 第二個人選了s2狀态 我的方案數是多少

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1<<8;
struct node{
    int x,y;
}data[550];
ll g[2][N][N],dp[N][N],mod;int n,tot;
int prime[]={2, 3, 5, 7, 11, 13, 17, 19};
inline bool cmp(const node &a,const node &b){return a.x<b.x;}
inline void inc(ll &x,ll v){x=x+v>=mod?x+v-mod:x+v;}
inline ll dec(ll x,ll v){return x-v<0?x-v+mod:x-v;}
int main(){
    freopen("3.in","r",stdin);
    scanf("%d%lld",&n,&mod);
    for (int i=2;i<=min(n,20);++i){
        bool flag=1;
        for (int j=2;j*j<=i;++j){
            if (i%j==0) {flag=0;break;}
        }if (flag)prime[tot++]=i;
    }
    for (int owo=2;owo<=n;++owo){
        int x=owo;
        for (int i=0;i<tot;++i){
            if (x%prime[i]) continue;
            data[owo].y|=1<<i;while(x%prime[i]==0) x/=prime[i];
        }data[owo].x=x;
    }sort(data+2,data+n+1,cmp);dp[0][0]=1;int S=1<<tot;S-=1;
    for (int i=2;i<=n;++i){
        if (i==2||data[i].x==1||data[i].x!=data[i-1].x){
            memcpy(g[0],dp,sizeof(dp));memcpy(g[1],dp,sizeof(dp));
        }
        for (int s1=S;~s1;--s1){int ss=S^s1;
            for (int s2=ss;s2;s2=(s2-1)&ss){
                if (!(data[i].y&s2)) inc(g[0][s1|data[i].y][s2],g[0][s1][s2]);
                if (!(data[i].y&s1)) inc(g[1][s1][s2|data[i].y],g[1][s1][s2]);
            }inc(g[0][s1|data[i].y][0],g[0][s1][0]);
            if (!(data[i].y&s1)) inc(g[1][s1][data[i].y],g[1][s1][0]);
        }
        if (i==n||data[i].x!=data[i+1].x||data[i].x==1){
            for (int s1=S;~s1;--s1){int ss=S^s1;
                for (int s2=ss;s2;s2=(s2-1)&ss){
                    dp[s1][s2]=(g[0][s1][s2]+dec(g[1][s1][s2],dp[s1][s2]))%mod;
                }dp[s1][0]=(g[0][s1][0]+dec(g[1][s1][0],dp[s1][0]))%mod;
            }
        }
    }ll ans=0;
    for (int s1=S;~s1;--s1){int ss=S^s1;
        for (int s2=ss;s2;s2=(s2-1)&ss){
            inc(ans,dp[s1][s2]);
        }inc(ans,dp[s1][0]);
    }printf("%lld\n",ans);
    return 0;
}