【题解】NOI2015寿司晚宴

　　想好久啊+不敢写啊……但果然人还是应当勇敢自信，只有坚定地去尝试，才会知道最后的结果。1A真的太开心啦，不过好像我的做法还是比较复杂的样子……理解起来应该算是比较容易好懂的类型，大家可以参考一下思路~

　　首先我们先考虑一下简单的30分算法：30以内的质数只有十个左右，可以利用状压表示出两个人所选择的集合，再通过寿司转移即可。之后的大数据呢？我们发现不能这样做是因为之后的质数越来越多，状压的空间就开不下了。

　　这时要注意到一个性质：对于1~n内的每一个数而言，都可以分解成若干个<sqrt(n)的质数之积 || 在此基础之上再乘上一个 > sqrt(n)的质数。这说明什么？对于所有的>sqrt(n)的质数而言，我们选择一个寿司只可能选择其中的一个——换句话说，就是不同的大质数之间的决策是相互独立的。

　　于是就有了如下算法：既然不同的大质数之间不会互相影响，我们就一个一个大质数来统计，之后再累加到一起即可。于是我们增加一维的状态，单独表示这一个大质数。0表示两个集合中均不含有这个大质数因子，1表示第一个人所选择的集合中含这个因子，2表示第二个人选择的集合中含有这个因子。不同的因子之间的转移将所有1&2的状态都加入0并清空1&2即可（对于新的质数来说，之前没有作出过相应的决策，所以是不含有该因子的）。

　　网上代码很短，然而我莫名长……

#include <bits/stdc++.h>

using namespace std;

#define maxn 1000

#define maxt 260

#define int long long

int n, mod, S[maxn], CNST = ( << ) - ;

int cnt, dp[][maxt][maxt], num[maxn], mark[maxn];

int tot, P[maxn], cnp = , ans;

int pri[maxn] = {, , , , , , , , };

map <int, int> Map;

int read()

{

    int x = ;

    char c;

    c = getchar();

    while(c < '' || c > '') c = getchar();

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x;

}

int up(int &x, int y)

{

    x += y;

    if(x >= mod) x -= mod;

}

void work(int i)

{

    for(int x = CNST; ~x; x --)

        for(int y = CNST; ~y; y --)

        {

            if(x & y) continue;

            int a = dp[][x][y], b = dp[][x][y];

            up(dp[][x | num[i]][y], dp[][x][y]);

            up(dp[][x][y | num[i]], dp[][x][y]);

            up(dp[][x | num[i]][y], a);

            up(dp[][x][y | num[i]], b);

        }

}

void DP(int k)

{

    for(int x = ; x <= CNST; x ++)

        for(int y = ; y <= CNST; y ++)

            if(x & y) continue;

            else

            {

                up(dp[][x][y], dp[][x][y]);

                up(dp[][x][y], dp[][x][y]);

                dp[][x][y] = dp[][x][y] = ;

            }

    if(k) for(int i = k; i <= n + ; i += k) work(i);

    else

    {

        for(int i = ; i <= cnt; i ++)

            for(int x = CNST; ~x; x --)

                for(int y = CNST; ~y; y --)

                {

                    if(x & y) continue;

                    int k = S[i];

                    int a = dp[][x][y];

                    up(dp[][x | num[k]][y], a);

                    up(dp[][x][y | num[k]], a);

                }

    }

}

signed main()

{

    n = read() - , mod = read();

    dp[][][] = ;

    for(int i = ; i <= n + ; i ++)

    {

        int k = i;

        for(int j = ; j <= cnp; j ++)

        {

            if(!(k % pri[j])) num[i] |= ( << (j - ));

            while(!(k % pri[j])) k /= pri[j];

        }

        if(k !=  && k != )

        {

            mark[i - ] = k;

            if(!Map[k]) Map[k] = , P[++ tot] = k;

        }

        else S[++ cnt] = i;

    }

    for(int i = ; i <= tot; i ++)

        DP(P[i]);

    for(int i = ; i <= CNST; i ++)

        for(int j = ; j <= CNST; j ++)

            if(i & j) continue;

            else

            {

                up(ans, dp[][i][j]);

                up(ans, dp[][i][j]);

                up(ans, dp[][i][j]);

            }

    printf("%lld\n", ans);

    return ;

}

巴特西

【题解】NOI2015寿司晚宴

最新文章

热门文章