首页 > 代码库 > 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+组合]