首页 > 代码库 > CodeForces 258B Little Elephant and Elections 数位DP
CodeForces 258B Little Elephant and Elections 数位DP
前面先用数位DP预处理,然后暴力计算组合方式即可。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 20;const LL MOD = 1e9 + 7;int M,lim[maxn],len;bool vis[maxn][maxn];struct EE { LL cnt[maxn]; EE() { memset(cnt,0,sizeof(cnt)); }};EE f[maxn][maxn], ans;void getlim(int num) { len = 0; memset(lim,0,sizeof(lim)); while(num) { lim[len++] = num % 10; num /= 10; }}EE dfs(int now,int cnt,int bound) { if(now == 0) { EE ret; ret.cnt[cnt] = 1; return ret; } if(!bound && vis[now][cnt]) return f[now][cnt]; int m = bound ? lim[now - 1] : 9; EE ret; for(int i = 0;i <= m;i++) { EE nret = dfs(now - 1,cnt + (i == 4 || i == 7),bound && i == m); for(int i = 0;i <= len;i++) ret.cnt[i] += nret.cnt[i]; } if(!bound) { f[now][cnt] = ret; vis[now][cnt] = true; } return ret;}LL A(LL m,LL n) { LL ret = 1; for(int i = 1;i <= n;i++) { ret *= m; m--; ret %= MOD; } return ret;}LL rest[maxn],rcnt[maxn];LL dfs1(int now,int sum,int limm) { if(sum >= limm) return 0; if(now == 7) { LL ret = 1; for(int i = 0;i < limm;i++) if(rcnt[i]) { ret = (ret * A(ans.cnt[i],rcnt[i])) % MOD; } return ret; } LL ret = 0; for(int i = 0;i < limm;i++) if(rest[i]) { rcnt[i]++; rest[i]--; ret = (ret + dfs1(now + 1,sum + i,limm)) % MOD; rcnt[i]--; rest[i]++; } return ret;}void solve() { memset(vis,0,sizeof(vis)); getlim(M); ans = dfs(len,0,1); ans.cnt[0]--; LL out = 0; for(int i = 1;i <= len;i++) if(ans.cnt[i]) { memcpy(rest,ans.cnt,sizeof(rest)); memset(rcnt,0,sizeof(rcnt)); out = (dfs1(1,0,i) * ans.cnt[i] % MOD + out) % MOD; } cout << out << endl;}int main() { cin >> M; solve(); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。