Submission #10162

ソースコード

?
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define SIZE 1111111
char k;
int len;
char a[SIZE],a_[SIZE];
int al;
char b[SIZE],b_[SIZE];
int bl;
ll dp[SIZE][3][2];
ll plus_(ll a,ll b)
{
return (a+b)%mod;
}
//何桁目？ aとbどっちの桁がまだ一致中か 目的の桁が既に使われたか 0以外を使ったか
// 1bit目:a 2bit目:b
ll solve(int p,int u,int ok,int uzero)
{
ll res = 0;
if( p == len ) {
if( k == '0' ) if(!uzero)return 1;
return ok;
}
if( dp[p][u][ok] >= 0 ) return dp[p][u][ok];
for(int i = '0'; i <= '9'; i++) {
int nuzero = uzero|(i!='0');
if( !u ) res = plus_(res,solve(p+1,u,ok|(nuzero&&i==k),nuzero));
else {
int nu = u;
if( (u&1) && i < a[p] ) continue;
if( (u&2) && i > b[p] ) continue;
if( i != a[p] ) nu = nu&~1;
if( i != b[p] ) nu = nu&~2;
res = plus_(res,solve(p+1,nu,ok|(nuzero&&i==k),nuzero));
}
}
return dp[p][u][ok] = res;
}
ll solve()
{
ll res = 0;
for(int i = '0'; i <= '9'; i++) {
int u = 3;
if( i < a[0] ) continue;
if( i > b[0] ) continue;
if( i != a[0] ) u = u&~(1<<0);
if( i != b[0] ) u = u&~(1<<1);
res = plus_(res,solve(1,u,i!='0'&&i==k,i!='0'));
}
return res;
}
int main(void)
{
scanf("%s%s %c",a_,b_,&k);
memset(dp,-1,sizeof(dp));
al = bl = 0;
while(a_[al])al++; while(b_[bl])bl++;
len = max(al, bl);
for(int i = 0; i < len; i++) {
if(i-(len-al) >= 0) a[i] = a_[i-(len-al)]; else a[i] = '0';
if(i-(len-bl) >= 0) b[i] = b_[i-(len-bl)]; else b[i] = '0';
}
ll res = solve();
printf("%lld\n",res);
return 0;
}

ステータス

項目 データ
問題 0565 - 桁
ユーザー名 💩
投稿日時 2016-11-09 13:59:19
言語 C++11
状態 Accepted
得点 2
ソースコード長 1817 Byte
最大実行時間 55 ms
最大メモリ使用量 65528 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00.in AC 55 ms 65248 KB
2
00large.in AC 46 ms 65232 KB
2
00sample.in AC 28 ms 55752 KB
2
00small.in AC 29 ms 55740 KB
1
2
01.in AC 51 ms 65328 KB
2
01large.in AC 44 ms 65316 KB
2
01sample.in AC 24 ms 55704 KB
2
01small.in AC 30 ms 55692 KB
1
2
02.in AC 49 ms 65156 KB
2
02large.in AC 47 ms 65268 KB
2
02sample.in AC 29 ms 55912 KB
2
02small.in AC 24 ms 55896 KB
1
2
03.in AC 49 ms 65228 KB
2
03large.in AC 45 ms 65344 KB
2
03small.in AC 27 ms 55860 KB
1
2
04.in AC 48 ms 65320 KB
2
04large.in AC 47 ms 65312 KB
2
04small.in AC 30 ms 55824 KB
1
2
05.in AC 50 ms 65416 KB
2
05large.in AC 44 ms 65404 KB
2
05small.in AC 30 ms 55796 KB
1
2
06.in AC 50 ms 65260 KB
2
06large.in AC 47 ms 65380 KB
2
06small.in AC 25 ms 55768 KB
1
2
07.in AC 46 ms 65360 KB
2
07large.in AC 43 ms 65348 KB
2
07small.in AC 32 ms 55860 KB
1
2
08.in AC 49 ms 65320 KB
2
08large.in AC 43 ms 65312 KB
2
08small.in AC 31 ms 55828 KB
1
2
09.in AC 45 ms 65412 KB
2
09large.in AC 44 ms 65528 KB
2
09small.in AC 27 ms 55908 KB
1
2