欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

#NOIP模拟赛#Cool子集(Dp + 状压)

程序员文章站 2022-07-01 11:26:04
...

#NOIP模拟赛#Cool子集(Dp + 状压)

#NOIP模拟赛#Cool子集(Dp + 状压)

#NOIP模拟赛#Cool子集(Dp + 状压)


用一个int S的二进制来表示当前这一个集合中包含哪些数字(0~9)
定义Bit[S]表示当前状态S中有多少个数字(即二进制中有多少个1)
定义Dp[S]表示当这个集合中只有一个整数, 这个整数不超过N,且包含数字的状态为S时,这个集合最多可能有多少种方案。
对于Dp[S]的处理:
当Bit[S] > N的位数:Dp[S] = 0;
当Bit[S] < N的位数:Dp[S] = Fac[Bit[S]];(Fac:阶乘)
当S中有数字‘0’时,Dp[S] = Fac[Bit[S]] - Fac[Bit[S] - 1](此时减去令最高位为0时可能的方案数)
当Bit[S] == N的位数:计算出小于等于N的全排列数


定义f[i][j][S]表示一个集合中包含i个数字,它们组成j个整数,数字包含状态为S时的方案数
f[i][j][S] = Σf[k][j - 1][TS] * Dp[S ^ TS](TS是S的子状态) 2 <= j <= i
f[i][1][S] = Dp[S];


最后答案是Σf[i][j][S] (1 <= j <= i <= 10,0 <= S <= (1 << 10) - 1)


Code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int Maxn = 10;
const int Maxs = 1 << 10;
const int MOD = 1e9 + 7;

int N, cnt, SALL;
int num[Maxn + 5], Bit[Maxs + 5], Dp[Maxs + 5];
int Fac[Maxn + 5], Inv[Maxn + 5];
int f[Maxn + 5][Maxn + 5][Maxs + 5];

bool getint(int & num){
    char c; int flg = 1;    num = 0;
    while((c = getchar()) < '0' || c > '9'){
        if(c == '-')    flg = -1;
        if(c == -1) return 0;
    }
    while(c >= '0' && c <= '9'){
        num = num * 10 + c - 48;
        if((c = getchar()) == -1)   return 0;
    }
    num *= flg;
    return 1;
}

void Pre(){
    Fac[0] = Fac[1] = Inv[0] = Inv[1] = 1;
    for(int i = 2; i <= 10; ++ i)    Fac[i] = 1ll*Fac[i - 1]*i%MOD, Inv[i] = 1ll*(MOD-MOD/i)*Inv[MOD%i]%MOD;
    for(int i = 2; i <= 10; ++ i)    Inv[i] = 1ll*Inv[i]*Inv[i-1]%MOD;
}

int main(){
    //freopen("data3.in", "r", stdin);
    freopen("cool.in", "r", stdin);
    freopen("cool.out", "w", stdout);
    getint(N);
    Pre();
    int t = N;
    while(t){
        num[++ cnt] = t % 10;
        t /= 10;
    }
    SALL = 1 << 10;
    for(int S = 0; S < SALL; ++ S){
        Bit[S] = Bit[S >> 1] + (S & 1);
        if(Bit[S] > cnt)    Dp[S] = 0;
        else if(Bit[S] < cnt){
            Dp[S] = Fac[Bit[S]];
            if(S & 1)   Dp[S] -= Fac[Bit[S] - 1];
        }
        else {
            Dp[S] = 0;
            int TS = S;
            bool flg = 1;
            for(int i = cnt; i >= 1; -- i){
                for(int j = (i == cnt); j < num[i]; ++ j)   if(TS & (1 << j))
                    Dp[S] += Fac[Bit[TS] - 1];
                if(! (TS & (1 << num[i]))){
                    flg = 0;
                    break;
                }
                else TS -= 1 << num[i];
            }
            Dp[S] += flg;
        }
    }
    f[0][0][0] = 1;
    for(int i = 1; i <= 10; ++ i)
        for(int j = 1; j <= i; ++ j)
            for(int S = 1; S < SALL; ++ S)  if(Bit[S] == i){
                if(j == 1)  f[i][j][S] = Dp[S];
                else{
                    for(int k = 1; k < i; ++ k)
                        for(int TS = S & (S - 1); TS; TS = (TS - 1) & S)    if(Bit[TS] == k)
                            f[i][j][S] = (f[i][j][S] + 1ll * f[k][j - 1][TS] * Dp[S ^ TS]) % MOD;
                }
            }
    int Ans = 0;
    for(int i = 1; i <= 10; ++ i)
        for(int j = 1; j <= i; ++ j)
            for(int S = 0; S < SALL; ++ S)
                Ans = (Ans + 1ll * f[i][j][S] * Inv[j]) % MOD;
    printf("%d\n", Ans);
    return 0;
}