emmm为啥这周这么少因为两场比赛力竭了。。。也可能是我太懒了hhh数位dp其实就是考虑对应进制的每一位去写转移方程或者是用记忆化dfs实现个人感觉后者好理解且好用就是调试的时候比较痛苦这类题有一个显著特点就是n基本都是超过1e8的遍历一遍直接超时。贴几个例题E - Digit Circus题目大意就是有三种限制条件要求找出恰好满足一种的个数1n10 500 10^{500}10500代码如下#includebits/stdc.h#defineintlonglongusingnamespacestd;constintMAX505;constintMOD998244353;intdp[MAX][110][3][2][2];string x;//sum各个位之和//used已经用的个数//flag3用过intSearch(intlen,intsum,intused,intflag,intfree,intnz,intcnt){intans0;if(!len){booljkl!sum;booluioflag;booliop(cnt3);if(jkl!uio!iop)return1;if(!jkluio!iop)return1;if(!jkl!uioiop)return1;return0;};if(freedp[len][used][sum][flag][nz]!-1)returndp[len][used][sum][flag][nz];intcurx[len]-0;// cout???curendl;intedfree?9:cur;for(inti0;ied;i){intnew_nznz||i;intnew_freefree||icur;intnew_flagflag||i3;intadd(1i)used;if(!new_nz)ans(ansSearch(len-1,(sumi)%3,used,new_flag,new_free,new_nz,cnt))%MOD;elseans(ansSearch(len-1,(sumi)%3,used|(1i),new_flag,new_free,new_nz,cnt(add?0:1)))%MOD;}if(free)dp[len][used][sum][flag][nz]ans;returnans;}signedmain(){memset(dp,-1,sizeof(dp));cinx;intlenx.length();reverse(x.begin(),x.end());x0x;coutSearch(len,0,0,0,0,0,0)-1;}数组dp用于记忆化搜索考虑要存些什么首先是len即当前处理的位置从高往低其次就是用10位表示0-9的选择状态对应110对应2进制上1表示选取0表示未选然后就是当前len位之前的各位之和mod3以及3是否出现过最后一位是是否最高位为0。有人可能会问free即是否前面贴着上限为什么不用存入dp其实因为我每次存的都是free才处理因为如果仍贴着上限每次继续选择的上线就会与当前位的数字有关就不能统一看成同一种情况。总的来说就是要考虑什么情况可以统一。E. Find Maximum题目大意就是每一位都可以用当前位置i的三进制各位之和数码表示问某个区间的最值像常规的数位dp都可以先求0-r区间的答案再求0-l-1的答案二者一减即可因为一般都是问满足条件的个数但是这题是要求最值只能在原本的基础上加一个下限写完也是力竭了。#includebits/stdc.h#defineintlonglongusingnamespacestd;constintMAX50;intdp[MAX][100][50][2];intSearch(intlen,intl,intr,intsum,boolfree_l,boolfree_r,intcnt,intoffset,intnz){intans-0x3f3f3f3f;if(!len){if(!nz)return1;ansmax(ans,sumcnt);returnans;}if(free_lfree_rdp[len][sum][cnt][nz]!-1)returndp[len][sum][cnt][nz];intcur_ll/offset;cur_l%3;intcur_rr/offset;cur_r%3;intstfree_l?0:cur_l;intedfree_r?2:cur_r;if(!nz){if(0st0ed){boolnfrfree_r||(0cur_r);ansmax(ans,Search(len-1,l,r,sum,free_l,nfr,cnt,offset/3,0));}for(intist;ied;i){if(i0)continue;booljklicur_l||free_l;booluioicur_r||free_r;ansmax(ans,Search(len-1,l,r,sumi,jkl,uio,cnt1,offset/3,1));}}else{for(intist;ied;i){booljklicur_l||free_l;booluioicur_r||free_r;ansmax(ans,Search(len-1,l,r,sumi,jkl,uio,cnt1,offset/3,1));}}if(free_lfree_r)dp[len][sum][cnt][nz]ans;returnans;}signedmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intt;cint;memset(dp,-1,sizeof(dp));while(t--){intl,r;cinlr;inttemp,len,offset;tempr,len0,offset1;while(temp){len;temp/3;offset*3;}coutSearch(len,l,r,0,false,false,0,offset/3,0)\n;}return0;}其他题其实也大差不差就是找到限制条件把记忆存储维度设好递归参数找齐多做几题就理解了。矩阵快速幂非常简单的一个知识点就是矩阵快速幂。while(b0){if(b%21)ans(ans*a)%c;a(a*a)%c;b1;}这是常规快速幂只需变成while(b0){if(b1)get1();get2();b1;}其中get1和get2换成对应的矩阵乘法即可贴上板子#includebits/stdc.h#defineintlonglongusingnamespacestd;constintMAXN105;constintMOD1e97;intans[MAXN][MAXN],a[MAXN][MAXN],temp[MAXN][MAXN];intn,k;voidget1(){memset(temp,0,sizeof(temp));for(inti1;in;i){for(intj1;jn;j){for(intl1;ln;l){temp[i][j](temp[i][j]ans[i][l]*a[l][j])%MOD;}}}for(inti1;in;i){for(intj1;jn;j){ans[i][j]temp[i][j];}}}voidget2(){memset(temp,0,sizeof(temp));for(inti1;in;i){for(intj1;jn;j){for(intl1;ln;l){temp[i][j](temp[i][j]a[i][l]*a[l][j])%MOD;}}}for(inti1;in;i){for(intj1;jn;j){a[i][j]temp[i][j];}}}voidquick(){while(k){if(k1)get1();get2();k1;}}signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinnk;for(inti1;in;i){for(intj1;jn;j){cina[i][j];}}for(inti1;in;i)ans[i][i]1;quick();for(inti1;in;i){for(intj1;jn;j){coutans[i][j] ;}coutendl;}return0;}什么你不知道什么是快速幂其实就是求a b a^{b}ab%c的值b可能非常大可以考虑b的二进制表示如果当前位是1就加入ans否则就自身翻倍。嗯就这些谢谢读完 ^ - ^