HDU多校第六场 1011 11 Dimensions —— DP +思维

本文主要是介绍HDU多校第六场 1011 11 Dimensions —— DP +思维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    长度为 $n$ 的数，部分位置是 $？$，$？$可以是 $0$ ~ $9$
    要求这个数整除 $m$，$q$ 次询问
    每次询问第 $k$ 小的解

解题思路：

    对于 $23??56??$
    将其拆为 $23005600$ $+$ $??00??$
    然后考虑 $？$ 的方案，$cnt$ 个问号的方案数为 $10^{cnt}$
    因为 $k\le 10^{18}$，如果 $10^{cnt}$ 内的数均匀分布，整除 $m$ 的个数大约为 $\frac{10^{cnt}}{m}$
    因此 $cnt=20$ 即可，也就是探讨后 $20$ 个问号的方案，前面的问号都取为 $0$

---

    $dp[i][j]$ 为到第 $i$ 个问号，模 $m$ 为 $j$ 的方案数
    $dp[i][j]=\sum dp[i-1][j+10^i\times x]$   $x\in [0,9]$
    注意 $i=1$ 的时候，要将初始的影响加上去，也就是 $23005600$
    可以理解为用第一位去解决初始的影响，用高位的话不是最贪心的
    查询的时候从高位到低位枚举，也要考虑到第一位时初始的影响
    时间复杂度：$O(20\ast m\ast 10+q\ast 20\ast 10)$

核心：DP + 思维

#include<bits/stdc++.h>
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 5;
const ll mod = 1e9 + 7;
int T, n, m, q;
char s[maxn];
ll dp[30][30], fac1[50], fac2[50];int main() {scanf("%d", &T);while(T--) {scanf("%d%d%d%s", &n, &m, &q, s);ll p1 = 1, p2 = 1, val = 0, rem = 0, cnt = 0, k;for(int i=n-1; ~i; i--) {if(isdigit(s[i])) {val = (val + (s[i]-'0') * p1 % mod) % mod;rem = (rem + (s[i]-'0') * p2 % m) % m;} else if(cnt < 20) {fac1[++cnt] = p1;fac2[cnt] = p2;}p1 = p1 * 10 % mod;p2 = p2 * 10 % m;}memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int i=1; i<=cnt; i++)for(int j=0; j<m; j++)for(int x=0; x<10; x++) {if(i > 1) dp[i][j] += dp[i-1][(j + fac2[i] * x % m) % m];else dp[i][j] += dp[i-1][(j + rem + fac2[i] * x % m) % m];if(dp[i][j] >= 1e18 + 10 || dp[i][j] < 0) dp[i][j] = 1e18 + 10;}while(q--) {scanf("%lld", &k);if(dp[cnt][0] < k) {puts("-1");continue;}ll ans = val, pre_rem = 0, now_rem;for(int i=cnt; i; i--)for(int x=0; x<10; x++) {if(i > 1) now_rem = (pre_rem + fac2[i] * x % m) % m;else now_rem = (pre_rem + rem + fac2[i] * x % m) % m;if(dp[i-1][now_rem] < k) k -= dp[i-1][now_rem];else {pre_rem = now_rem;ans = (ans + fac1[i] * x % mod) % mod;break;}}printf("%lld\n", ans);}}
}

这篇关于HDU多校第六场 1011 11 Dimensions —— DP +思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---