首页 > 代码库 > CF 258B Little Elephant and Elections [dp+组合]

CF 258B Little Elephant and Elections [dp+组合]

给出1,2,3...m

任取7个互不相同的数a1,a2,a3,a4,a5,a6,a7

一个数的幸运度是数位上4或7的个数

比如244,470幸运度是2。

44434,7276727,4747,7474,幸运度都是4。

求出满足a1,a2,a3,a4,a5,a6,a7这样的前6个数的幸运度之和严格小于第七个数的幸运度排列共有多少种

 

1.先求出数组t

  t[i]代表1-m中幸运度为i的数的个数。

2.有了t数组后,问题变为一个排列组合问题(枚举a7幸运度,求有多少排列满足前6幸运度之和小于a7幸运度,再求和)

 

t数组怎么得到?

我们定义

d[i][j][0]为0到从第1数位开始到第i数位(包括第i数位)组成的数中幸运度为j且含自身(小于自身)的个数

d[i][j][1]为0到从第1数位开始到第i数位(包括第i数位)组成的数中幸运度为j且含自身(小于自身)的个数

例如m=14632,对i=2来说,14是自身;对i=3来说,146是自身。

 

那么

基于dp[i-1][j]转移方式如下

例如m=14632

我们处理好了前两位,到第三位6时

从0开始枚举0,1,2,3,4,5,6,7,8,9

首先所有数(0-5,6,7-9)都可以安插在dp[2][][0]后(显然是dp[3][][0]+=)

如果是小于6的数,还可以安插在dp[2][][1]后(显然是dp[3][][0]+=)

如果是等于6的数,还得有dp[3][][1]+=dp[2][][1]

第二维随情况变化

 

怎么处理如下的问题(枚举a7幸运度,求有多少排列满足前6幸运度之和小于a7幸运度,再求和)

我们可以拿dfs来解决

首先试着设计这个dfs

状态我们可以这么挂

dfs(int now_lucky_num,int max_lucky_num,int seq)

now_lucky_num:当前的幸运值和

max_lucky_num:幸运值上限(即a7幸运值)

seq:正在处理第几个数(正在处理a几来着)

我们要枚举所有的max_lucky_num从0到9

需要一个cur变量来记录当前的方案数目,一开始cur=t[i]

 

dfs中,一旦到了第七个数 或者 now_lucky_num>=max_lucky_num,就要return,第二种情况在return之前还得把cur加到最终的答案ans上

在dfs中枚举当前a[seq]的幸运度情况,i从0-9,如果t[i]不为0的话,t[i]--后进入下一个dfs,完成后把t[i]++复原

 

这样就求得了ans

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
long long f[11][11][2];
long long t[11];
long long n[11];
long long ans=0;
const long long MOD=1e9+7;
long long cur=1;
void dfs(long long now,long long limit,long long number){
    if(now>=limit) return;
    if(number==7){
            ans+=(cur%MOD);
            return;
    }
    for(long long i=0;i<=9;i++){
        if(n[i]){
            long long tmpcur=cur;
            cur*=n[i];
            cur%=MOD;
            n[i]--;
            dfs(now+i,limit,number+1);
            cur=tmpcur;
            n[i]++;
        }
    }
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("G:/in.txt","r",stdin);
        //freopen("G:/myout.txt","w",stdout);
    #endif
    long long m;
    cin>>m;
    long long tmp=m;
    for(long long i=10;i>=0 && tmp;i--){
        t[i]=tmp%10;
        tmp/=10;
    }
    f[0][0][1]=1;
    for(long long i=1;i<=10;i++){
        for(long long j=0;j<=10;j++){
            for(long long d=0;d<=9;d++){
                if(d<t[i]){
                    f[i][j+(d==4 || d==7)][0]+=f[i-1][j][0];
                    f[i][j+(d==4 || d==7)][0]+=f[i-1][j][1];
                }else if(d==t[i]){
                    f[i][j+(d==4 || d==7)][1]+=f[i-1][j][1];
                    f[i][j+(d==4 || d==7)][0]+=f[i-1][j][0];
                }else{
                    f[i][j+(d==4 || d==7)][0]+=f[i-1][j][0];
                }
            }
        }
    }
    for(long long i=0;i<=10;i++)
        n[i]=f[10][i][0]+f[10][i][1]-(i==0);
    for(long long i=0;i<=9;i++){
        cur=n[i];
        dfs(0,i,1);
    }
    cout<<ans%MOD<<endl;
    return 0;
}


 

 

CF 258B Little Elephant and Elections [dp+组合]