CF258B

ゞ浴缸里的玫瑰 2024-04-20 10:25 76阅读 0赞

##  ##

CF258B

### 题意： ###

> 7个人在 $ \[1,m\] $ 区间内取数，求第一个人选的数的4和7的个数大于其他人的4和7个数总和的方案数。

### 解法： ###

> 要求输入的 $ m $ 可以很大，而且需要按位考虑每隔人的贡献，所以考虑数位DP。  
> 设 $ f\[i\]\[j\] $ 表示到第 $ i $ 位，有 $ j $ 个数是 $ 4 和 7 $ 的方案数，再利用dfs进行转移就行。

### CODE : ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long const LL MOD = 1e9+7; LL final,dp[16][16],c[16]; int bit[16],l,cnt,tot,m; int work(int m, int n) { cnt = tot = l = 0; for (; m; m /= 10) bit[++l] = m % 10; for (int i = l; i && tot <= n; --i) { for(int j = 0 ; j < bit[i] ; j++) if (j == 4 || j == 7) { if (tot < n) cnt += dp[i - 1][n - tot - 1]; } else cnt += dp[i - 1][n - tot]; if (bit[i] == 4 || bit[i] == 7) ++tot; } if(tot == n) ++cnt; if(n == 0) --cnt; return cnt; } void dfs(int t, int now, int lim, LL ans) { if (t == 6) (final += ans) %= MOD; else { for (int i = 0; i <= 9 && i + now < lim; ++i) if (c[i]) { c[i]--; dfs(t + 1, now + i, lim, ans * (c[i] + 1) % MOD); c[i]++; } } } int main() { scanf("%d", &m); dp[0][0] = 1; for(int i = 0 ; i <= 9 ; i++) { for(int j = 0 ; j <= i ; j++) { dp[i + 1][j + 1] += dp[i][j] * 2; dp[i + 1][j] += dp[i][j] * 8; } } for(int i = 0 ; i <= 9 ; i++) c[i] = work(m, i); for(int i = 0 ; i <= 9 ; i++) { if (c[i]) { --c[i]; dfs(0, 0, i, (c[i] + 1) % MOD); ++c[i]; } } printf("%lld \n", final); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11373454.html

发表评论取消回复

表情：

评论列表（有 0 条评论，76人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1217B

CF1217B 题意： > 有一个有 $ x $ 个头的龙，你有 $ n $ 种方案，每种方案中包含你可以砍掉的头 $ d\_i $ 和龙会生长的头 $ h...

悠悠/ 2024年04月20日 10:34/ 0 赞/ 84 阅读

相关 CF1214B

CF1214B 解法： > 暴力枚举，时间复杂度 $ O(n) $ CODE: include<iostream> include<cstd...

不念不忘少年蓝@/ 2024年04月20日 10:33/ 0 赞/ 99 阅读

相关 CF1200B

CF1200B 解法： > 贪心。当在第i列时，尽可能多的取走第i列的木块使得袋子里的木块尽可能多 CODE: include<iostre...

本是古典何须时尚/ 2024年04月20日 10:29/ 0 赞/ 87 阅读

相关 CF1197B

CF1197B 题意： > 出n个柱子，每个柱子一个圆盘，其半径各不相同，每次只能将柱子上只有一个圆盘的移到相邻位置，问能否全部移到一个柱子上。解法：...

落日映苍穹つ/ 2024年04月20日 10:28/ 0 赞/ 100 阅读

相关 CF1207B

CF1207B-Square Filling 题意： > 两个矩阵a,b，已知矩阵b，每次能修改b矩阵中相邻的四个格（b为空矩阵），使b变为a 解法： ...

梦里梦外;/ 2024年04月20日 10:28/ 0 赞/ 87 阅读

相关 CF1195B

CF1195B 题意： > 有一个盒子，每次可以做两个操作： > > > 1.每次吃掉一块蛋糕 > > 2.每次放入比上一次放入数多1的蛋糕 > ...

墨蓝/ 2024年04月20日 10:28/ 0 赞/ 90 阅读

相关 CF1208B

CF1208B 题意： > 给出n个数字，找出最小的一端连续区间进行删除操作，使其剩余元素不含重复元素，求要删除的最小区间长度解法： > 删除子段...

「爱情、让人受尽委屈。」/ 2024年04月20日 10:28/ 0 赞/ 80 阅读

相关 CF1204B

CF1204B-Mislove Has Lost an Array 题意： > 给你n，l，r 表示在区间1-n内至少有l个不相同的数至多有r个不相同的数，...

女爷i/ 2024年04月20日 10:26/ 0 赞/ 83 阅读

相关 CF258B

CF258B 题意： > 7个人在 $ \[1,m\] $ 区间内取数，求第一个人选的数的4和7的个数大于其他人的4和7个数总和的方案数。解法： ...

ゞ浴缸里的玫瑰/ 2024年04月20日 10:25/ 0 赞/ 77 阅读

相关【反悔贪心】CF1278B CF11B

[Problem - 1278B - Codeforces][] 题意： ![c0fbd2f3d4224469b8dd5bb7d049f4ee.png][] 思路： !

以你之姓@/ 2024年03月24日 18:30/ 0 赞/ 91 阅读