Submission #10165

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
string A, B;
int K;
int dp[100002][2][2][2];
int rec(string &s, int idx, bool free, bool zero, bool f)
{
if(idx == s.size()) return (f);
if(~dp[idx][free][zero][f]) return (dp[idx][free][zero][f]);
int end = free ? 9 : s[idx] - '0', ret = 0;
for(int i = 0; i <= end; i++) {
(ret += rec(s, idx + 1, free | (i != end), zero | (i != 0), f | (i == K && (zero | (i != 0))))) %= mod;
}
return (dp[idx][free][zero][f] = ret);
}
int solve(string &S)
{
memset(dp, -1, sizeof(dp));
return (rec(S, 0, 0, 0, 0));
}
int main()
{
cin >> A;
cin >> B;
cin >> K;
cout << (solve(B) - solve(A) + (count(begin(A), end(A), K + '0') >= 1) + mod) % mod << endl;
}

ステータス

項目 データ
問題 0565 - 桁
ユーザー名 ei1333
投稿日時 2016-11-09 14:47:22
言語 C++11
状態 Accepted
得点 2
ソースコード長 777 Byte
最大実行時間 82 ms
最大メモリ使用量 14988 KB

セット

セット 得点 Cases
1 SMALL 1 / 1 *small*
2 LARGE 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00.in AC 75 ms 14816 KB
2
00large.in AC 47 ms 14628 KB
2
00sample.in AC 20 ms 3528 KB
2
00small.in AC 23 ms 3584 KB
1
2
01.in AC 73 ms 14912 KB
2
01large.in AC 45 ms 14844 KB
2
01sample.in AC 21 ms 3740 KB
2
01small.in AC 19 ms 3672 KB
1
2
02.in AC 82 ms 14864 KB
2
02large.in AC 48 ms 14668 KB
2
02sample.in AC 22 ms 3564 KB
2
02small.in AC 23 ms 3620 KB
1
2
03.in AC 80 ms 14820 KB
2
03large.in AC 49 ms 14888 KB
2
03small.in AC 21 ms 3664 KB
1
2
04.in AC 71 ms 14856 KB
2
04large.in AC 44 ms 14788 KB
2
04small.in AC 21 ms 3692 KB
1
2
05.in AC 72 ms 14892 KB
2
05large.in AC 47 ms 14824 KB
2
05small.in AC 19 ms 3728 KB
1
2
06.in AC 72 ms 14924 KB
2
06large.in AC 45 ms 14852 KB
2
06small.in AC 26 ms 3744 KB
1
2
07.in AC 80 ms 14936 KB
2
07large.in AC 47 ms 14744 KB
2
07small.in AC 18 ms 3640 KB
1
2
08.in AC 78 ms 14968 KB
2
08large.in AC 41 ms 14896 KB
2
08small.in AC 17 ms 3796 KB
1
2
09.in AC 75 ms 14988 KB
2
09large.in AC 51 ms 14920 KB
2
09small.in AC 18 ms 3560 KB
1
2