A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4197: [Noi2015]寿司晚宴 状压dp
发表于: | 分类: Oi | 评论:0 | 阅读:46

这题我居然自己做出来了……

主要是我以前做过这么一个问题

给定$n$个数,规定一组数的价值为这组数的最小公倍数,现在求所有组合的价值的和。这样的组合一共有$2^n−1$种,$n\le 500$,$val\le 200$

然后这题是用了这么一个性质就是对于任意一个$\le 200$的数字,$>13$的质因子至多只有一个,然后直接用$f(i,j,k,l,m,n)$表示$2$用了$i$个,$3$用了$j$个,…,$13$用了$n$个的方案数.看上去我们只需要把每个数字质因数分解,然后每一维都取一下最大值方案直接加一下就行了,对于大于$13$的质因子,我们可以直接加上这个质因子倍数的方案数。然后对于多出来的一个$>13$的质因子就大力再开一维就行了

然后我还做过一个问怎么取数字让两个东西的质因子不重叠,正解是把所有的质因子状压一下

然后这题就变成上面两个题的总和了……

$f(temp1,temp2)$表示质因子的选取情况为第一个人$temp1$第二个人$temp2$的方案数,注意状态合法当且仅当temp1&temp2=0

对于$>19$的质因子直接和第一题一样把他们都放在一起,然后再开一维就行了

T1是TC的某题,T2是BZ的某题

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000+5;
int mod, n;
int F[260][260], G[260][260], H[260][260];

struct data {
    int x, y;
    bool operator < (const data &z) const {
        return y < z.y;
    }
}a[N];

int prime[] = {2,3,5,7,11,13,17,19};

int main() {
    cin >> n >> mod;
    int Max = (1<<8)-1;
    for(int i=2;i<=n;++i) {
        int x = i;
        for(int j=0;j<8;++j)
            while(x % prime[j] == 0) a[i].x |= (1<<j), x /= prime[j];
        a[i].y = x;
    }
    sort(a+2,a+n+1);
    F[0][0] = 1;
    int i;
    register int temp1,temp2;

    for(i=2;a[i].y==1;++i) {
        int x = a[i].x;
        memcpy(G, F, sizeof F);
        for(temp1=0;temp1<=Max;++temp1) {
            for(temp2=0;temp2<=Max;++temp2) if(!(temp1&temp2)){
                if(!(temp2&x)) (G[temp1|x][temp2] += F[temp1][temp2]) %= mod;
                if(!(temp1&x)) (G[temp1][temp2|x] += F[temp1][temp2]) %= mod;
            }
        }
        memcpy(F, G, sizeof F);
    }

    for(int p=i;a[i].y;) {
        memcpy(G, F, sizeof F);
        memcpy(H, F, sizeof F);
        while(a[p].y == a[i].y) ++p;
        for(;i<p;++i) {
            int x = a[i].x;
            for(temp1=Max;~temp1;--temp1) {
                for(temp2=Max;~temp2;--temp2) {
                    if(!(temp1&temp2)) {
                        if(!(temp2&x)) (G[temp1|x][temp2] += G[temp1][temp2]) %= mod;
                    }
                }
            }
            for(temp1=Max;~temp1;--temp1) {
                for(temp2=Max;~temp2;--temp2) {
                    if(!(temp1&temp2)) 
                        if(!(temp1&x)) (H[temp1][temp2|x] += H[temp1][temp2]) %= mod;
                }
            }
        }
        for(temp1=0;temp1<=Max;++temp1) {
            for(temp2=0;temp2<=Max;++temp2) {
                if(!(temp1&temp2)) {
                    F[temp1][temp2] = - F[temp1][temp2];
                    (F[temp1][temp2] += G[temp1][temp2]) %= mod;
                    (F[temp1][temp2] += H[temp1][temp2]) %= mod;
                    (F[temp1][temp2] += mod) %= mod; 
                }
            }
        }
    }
    int ans = 0;
    for(temp1=0;temp1<=Max;++temp1)
        for(temp2=0;temp2<=Max;++temp2) {
            (ans += F[temp1][temp2]) %= mod;
        }
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP