2019 Multi-University Training Contest 6 11 Dimensions DP 求第k大m的倍数

本文主要是介绍2019 Multi-University Training Contest 6 11 Dimensions DP 求第k大m的倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一个不完整的数，知道它有n位，是m的倍数，总共q个询问，每次问你它第k大是多少。

题解：

dp[i][j]表示到第i位的时候，模m为j时的个数。
我们用res表示当前枚举到的数模m是多少，然后枚举前面模m的余数，
那么状态转移方程就是
$dp[i][(res+k)\%m]+=dp[i-1][k];$
注意它是会爆ll的，那么我们需要让他在一个k达不到的值即可。
然后我们枚举后20位，因为$10^{18}\ast 20<10^{20}$
对于当前一位，我们查看它之后一位而不是它本身，因为这一位取模之后我不知道它是从哪些地方转移过来的，但是确定了这一位的值，那么我就知道下一位是从哪里转移过来的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e4+5;
const ll mod=1e9+7;
const ll inf=2e18;
char s[N];
int a[N];
ll p_mod[N],p_m[N],dp[N][21];
int main()
{int t;scanf("%d",&t);while(t--){int n,m,q;scanf("%d%d%d",&n,&m,&q);scanf("%s",s);ll ans=0,_m=0;int cnt=0;for(int i=0;i<n;i++){if(s[i]!='?'){ans=(ans*10+(ll)(s[i]-'0'))%mod;_m=(_m*10+(ll)(s[i]-'0'))%m;}elseans=ans*10%mod,_m=_m*10%m;}for(int i=n-1;~i;i--)if(s[i]=='?')a[++cnt]=n-i-1;p_mod[0]=p_m[0]=1;for(ll i=1;i<=n;i++)p_mod[i]=p_mod[i-1]*10%mod,p_m[i]=p_m[i-1]*10%m;dp[0][0]=1;for(int i=1;i<=cnt;i++){for(int j=0;j<m;j++)dp[i][j]=0;for(int j=0;j<=9;j++){int res=j*p_m[a[i]]%m;for(int k=0;k<m;k++){dp[i][(res+k)%m]+=dp[i-1][k];dp[i][(res+k)%m]>inf&&(dp[i][(res+k)%m]=inf);}}}_m=(m-_m)%m;ll aa=ans;while(q--){ll k;scanf("%lld",&k);if(dp[cnt][_m]<k){printf("-1\n");continue;}ans=aa;int now_m=_m,ne_m;for(int i=min(20,cnt);i;i--){for(ll j=0;j<=9;j++){ne_m=(now_m-j*p_m[a[i]]%m+m)%m;if(dp[i-1][ne_m]<k)k-=dp[i-1][ne_m];else{ans=(ans+p_mod[a[i]]*j)%mod;now_m=ne_m;break;}}}printf("%lld\n",ans);}}return 0;
}

这篇关于2019 Multi-University Training Contest 6 11 Dimensions DP 求第k大m的倍数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---