New Year and Original Order
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Let S(n) denote the number that represents the digits of n in sorted order. For example, S(1) = 1, S(5) = 5, S(50394) = 3459, S(353535) = 333555.
Given a number X, compute 
Input
The first line of input will contain the integer X (1 ≤ X ≤ 10700).
Output
Print a single integer, the answer to the question.
Examples
input
21
output
195
input
345342
output
390548434
Note
The first few values of S are 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 12. The sum of these values is 195.
数位dp
f[i][j]k][o]
表示考虑了前i位，有j位>=k 是否<=n 的方案数
最后统计答案就枚举每个数 扫一遍就好了
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=710,mod=int(1e9)+7;
int n,f[N][N][10][2];
char s[N];
int main()
{
register int i,j,k,o,p;
scanf("%s",s+1);
int n=strlen(s+1);
for(i=1;i<=9;++i) f[0][0][i][0]=1;
for(i=0;i<n;++i)
for(j=0;j<=i;++j)
for(k=1;k<=9;++k)
for(o=0;o<2;++o)
for(p=0;p<=(o ? 9 : s[i+1]-'0');++p)
(f[i+1][j+(p>=k)][k][o|(p<s[i+1]-'0')]+=f[i][j][k][o])%=mod;
ll ans(0);
for(k=1;k<=9;++k)
{
ll tmp(1);
for(i=1;i<=n;++i,tmp=(tmp*10+1)%mod)
(ans+=tmp*(f[n][i][k][0]+f[n][i][k][1]))%=mod;
}
cout<<ans<<endl;
}
/*
21
195
345342
390548434
*/