洛谷2150 [NOI2015]寿司晚宴

Luogu

重新写一遍 qwq

分析

先考虑一个 $30$ 分做法。

设 $dp_{i,j,k}$ 表示前 $i$ 个数,小 G 选的数的质因子集合为 $j$ ,小 W 选的数的质因子集合为 $k$ 的方案数。

转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。


注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子,因此我们可以只状压 $<\sqrt{500}$ 的质因子,然后再单独记录一下最大的那个质因子。

我们把 $2\sim n$ 的所有数按照最大质因子从小到大排序,这样子可以把最大质因子相同的数放在一起处理。

同样设 $dp_{i,j}$ 表示小 G 选的数的质因子集合为 $i$ ,小 W 选的数的质因子集合为 $j$ 的方案数。这里滚动掉了一维。

再设 $f_{0/1,i,j}$ 表示当前的最大质因子给了小 G / 小 W,小 G 选的数的质因子集合为 $i$ ,小 W 选的数的质因子集合为 $j$ 的方案数。这里也滚动掉了一维。

每次把 $f_{0/1}$ 的初值设为 $dp$ ,然后把最大质因子相同的数批量转移,最后再将 $f_{0/1}$ 合并到 $dp$ 里去。

具体的合并是 $dp_{i,j}=f_{0,i,j}+f_{1,i,j}-dp_{i,j}$ ,减去 $dp_{i,j}$ 的原因是多算了一次都不选的情况。

最后的答案就是所有的 $dp_{i,j}$ 之和。


具体实现上有一些细节,详见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;
const int p[8]={2,3,5,7,11,13,17,19};

int n,mod;
int dp[256][256],f[2][256][256];

struct num { int S,r; } a[N];
bool operator <(num a,num b) { return a.r<b.r; }

inline void add(int& x,int y) { x=(x+y)%mod; }

inline void init(int x,int t) {
    for (re int i=0;i<8;++i)
        while (t%p[i]==0) t/=p[i],a[x].S|=1<<i;
    a[x].r=t;
}

int main() {
    n=read(),mod=read();
    for (re int i=2;i<=n;++i) init(i,i);
    sort(a+2,a+n+1); dp[0][0]=f[0][0][0]=f[1][0][0]=1;
    for (re int k=2;k<=n;++k) {
        for (re int i=255;~i;--i)
            for (re int j=255;~j;--j) {
                if (i&j) continue;
                if (!(j&a[k].S)) add(f[0][i|a[k].S][j],f[0][i][j]);
                if (!(i&a[k].S)) add(f[1][i][j|a[k].S],f[1][i][j]);
            }
        if (a[k].r!=a[k+1].r||a[k].r==1) {
            for (re int i=0;i<256;++i)
                for (re int j=0;j<256;++j) {
                    if (i&j) continue;
                    dp[i][j]=(0ll+f[0][i][j]+f[1][i][j]-dp[i][j]+mod)%mod;
                }
            memcpy(f[0],dp,sizeof(dp)),memcpy(f[1],dp,sizeof(dp));
        }
    }
    int ans=0;
    for (re int i=0;i<256;++i)
        for (re int j=0;j<256;++j)
            if ((i&j)==0) add(ans,dp[i][j]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 53 PM

4 条评论

  1. smy

    怎么重写一遍啊

    1. M_sea
      @smy

      发现自己忘光了

  2. xgzc

    不是n * (3^8)差评

    1. M_sea
      @xgzc

      不会,告辞

发表评论