{"id":19,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-09-09-%e6%95%b0%e4%bd%8ddp\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-09-%e6%95%b0%e4%bd%8ddp","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-09-%e6%95%b0%e4%bd%8ddp\/","title":{"rendered":"2020-09-09 \u6570\u4f4dDP"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?id=14643<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.
Constraints
\u00b71\u2264N<10100
\u00b71\u2264K\u22643<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

Input is given from Standard Input in the following format:
N
K<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

Print the count.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n

\u3010\u6837\u4f8b1\u3011
100
1
\u3010\u6837\u4f8b2\u3011
25
2
\u3010\u6837\u4f8b3\u3011
314159
2
\u3010\u6837\u4f8b4\u3011
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n

\u3010\u6837\u4f8b1\u3011
19
\u3010\u6837\u4f8b2\u3011
14
\u3010\u6837\u4f8b3\u3011
937
\u3010\u6837\u4f8b4\u3011
117879300<\/p>\n

<\/a>\u63d0\u793a<\/h5>\n

\u6837\u4f8b1\u89e3\u91ca
The following 19 integers satisfy the condition:1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100
\u6837\u4f8b2\u89e3\u91ca
The following 14 integers satisfy the condition:11,12,13,14,15,16,17,18,19,21,22,23,24,25<\/p>\n

#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nll dp[<\/span>300<\/span>]<\/span>[<\/span>30<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nchar<\/span> a[<\/span>1005<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    ll k;<\/span>\n    scanf<\/span>(<\/span>\"%s%lld\"<\/span>,<\/span>a+<\/span>1<\/span>,<\/span>&<\/span>k)<\/span>;<\/span>\n    ll n=<\/span>strlen<\/span>(<\/span>a+<\/span>1<\/span>)<\/span>;<\/span>\n    dp[<\/span>0<\/span>]<\/span>[<\/span>0<\/span>]<\/span>=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>200<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        dp[<\/span>i]<\/span>[<\/span>0<\/span>]<\/span>=<\/span>dp[<\/span>i-<\/span>1<\/span>]<\/span>[<\/span>0<\/span>]<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>20<\/span>;<\/span>j++<\/span>)<\/span>\n            dp[<\/span>i]<\/span>[<\/span>j]<\/span>=<\/span>dp[<\/span>i-<\/span>1<\/span>]<\/span>[<\/span>j]<\/span>+<\/span>9<\/span>*<\/span>dp[<\/span>i-<\/span>1<\/span>]<\/span>[<\/span>j-<\/span>1<\/span>]<\/span>;<\/span>\n    }<\/span>\n    ll sum=<\/span>0<\/span>,<\/span>cnt=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>><\/span>'0'<\/span>&&<\/span>k-<\/span>cnt>=<\/span>0<\/span>)<\/span>\n            sum+<\/span>=<\/span>dp[<\/span>n-<\/span>i]<\/span>[<\/span>k-<\/span>cnt]<\/span>;<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>><\/span>'1'<\/span>&&<\/span>k-<\/span>1<\/span>-<\/span>cnt>=<\/span>0<\/span>)<\/span>\n            sum+<\/span>=<\/span>(<\/span>a[<\/span>i]<\/span>-<\/span>'0'<\/span>-<\/span>1<\/span>)<\/span>*<\/span>dp[<\/span>n-<\/span>i]<\/span>[<\/span>k-<\/span>1<\/span>-<\/span>cnt]<\/span>;<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>><\/span>'0'<\/span>)<\/span>\n            cnt++<\/span>;<\/span>\n    }<\/span>\n    if<\/span>(<\/span>cnt==<\/span>k)<\/span>\n        sum++<\/span>;<\/span>\n    cout<<<\/span>sum<<<\/span>endl;<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-19","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/19","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=19"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/19\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=19"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=19"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=19"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}