Good Bye 2017 G. New Year and Original Order
2024-09-30 14:48:28
G. 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 modulo 109 + 7.
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.
tls原话:最简单的数位dp,出题人成功骗过验题人放在了G。
Oh...uuu...原来是简单的数位dp...等等...tls的简单,莫不是.....
#include<bits/stdc++.h>
#define LL long long
using namespace std;
char s[];
int dp[][][],res;
const int mod=1e9+;
int main()
{
cin>>s;
int len=strlen(s);
int ll,kk,i,j,k,l,m;
for(i=;i<=;i++)
{
dp[][][]=;
for(j=;j<len;j++)
for(k=;k<=j;k++)
for(l=;l<=;l++)
for(m=;m<=;m++)
{
if(m<s[j]-'') ll=;
else if(m==s[j]-'') ll=l;
else if(l) continue;
else ll=;
if(m>=i) kk=k+;
else kk=k;
dp[j+][kk][ll]=(dp[j+][kk][ll]+dp[j][k][l])%mod;
}
for(j=,k=;j<=len;j++)
{
res=(res+(LL)k*(dp[len][j][]+dp[len][j][]))%mod;
k=(k*10ll+)%mod;
}
for(j=;j<=len;j++)
for(k=;k<=j;k++)
for(l=;l<=;l++)
dp[j][k][l]=;
}
cout<<res<<endl;
return ;
}
九月巨巨的滚动数组:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+,maxn=;
#define LL long long
LL sum[maxn][],dp[maxn][];
string s;
inline void Update(LL &x,LL y)
{
x=(x+y)%mod;
}
void Clear()
{
memset(dp,,sizeof(dp));
memset(sum,,sizeof(sum));
dp[][]=;
}
int main()
{
cin>>s;
int len=s.length();
LL ans=;
for(int l=;l<=;l++)
{
Clear();
for(int i=;i<len;i++)
for(int j=;j<;j++)
for(int k=;k<=;k++)
{
if(!j&&k>s[i]-'') continue;
Update(dp[i+][j|k<s[i]-''],dp[i][j]); ///j和k<s[i] 任意一个是1就为1
if(k<l) Update(sum[i+1][j|k<s[i]-'0'],sum[i][j]);
else Update(sum[i+1][j|k<s[i]-'0'],(sum[i][j]*10+dp[i][j])%mod);
}
Update(ans,sum[len][]);
Update(ans,sum[len][]);
}
cout<<ans<<endl;
return ;
}
最新文章
- bzoj2179: FFT快速傅立叶
- UVA 11419SAM I AM(输出 最小覆盖点 )
- 8.11 CSS知识点4
- uml定义的使用的关系
- 段落排版--缩进(text-indent)
- URAL 1792. Hamming Code (枚举)
- LeetCode OJ 119. Pascal&#39;s Triangle II
- Vue.js优雅的实现列表清单
- 中断处理程序不能使用printf的本质
- luoguo 1306 斐波那契公约数
- codeblock 生成和使用makefile
- python 的基础 学习 第五天 基础数据类型的操作方法
- ambari 安装HDP3.0.1后,启动服务的问题记录
- codeforces #305 E Mike and friends
- 20155228 2016-2017-2 《Java程序设计》第8周学习总结
- day4----函数-闭包-装饰器
- [Jmeter] Concurrency Thread Group
- mac下配置android环境变量
- 【转】web应用缓慢故障分析
- wait(),notify(),notifyAll()用来操作线程为什么定义在Object类中?