题解 P3413 【SAC#1 - 萌数】

巨型方块

2017-07-30 16:50:13

Solution

百度果然搜不到题解,最后我在google 里面找到了; 首先回文串嘛>2就好啦 所以我们只要判断2情况 aa或者aba; 所以我们f[i][j][k] 表示第i位为j i-1位为k的所有萌; 那么显然对于重复很难判断; 所以我萌有2种方法,一是在开一维数组记录是否出现; 另外的方法就是吧f[i][j][k]记录的是当前状态的非萌; 那我就用了第二种; 那么这样的话只要特判i=1的情况,f数组可以方便的求了; 那么之后的话就是数位dp了; ```cpp #include<bits/stdc++.h> #define Ll long long using namespace std; const int N=1e3+5; Ll f[N][10][10],mo=1e9+7,ans; string l,r; void dp(){ for(int i=2;i<=1000;i++) for(int x=0;x<=9;x++) for(int y=0;y<=9;y++)if(x!=y){ for(int z=0;z<=9;z++) if(y!=z&&x!=z) f[i][x][y]+=f[i-1][y][z]; if(i-1==1)f[i][x][y]++; f[i][x][y]%=mo; } } Ll out(string s){ int n=s.length(),X=-1,Y=-1; Ll tot=0,ans=0;bool ok=1; for(int i=0;i<n;i++)tot=(tot*10+s[i]-48)%mo; for(int i=1;i<n;i++) for(int x=1;x<=9;x++) for(int y=0;y<=9;y++) ans=(ans+f[i][x][y])%mo; if(n>1)ans+=10;//10的含义是0~9这10个数字 for(int i=n;i>1;i--){ int v=s[n-i]-48; for(int j=0;j<v;j++)if(i!=n||j!=0) for(int k=0;k<=9;k++) if(X!=j&&Y!=j&&j!=k&&k!=X) ans=(ans+f[i][j][k])%mo; if(v==X||v==Y){ok=0;break;} Y=X;X=v; } if(ok)for(int j=0;j<=s[n-1]-48;j++) if(j!=Y&&j!=X)ans=(ans+1)%mo; return(tot+1-ans+mo)%mo;//1的含义就是0这个数字 } int main() { dp(); cin>>l>>r; ans=(out(r)-out(l)+mo)%mo; for(int i=1;i<=l.length()-1;i++) if(l[i]==l[i-1]||(i>1&&l[i]==l[i-2])){ ans=(ans+1)%mo;break; } printf("%lld",ans); } ```