給出上下界，讓你求出其中滿足條件：不同的數字的數量不超過k個的數字的總和，答案模998244353，比如123里不同的數字個數為3，113里不同的數字個數為2，111里不同的數字個數為1。

跟普通的數位dp相比，這道題的不同在于是求總和，不是求數字的個數，但我們可以在求數字個數的基礎上再進行求和，以下可以看代碼注釋。 ??

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<stack> #include<map> #include<vector> #include<queue> #include<set> #include<iomanip> #include<cctype> #include<ctime> using namespace std; typedef long long ll; #define edl putchar('\n') #define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define FOR(i,a,b) for(int i=a;i<=b;i++) #define ROF(i,a,b) for(int i=a;i>=b;i--) #define FORLL(i,a,b) for(ll i=a;i<=b;i++) #define ROFLL(i,a,b) for(ll i=a;i>=b;i--) #define mst(a) memset(a,0,sizeof(a)) #define mstn(a,n) memset(a,n,sizeof(a)) #define zero(x)(((x)>0?(x):-(x))<eps) #define si(a) scanf("%d",&a) #define sl(a) scanf("%lld",&a) #define sd(a) scanf("%lf",&a) #define ss(a) scanf("%s",a) inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int month[15]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{1,-1},{-1,1}}; const int MAXN=2e5+5; const int INF=1<<30; const long long mod=998244353; const double eps=1e-8; const ll inff=0x3f3f3f3f3f3f3f3f; ll dp[25][1030][12];/*記錄答案總和的數組*/ ll d[25][1030];/*記錄答案個數的數組*/ ll t[25];/*10的冪次方，節省時間*/ int a[25];/*記錄每一位數字*/ int f[25];/*2的冪次方，節省時間*/ int k[1030];/*狀態壓縮，記錄某個狀態有多少個不同的數字*/ int p;/*題目問的最大不同數量*/ struct num {ll a,b;/*a對應d數組，b對應dp數組*/ }s; num dfs(int pos,int now,int sta,int limit) {if(pos==0){return (num){1,now};} if(!limit&&dp[pos][sta][now]!=-1){return (num){d[pos][sta],dp[pos][sta][now]};}int up=limit?a[pos]:9,g;ll ans=0,cnt=0;FOR(i,0,up){if(sta==0&&i==0)/*前導0的特殊判斷*/ {s=dfs(pos-1,i,sta,limit&&i==up);cnt+=s.a;/*答案個數*/ans+=s.b;/*答案總和*/cnt%=mod;ans%=mod;}else{g=sta|f[i];if(k[g]<=p){s=dfs(pos-1,i,g,limit&&i==up);cnt+=s.a;/*答案個數*/ans+=s.b;/*答案總和*/cnt%=mod;ans%=mod;}} }ans=(ans+cnt*t[pos]%mod*(ll)now%mod)%mod;if(!limit)d[pos][sta]=cnt,dp[pos][sta][now]=ans;return (num){cnt,ans}; } ll solve(ll x) {if(x==0) return 0;int pos=0;while(x){a[++pos]=x%10;x/=10;}a[pos+1]=0;return dfs(pos,0,0,1).b; } int main() {ll n,m;f[0]=1,t[0]=1;FOR(i,1,18)f[i]=f[i-1]*2,t[i]=t[i-1]*10,t[i]%=mod;FOR(i,0,1024){int j=i,cnt=0;while(j){cnt+=j%2;j/=2;}k[i]=cnt;}FOR(i,0,20)FOR(j,0,1024){d[i][j]=-1;FOR(I,0,9)dp[i][j][I]=-1;}//scanf("%d",&T);//while(1){scanf("%lld%lld%d",&n,&m,&p);n=solve(n-1);m=solve(m);printf("%lld\n",(m-n+mod)%mod);}return 0; }

　　

轉載于:https://www.cnblogs.com/qq936584671/p/9889829.html

總結

以上是生活随笔為你收集整理的数位dp：Educational Codeforces Round 53 (Rated for Div. 2) E. Segment Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。