Time is not enough.
Previously, I was misunderstood by the search code, thinking that the digital DP is actually a memory search. (Although the search is really comfortable and good to think)
But later it was discovered that the standard format of digital DP is in fact preprocessing + DP…
Introduction of digital DP
The digital DP is actually the number of numbers that you deal with in an interval that satisfies the conditions, but in general the interval is desperately large… For example, 1e9 is conscience. The general rule is 1e18 or even 1e10.n （n Usually 3 or 5 times.
General solution of digital DP
Then we know that we can’t judge whether the number satisfies the condition one by one, so we introduce the concept of digital processing.
If the number of digits not more than I bits (such as I = 10, 100, 1000, 1e4, 1e5) is satisfied, DP [i] means less than or equal to 10i How many of the numbers satisfy the conditions?
But most of the questions have something to do with the numbers themselves (such as not having certain numbers or having to have certain formulas and so on), so we have to add one dimension (or multi-dimension) to transfer.
Then dp[i][j] means the number of I satisfying J.
Next, we press the bit again. Interval endpointProcessing. Why is the interval endpoint handled here?（Is it not obvious? Otherwise, do you enumerate each number in the interval?
Recalling the previous operation, we can use the preprocessed information to calculate how many numbers satisfy the conditions in the range of 1 to a certain number, because we calculate the prefix information, satisfying the interval additivity (subtraction).
So we can figure out how many numbers satisfy the conditions in the intervals of $1 to L-1 and $1 to R ([L, R] is the range of numbers that satisfy the conditions), and subtract the answer.
How to achieve it concretely? We usually think about fixing a number on the bit (i) we’re dealing with (but it’s less than the number of bits (i) of n), and then it’s easy to see that we can fill i n any number we want.
When we’ve finished, we fill i n the first place of n (or record it and compare it with the next one, depending on the topic), and iterate through the next steps.
However, digital DP says DP, sometimes DP arrays are pre processed and cumulative answers… Excellent!
I don’t think it’s very useful to read all this stuff (after all, it’s true to know what the theory is all about when you’re all doing things uuuuuuuuuuuu
Basic introduction to digital DP
Let’s have three blue questions first. (really, there is no lighter problem. QwQ)
- Luo Valley P2657 [SCOI2009]windy number
- P2518 [HAOI2010] counting
- Luo Valley P3413 SAC#1 – sprouting number
I believe you all have seen the current labels.（Watt? Province selection? FAQ!) 。。。But don’t give up your treatment in the year of Sao… It’s not so horrible when you do it!
1.Luo Valley P2657 [SCOI2009]windy number
Title Description
windyA windy number is defined. A positive integer without a leading zero and a difference of two adjacent numbers at least 2 is called the windy number. Windy wants to know.
How many windy numbers are there between A and B, including A and B?
Input output format
Input format:
Contains two integers, A B.
Output format:
An integer
Analysis
No, just pretreat the number of digits in the range of I digits to meet the difference greater than 1, and then it’s hard to explain the general solv clearly, depending on the code.
Code
1 //by Judge 2 #include<iostream> 3 #include<cstdio> 4 #define ll long long 5 using namespace std; 6 const int M=21; 7 ll f[M][10][10],d[M],l,r,ans; 8 inline bool get(int x){ return x>1 || x<-1; } //Judging whether or not to meet the requirements 9 inline void prep(){ //Pretreatment is not difficult to understand.10 for(int i=2,x,y,z;i<=10;++i) for(x=0;x<=9;++x) 11 for(y=0;y<=9;++y) if(get(x-y)){ //Enumeration if conditions are met.12 for(z=0;z<=9;++z) if(get(y-z)) //If we satisfy the conditions, we will accumulate.13 f[i][x][y]+=f[i-1][y][z]; 14 if(i==2) ++f[i][x][y]; //Under special circumstances, i==2 can not be accumulated, and +1 is directly manual.15 } 16 } 17 inline ll solv(int n,ll res=0,int len=0){ 18 if(n<10) return n; //10The number within is bound to satisfy, return directly, or decompose the number of operations.19 while(n) d[++len]=n%10,n/=10; int las=-1; //lasIt's the last digit.20 for(int i=2,j,k;i<len;++i) for(j=1;j<=9;++j) //Enumeration state (since the number of digits less than the current n is unrestricted, can be directly accumulated), as for the number of digits equal to len we deal with another21 for(k=0;k<=9;++k) res+=f[i][j][k]; 22 res+=9; bool flag=1; //The answer is +9 (actually the 9 numbers of 1~9), and then set up a flag.23 for(int i=len,j,k;i>1;--i){ //Processing from low to high24 for(j=0;j<d[i];++j) if((i^len || j) && get(j-las)) //The highest level is not zero, and the difference between J and the last digit is > the 1 begins with enumeration.25 for(k=0;k<=9;++k) res+=f[i][j][k]; //The answer is cumulative.26 if(!get(las-d[i])){ flag=0; break; } las=d[i]; //If processing to the current bit does not meet the conditions otherwise Las records the current number, ready for the next calculation27 } 28 if(flag) for(int j=0;j<=d[1];++j) //If flag is still there, it is shown that the number of 2~len in front satisfies the condition, so the lowest position accumulates the answer.29 if(get(j-las)) ++res; 30 return res; 31 } 32 signed main(){ 33 cin>>l>>r,prep(); //Preprocessing34 ans=solv(r)-solv(l-1); //Calculate the answer35 printf("%lld\n",ans); 36 return 0; 37 }
I believe that with the introduction of the first question, there will be less trouble in the back…………………………………………………………….
2.P2518 [HAOI2010] counting
Title Description
You have a set of non-zero numbers (not necessarily unique), and you can insert any number of zeros into it, so you can produce an infinite number. For example, given {1,2}, you can generate digital 12,2110212020121010021020, and so on.
Now let’s give a number and ask how many numbers there are before this number. (note that this number does not have a lead 0).
Input output format
Input format:
There are only 1 rows, which are 1 integers n..
Output format:
Only integers, representing the number of numbers before N.
Analysis
This question is not so difficult. Preprocessing the combination number is OK!
But think of yourself as being silly * arranging the numbers directly (that is, multiplying them by factories) and wondering how the answer is so big
Be careful! The same number of places to change the position is still a solution! (to yourself)
Code
1 //by Judge 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #define ll long long 6 using namespace std; 7 char s[60]; 8 ll len,d[60],num[15],C[60][60]; 9 inline void prep(){ //Preprocessing combination number10 for(int i=0;i<=50;++i) C[i][0]=1; 11 for(int i=1,j;i<=50;++i) for(j=1;j<=50;++j) 12 C[i][j]=C[i-1][j-1]+C[i-1][j]; 13 } 14 inline ll solv(){ 15 ll ans=0,tot,tmp; 16 for(int i=1,j,k;i<=len;++i){ 17 for(j=0;j<d[i];++j) if(num[j]){ 18 --num[j],tmp=1,tot=len-i; //Fill this in first.19 for(k=0;k<=9;++k) tmp*=C[tot][num[k]],tot-=num[k]; //Then the number of multiplicative solutions (num[k] numbers in TOT spaces).20 ans+=tmp,++num[j]; //Accumulate the answers and bring back the numbers.21 } --num[d[i]]; //The current digit is lost and the next digit is taken.22 } return ans; 23 } 24 signed main(){ 25 scanf("%s",s+1),prep(),len=strlen(s+1); //Decomposition number26 for(int i=1;i<=len;++i) ++num[d[i]=s[i]-'0']; //How many treatments per figure?27 printf("%lld\n",solv()); return 0; 28 }
Title Background
This topic is provided by SOL, the most spicy chicken in the world.
Lonesome City website is the official website of the perfect information classroom. Address: http://191.101.11.174/mgzd.
Title Description
Spicy chicken SOL is a fool. He actually thinks it’s very sprouting.
Fortunately, in his eyes, not all numbers are sprouting up. Only the number satisfying “palindrome substrings of at least 2 in length” is germinative – that is, 101 is germinative, because 101 itself is a palindrome number; 110 is germinative, because it contains palindrome substrings 11; but 102 is not germinative, 1.201 was not born either.
Now SOL wants to know the number of sprouts from all the integers from L to R.
Since the answer may be large, it is necessary to output the answer to the residue of 1000000007 (10^9+7).
Input output format
Input format:
The input contains only 1 rows, which contain two integers: l and R.
Output format:
Output is only 1 rows, contains an integer, that is the answer.
Analysis
We can analyze from the title that if there is a length > = 2 palindrome substring in a number, there must be a palindrome substring of length 2 or 3 (we can remove both ends of the palindrome substring repeatedly until the length is 2 or 3).
Then we thought it was too cumbersome to calculate the number of satisfied numbers, so we could calculate the number of unsatisfied numbers, and then subtract from tot, and the answer came out.
Then we can start the state transition by designing a three-dimensional DP state (recording the number of digits of bit i, first bit j, second bit k).
Code
1 // luogu-judger-enable-o2 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 const int N=1111; 6 const ll mod=1e9+7; 7 ll f[N][10][10],ans; 8 string l,r; 9 inline void prep(){ //Preprocessing is not explained.10 for(int i=2,x,y,z;i<=1000;++i) for(x=0;x<=9;++x) 11 for(y=0;y<=9;++y) if(x!=y){ 12 for(z=0;z<=9;++z) if(x!=z && y!=z) 13 f[i][x][y]+=f[i-1][y][z]; 14 if(i==2) ++f[i][x][y]; f[i][x][y]%=mod; 15 } 16 } 17 inline ll solv(string s){ 18 int len=s.length(),X=-1,Y=-1; //Here is a little bit special, to record the first two numbers.19 ll tot=0,ans=0; bool flag=1; 20 for(int i=0;i<len;++i) tot=(tot*10+s[i]-'0')%mod; 21 for(int i=2,x,y;i<len;++i) for(x=1;x<=9;++x) 22 for(y=0;y<=9;++y) ans=(ans+f[i][x][y])%mod; 23 if(len>1) ans+=10; 24 for(int i=len,j,k;i>1;--i){ 25 int now=s[len-i]-'0'; 26 for(j=0;j<now;++j) if((i!=len || j!=0) && X!=j && Y!=j ) 27 for(k=0;k<=9;++k) if(j!=k && k!=X) ans=(ans+f[i][j][k])%mod; 28 if(now==X || now==Y) { flag=0; break; } Y=X,X=now; //Similar to windy numbers?29 } 30 if(flag) for(int j=0;j<=s[len-1]-'0';++j) 31 if(j!=Y && j!=X) ans=(ans+1)%mod; 32 return (tot+1+mod-ans)%mod; 33 } 34 int main(){ 35 prep(),cin>>l>>r; 36 ans=(solv(r)-solv(l)+mod)%mod; 37 for(int i=1;i<=l.length()-1;++i) //There are two ways to solve the problem of too long a number. One is to reduce violence (according to the principle of borrowing from a higher position if the current position is not enough). Here is whether the current number of violence is satisfied or not, satisfaction will accumulate.38 if(l[i]==l[i-1] || l[i-1]==l[i+1]){ 39 ans=(ans+1)%mod; break; 40 } 41 printf("%lld\n",ans); 42 }
The basic entry is finished. Here are a bunch of questions.（Uh… Don’t blow your face.
loj The third chapter: digital dynamic programming.
- #10163 「One pass 5.3 cases 1 “Amount of Degrees
- #10164 「A digital game of 5.3 cases, 2.
- #10165 「One pass 5.3 cases 3 “Windy number (emmm…)
- #10166 「A number 5.3 practice 1 “digital game”
- #10167 「One exercise 5.3 practice 2 “do not 62
- #10168 「One book 5.3 exercises 3, hate 7 no wife.
- #10169 「One through 5.3 exercise 4 “digit count
After doing these questions, you will find that I have been caught in the pit. (╯‵□′)╯︵┻━┻ ）…
emmm…But ah… Do you have any sense of accomplishment at the same time? (forcibly explained)
Cough and cough… Actually, this is also a historical reference. What plays the piano?（Uh… Don’t blow your face.
Digital DP training
Let’s put two questions.
- The number theory of P4317 Flower God
- Luo Valley P4124 [CQOI2016] mobile phone number
Save emmm…（Uh… Don’t blow your face.
1.The number theory of P4317 Flower God
Title Background
As we all know, the flower god has been using the boundless magic power to abuse OJ, OI, CF and TC for many years. Of course, it also includes CH.
Title Description
The flower god has come to lecture again this day. After class, as usual, there are super difficult questions. I waited for him to suffer. The theme of Flower God is this:\text{sum}(i)sum(i)Representationii Binary representation11 The number of the number. Give a positive integer.NN ，The flower god wants to ask you.\prod_{i=1}^{N}\text{sum}(i)∏i=1Nsum(i) ，That is,\text{sum}(1)\sim\text{sum}(N)sum(1)∼sum(N)The product of the product.
Input output format
Input format:
A positive integer N.
Output format:
A number, the value of the answer module 10000007.
Analysis
emmmm…Calculate the product of sum[1~n]. Actually, it’s quite routine.
When we split the numbers, we split them into binaries, and then do it routinely, stuffing one bit behind the I-1 bit of the current processing each time.
Then calculate the number of the 1 number of plugs, and finally the fast power will be multiplied into the answer.
When I was doing it, I was entangled with a half day Lucas’s preprocessing, 502 Violence is a good combination. Look at the code!
Code
1 // luogu-judger-enable-o2 2 //by Judge 3 #include<iostream> 4 #include<cstdio> 5 #define ll long long 6 using namespace std; 7 const int M=55; 8 const ll mod=1e7+7; 9 ll n,len,cnt,ans=1; 10 ll C[M][M],d[M],num[M]; 11 inline void prep(){ //Preprocessing combined number templates? 12 for(int i=0;i<=50;++i) C[i][0]=1; 13 for(int i=1,j;i<=50;++i) for(j=1;j<=50;++j) 14 C[i][j]=C[i-1][j]+C[i-1][j-1]; 15 } 16 inline ll quick_pow(ll x,ll p,ll ans=1){ //Fast power template? 17 while(p){ 18 if(p&1) ans=ans*x%mod; 19 x=x*x%mod, p>>=1; 20 } return ans; 21 } 22 signed main(){ 23 cin>>n,prep(); 24 while(n) d[++len]=n&1,n>>=1;//Transform binary 25 for(ll i=len,j;i;--i) if(d[i]){ 26 for(j=1;j<i;++j) //The number of combinations is random. 27 num[cnt+j]+=C[i-1][j]; 28 ++num[++cnt]; 29 } 30 for(ll i=1;i<=len;++i) //Direct multiply 31 ans=ans*quick_pow(i,num[i])%mod; 32 cout<<ans<<endl; return 0; 33 }
2. Luo Valley P4124 [CQOI2016] mobile phone number
Title Description
When people choose cell phone numbers, they hope that the number is good and lucky. For example, the number contains several adjacent numbers, no homonyms, unlucky figures, etc. Mobile phone operators will also consider these factors when issuing new numbers, from the segment to select a number containing certain characteristics for sale separately. In order to facilitate early planning, transportationThe business wants to develop a tool to automatically count the number of characters that satisfy the characteristics in the paragraph.
There are two characteristics that the tool needs to detect: the number should appear at least.33 The same number adjacent to each other; the number can not appear at the same time.88 And44。The number must contain two features at the same time. The numbers that satisfy the conditions are: 13000988721, 23333333333, 14444101000. The numbers that do not satisfy the conditions are: 1015400080, 10010012022.
The phone number must be11 Bits without leading00。The tool receives two numbers.LL AndRR，Automatic statistics[L,R][L,R] The number of all qualified numbers in the interval.LL AndRR Also1111 Mobile phone number.
Input output format
Input format:
There is only one row of input files, separated by spaces.22 Positive integerL,RL,R。
Output format:
The output file contains only one line.11 An integer to indicate the number of mobile phones that meet the requirements.
Analysis
5Dimension state directly!…The first dimension, the second dimension is which number, the third dimension ahead of a number of the same situation, the fourth dimension 8 appeared or not, the fifth dimension 4 appeared or not.
Code
1 //by Judge 2 #include<iostream> 3 #include<cstdio> 4 #define ll long long 5 using namespace std; 6 ll L,R,d[15],f[15][15][5][2][2]; // F[ i,j,k,et,fr] Indicates the position I, which has the same K in front, whether 8 has occurred, and whether 4 has occurred. 7 inline void prep(){ //Preprocessing DP array 8 for(int i=0,j,c,et,fr,w;i<=11;++i) for(j=0;j<=9;++j) 9 for(c=1;c<=3;++c) for(et=0;et<=1;++et) for(fr=0;fr<=1;++fr){ 10 ll &t=f[i][j][c][et][fr]; if(!i) t=(c==3?1:0); 11 else for(w=0;w<=9;++w) t+=f[i-1][w][c==3?3:w==j?c+1:1][et||(w==8)][fr||(w==4)]; 12 if(et && fr) t=0; 13 } 14 } 15 inline ll solv(ll n){ 16 ll len=0,ans=0,c=0,et=0,fr=0; 17 while(n) d[++len]=n%10,n/=10; //Decomposition number18 if(len<11) return 0; d[len+1]=-1; //Special judgement of L=1e1119 for(int i=len,j;i;--i){ //Violent enumeration transfer20 for(j=0;j<d[i];++j) ans+=f[i-1][j][c==3?3:d[i+1]==j?c+1:1][(j==8)||et][(j==4)||fr]; 21 c=(c==3?3:d[i]==d[i+1]?c+1:1),et|=d[i]==8;fr|=d[i]==4; if(et && fr) break; 22 } return ans-f[10][0][1][0][0]+f[0][d[1]][c][et][fr];; 23 } 24 signed main(){ prep(),scanf("%lld%lld",&L,&R),printf("%lld\n",solv(R)-solv(L-1)); return 0; } //One row principal function
Here are some more topics:
- Similar distribution of P4127 [AHOI2009]
- P2606 [ZJOI2010] counting in Luo Valley
- Count P3281 [SCOI2013]
- Shopping tour of Uncle P3286 [SCOI2014]
（Just four questions, and I haven’t done it yet… 0)
The code is as follows:
P4127：（…Code is very short, the idea is very round.
1 //by Judge 2 #include<cstring> 3 #include<cstdio> 4 #define ll long long 5 using namespace std; 6 ll f[23][200][200][2],d[23],l,r; //The number of bits, the whole number of%sum, the number of digits and%sum, whether the upper bound of the current bit is reached. 7 inline ll solv(ll n){ 8 ll len=0,ans=0,tmp; 9 while(n) d[++len]=n%10,n/=10; 10 for(int sum=1,i,s,m,c,k;sum<=len*9;++sum){ 11 memset(f,0,sizeof(f)), f[len+1][0][0][1]=1; 12 for(i=len;i;--i) for(s=0;s<=sum;++s) 13 for(m=0;m<sum;++m) for(c=0;c<=1;++c){ 14 tmp=f[i+1][s][m][c]; if(!tmp) continue; 15 for(k=0;k<=(c?d[i]:9) && s+k<=sum;++k) 16 f[i][s+k][(m*10+k)%sum][c&(k==d[i])]+=tmp; 17 } ans+=f[1][sum][0][0]+f[1][sum][0][1]; 18 } return ans; 19 } 20 signed main(){ 21 scanf("%lld%lld",&l,&r); 22 printf("%lld\n",solv(r)-solv(l-1)); 23 return 0; 24 }
View Code
P3281：（See here for details)
1 //by Judge 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #define ll long long 6 #define int long long 7 using namespace std; 8 const int M=1e5+111; 9 const ll mod=20130427; 10 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 11 char buf[1<<21],*p1=buf,*p2=buf; 12 inline int read(){ 13 int x=0,f=1; char c=getchar(); 14 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 15 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 16 } 17 ll B,len,ans,d[M],f[M]={1},sum[M]={1},pre[M],sub[M],dp[M][2]; 18 inline void prep(){ for(int i=1,j;i<=1e5;++i) f[i]=f[i-1]*B%mod,sum[i]=(sum[i-1]+f[i])%mod; } 19 inline ll solv(){ 20 ll ans=pre[len+1]=0; 21 for(int i=1;i<=len;++i) sub[i]=(d[i]*f[i-1]%mod+sub[i-1])%mod; 22 for(int i=len;i>=1;--i) pre[i]=(pre[i+1]*B%mod+d[i])%mod; 23 for(int i=1;i<=len;++i){ //All kinds of nausea... 24 dp[i][0]=(dp[i-1][0]*B%mod+B*(B-1)/2%mod*f[i-1]%mod*sum[i-1]%mod)%mod; 25 dp[i][1]=(dp[i-1][0]*d[i]%mod+d[i]*(d[i]-1)/2%mod*f[i-1]%mod*sum[i-1]%mod)%mod; 26 dp[i][1]=(dp[i][1]+dp[i-1][1]+d[i]*(sub[i-1]+1)%mod*sum[i-1]%mod)%mod; 27 ans=(ans+max(0ll,pre[i+1]-1)*dp[i][0]%mod+dp[i][1])%mod; 28 } return ans; 29 } 30 signed main(){ 31 B=read(),len=read(),prep(); 32 for(int i=len;i;--i) d[i]=read(); 33 for(int i=1;i<=len;++i) 34 if(d[i]){ --d[i]; break; } 35 else d[i]=B-1; 36 if(!d[len]) --len; 37 ans=-solv(), len=read(); 38 for(int i=len;i;--i) d[i]=read(); 39 ans+=solv(),printf("%lld\n",(ans%mod+mod)%mod); return 0; 40 }
View Code
P3286：（I don’t know much about it.
1 //by Judge 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #define ll long long 6 using namespace std; 7 const int M=70; 8 ll L,R,K,num[M],f[M][4000]; 9 ll dfs1(ll n,ll s,bool lim){ 10 if(!n) return s; 11 if(!lim && f[n][s]>=0) return f[n][s]; 12 ll res=0,k=lim?num[n]:K-1; 13 for(ll i=0;i<=k;++i) 14 res+=dfs1(n-1,s+i*(n-1),lim&&(num[n]==i)); 15 if(!lim) f[n][s]=res; return res; 16 } 17 ll dfs2(ll n,ll s,ll m,ll lim){ 18 if(s<0) return 0; if(!n) return s; 19 if(!lim && f[n][s]>=0) return f[n][s]; 20 ll res=0,k=lim?num[n]:K-1; 21 for(ll i=0;i<=k;++i) 22 if(n>=m) res+=dfs2(n-1,s+i,m,lim&(num[n]==i)); 23 else res+=dfs2(n-1,s-i,m,lim&(num[n]==i)); 24 if(!lim) f[n][s]=res; return res; 25 } 26 inline ll calc(ll n){ 27 ll len=0; 28 memset(f,-1,sizeof(f)); 29 while(n) num[++len]=n%K,n/=K; 30 ll res=dfs1(len,0,1); 31 for(ll i=2;i<=len;++i) 32 memset(f,-1,sizeof(f)), 33 res-=dfs2(len,0,i,1); 34 return res; 35 } 36 signed main(){ 37 cin>>L>>R>>K, cout<<calc(R)-calc(L-1)<<endl; return 0; 38 }
View Code
Judge’s class… ヾ(ToT)Bye~Bye~ （Dead tired… Wrote for more than two hours… Ask for recommendation)