Submission #10164

ソースコード

?
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[1000000][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:46:38
言語 C++11
状態 Accepted
得点 2
ソースコード長 778 Byte
最大実行時間 89 ms
最大メモリ使用量 43084 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00.in AC 84 ms 42976 KB
2
00large.in AC 59 ms 42816 KB
2
00sample.in AC 19 ms 31624 KB
2
00small.in AC 27 ms 31720 KB
1
2
01.in AC 81 ms 42824 KB
2
01large.in AC 47 ms 42928 KB
2
01sample.in AC 27 ms 31736 KB
2
01small.in AC 28 ms 31704 KB
1
2
02.in AC 85 ms 42932 KB
2
02large.in AC 52 ms 42900 KB
2
02sample.in AC 22 ms 31708 KB
2
02small.in AC 25 ms 31672 KB
1
2
03.in AC 80 ms 43032 KB
2
03large.in AC 57 ms 43000 KB
2
03small.in AC 22 ms 31812 KB
1
2
04.in AC 74 ms 43044 KB
2
04large.in AC 47 ms 42888 KB
2
04small.in AC 30 ms 31820 KB
1
2
05.in AC 81 ms 42920 KB
2
05large.in AC 53 ms 43012 KB
2
05small.in AC 30 ms 31816 KB
1
2
06.in AC 80 ms 43044 KB
2
06large.in AC 53 ms 43008 KB
2
06small.in AC 31 ms 31816 KB
1
2
07.in AC 84 ms 43048 KB
2
07large.in AC 53 ms 43016 KB
2
07small.in AC 25 ms 31832 KB
1
2
08.in AC 89 ms 43068 KB
2
08large.in AC 51 ms 43036 KB
2
08small.in AC 24 ms 31976 KB
1
2
09.in AC 85 ms 43084 KB
2
09large.in AC 48 ms 43056 KB
2
09small.in AC 24 ms 31868 KB
1
2