BZOJ 2734: [HNOI 2012]集合选数

这题开始想了一个很nc的动归思路。。最后发现是错的= =
这题利用它的特性可以建立好几个类似杨辉三角(好像也没什么关系 = =) 的三角形数字阵
对于一个不能被任意一个数约束的数x 可以得到下面数字阵:
x
2x 3x
4x 6x 9x
….
对于第i +1行的数
系数分别为2^ (i) * 3 ^ 0,2 ^ (i – 1) * 3 ^ 1 …,2 ^ 0 * 3 ^ (i)
且对于第i+1行第j个数 如果它可以取 仅当第i行第j个和第j+1个数都没取
状压之~
最后把每个数字阵的ans乘起来就是最后的ans
———————————————————–

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int inf = 1000000001;
int f[20][1 << 13], b[maxn], n, num[20];
ll tans, ans;
void dfs(int n, int t, int now, int k)
{
    if (now == num[n])
    {
        tans = (tans + f[n][k]) % inf;
        return;
    }
    dfs(n, t, now + 1, k << 1);
    if (!((t & (1 << (num[n + 1] – now – 1))) || (t & (1 << (num[n + 1] – now – 2)))))
            dfs(n, t, now + 1, (k << 1) + 1);
        }
        void deal(int now)
{
    b[now] = 1;
    memset(num, 0, sizeof(num));
    num[0] = 1;
    for (int i = 1; i <= 20; i++)
    {
        int k = 1 << i;
        for (int j = 0; j <= i && (ll)k * now <= n; j++, k = (k >> 1) * 3)
        {
            ++num[i];
            b[k * now] = 1;
        }
    }
    f[0][0] = f[0][1] = 1;
    int k = 0;
    for (int i = 1; i <= 20 && num[i]; i++)
    {
        for (int j = 0; j < (1 << num[i]); j++)
        {
            tans = 0;
            dfs(i – 1, j, 0, 0);
            f[i][j] = tans;
        }
        if (!num[i + 1])
        {
            k = i;
        }
    }
    tans = 0;
    dfs(k, 0, 0, 0);
    ans = (ans * tans) % inf;
}
int main()
{
    freopen(“input.in”,”r”,stdin);
    freopen(“output.out”,”w”,stdout);
    scanf(“%d”, &n);
    ans = 1;
    for (int i = 1; i <= n; i++)
        if (!b[i]) deal(i);
    printf(“%lld”, ans);
    fclose(stdin);
    fclose(stdout);
}

发表评论