https://ac.nowcoder.com/acm/contest/43058/C
思路
一个很简单的dp
记录每一位i可以给下一位的j提供的方案数
理论上层数应该倒着枚举，但是我这个写法恰好避免了重复，所以正着倒着都是对的
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<bitset>
#define ll long long
#define gc getchar
#define maxn 1000005
#define mo 1000000007
using namespace std;inline ll read(){ll a=0;int f=0;char p=gc();while(!isdigit(p)){f|=p=='-';p=gc();}while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}return f?-a:a;
}int n;
ll ans,f[10][15];char s[maxn];
int main(){scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;++i){int d=s[i]-'0';if(i>=7)ans=(ans+f[6][d])%mo;if(i>=6)for(int j=d-1;~j;--j)f[6][j]=(f[6][j]+f[5][d])%mo;if(i>=5)for(int j=d-1;~j;--j)f[5][j]=(f[5][j]+f[4][d])%mo;if(i>=4)for(int j=d-1;~j;--j)f[4][j]=(f[4][j]+f[3][d])%mo;if(i>=3)for(int j=d+1;j<=9;++j)f[3][j]=(f[3][j]+f[2][d])%mo;if(i>=2)for(int j=d-1;~j;--j)f[2][j]=(f[2][j]+f[1][d])%mo;for(int j=d+1;j<=9;++j)++f[1][j];}printf("%lld\n",ans);return 0;
}
