{"id":481,"date":"2020-05-10T22:23:57","date_gmt":"2020-05-10T14:23:57","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=481"},"modified":"2021-01-21T12:01:38","modified_gmt":"2021-01-21T04:01:38","slug":"%e6%95%b0%e4%bd%8ddp","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/05\/10\/%e6%95%b0%e4%bd%8ddp\/","title":{"rendered":"\u6570\u4f4ddp"},"content":{"rendered":"

\u6570\u4f4ddp<\/h4>\n

\u6570\u4f4ddp\u662f\u4e00\u79cd\u7528\u4e8e\u8ba1\u6570\u7684dp\uff0c\u901a\u5e38\u662f\u7528\u6765\u6c42\u5728\u6ee1\u8db3\u67d0\u79cd\u7ea6\u675f\u6761\u4ef6\u4e0b\uff0c\u6c42\u6709\u591a\u5c11\u4e2a\u6570\u6216\u8005\u5404\u4e2a\u6570\u7801\u7684\u51fa\u73b0\u6b21\u6570\u7b49\u3002\u53c8\u56e0\u4e3a\u6240\u6c42\u8303\u56f4\u4e00\u822c\u90fd\u975e\u5e38\u5927\uff0c\u6734\u7d20\u7684\u7b97\u6cd5\u4f1a\u8d85\u65f6\uff0c\u56e0\u6b64\u7528\u6570\u4f4ddp\u6765\u6c42\u89e3\u3002\u7ea6\u675f\u6761\u4ef6\u5927\u591a\u90fd\u5305\u542b\u533a\u95f4[l,r]\u4ee5\u53ca\u5176\u4ed6\u7684\u56e0\u9898\u800c\u5f02\u7684\u7ea6\u675f\u6761\u4ef6\u3002
\n\u6570\u4f4ddp\u5176\u5b9e\u4e5f\u662f\u679a\u4e3e\uff0c\u53ea\u4e0d\u8fc7\u548c\u666e\u901a\u7684\u4ece0\u5f00\u59cb\u9010\u6e10+1\u679a\u4e3e\u6570\u7684\u5927\u5c0f\u4e0d\u4e00\u6837\uff0c\u5b83\u662f\u5728\u6570\u4f4d\u4e0a\u8fdb\u884c\u679a\u4e3e\uff0c\u6bd4\u5982\u5728\u6570\u5b57n\u7684\u7b2ci\u4e2a\u4f4d\u7f6e\u4e0a\uff0c\u5728i\u524d\u9762\u7684\u4f4d\u7f6e\u4e0a\u7684\u6570\u90fd\u5df2\u7ecf\u6ee1\u8db3\u6761\u4ef6\u65f6\uff0c\u679a\u4e3e\u7b2ci\u4f4d\u53ef\u80fd\u7684\u53d6\u503c\u3002
\n\u4f60\u53ef\u80fd\u4f1a\u53d1\u73b0\uff0c\u8fd9\u6570\u4f4d\u679a\u4e3e\u4e0d\u4e5f\u7b97\u662f\u666e\u901a\u7684\u679a\u4e3e\u5417\uff1f\u8fd9\u5c31\u662f\u6570\u4f4ddp\u4f18\u5316(dp\u7684\u90a3\u79cd\u4f18\u5316)\u7684\u5730\u65b9\uff0c\u5b83\u4f18\u5316\u7684\u8bdd\u53ef\u4ee5\u628a\u5f53\u524d\u4f4d\u6570\u4e4b\u540e\u7684\u6240\u6709\u679a\u4e3e\u72b6\u6001\u76f4\u63a5\u8df3\u8fc7\u3002<\/p>\n

\u677f\u5b50<\/h5>\n

\u5728\u5e38\u7528\u7684dp\u4e2d\uff0c\u628a\u6570\u5b57n\u7528\u6570\u7ec4a\u9006\u5e8f\u8868\u793a\uff0c\u4e0b\u6807\u4ece0\u5f00\u59cb\u3002\u5bf9\u4e8e\u6570\u7ec4a\u7684\u7b2cpos\u4e2a\u4f4d\u7f6e\uff0c\u7528dp[i]\u8868\u793a\u524di-1\u4f4d\u6570\u5b57\u4e2d\uff0c\u5728\u65e0 1.\u524d\u5bfc\u96f6 2.\u5404\u4e2a\u4f4d\u6570\u7684\u679a\u4e3e\u9650\u5236 \u7b49\u7ea6\u675f\u6761\u4ef6\u4e0b\u6ee1\u8db3\u9898\u610f\u7684\u89e3\u4e3a\u591a\u5c11\u3002\u5177\u4f53\u770b\u4ee3\u7801\u3002
\n\u5bf9\u4e8e\u6bcf\u4e2a\u9898\u76ee\uff0c\u4e00\u5b9a\u8981\u641e\u6e05\u695adp[i]\u7684\u503c\uff0c\u662f\u5728\u6ee1\u8db3\u54ea\u4e9b\u6761\u4ef6\uff0c\u4e0d\u8003\u8651\u54ea\u4e9b\u6761\u4ef6\u4e0b\u89e3\u7684\u6570\u76ee\uff0c<\/strong><\/p>\n

\n

dp[i]:\u7b2ci\u4f4d\u5728\u6ca1\u6709limit\uff0cpre\u7b49\u9650\u5236\u6761\u4ef6\u4e0b\u7684\u89e3\u7684\u4e2a\u6570
\npre:\u4e0a\u4e00\u4f4d\u7684\u6709\u5173\u4fe1\u606f\uff0c\u53ef\u80fd\u4e3a\u662f\u5426\u6709\u524d\u5bfc\u96f6\uff0c\u4e5f\u53ef\u80fd\u4e3a\u5176\u5b83\u4fe1\u606f(\u6bd4\u5982\u4e0d\u898162\u91ccpre\u5c31\u662f\u4e0a\u4e00\u4f4d\u662f\u5426\u4e3a6)
\nlimit:\u5f53\u524d\u4f4d\u6570(\u5373pos\u4f4d)\u7684\u679a\u4e3e\u8303\u56f4\u662f\u5426\u53d7\u5230\u9650\u5236\uff0c\u4e0d\u53d7\u9650\u7684\u8bdd\u5c31\u662f0-9\uff1b\u53d7\u9650\u7684\u8bdd\u5c31\u662f0-a[pos]<\/p>\n<\/blockquote>\n

\u8fd9\u662f\u4e0d\u898162<\/a>\u7684\u9898\u89e3<\/p>\n

#include <iostream>\n#include <cstring>\nusing namespace std;\ntypedef long long ll;\n\nint l,r;\nint a[20];\nll dp[20][2];\nll dfs(int pos, int pre, bool limit){      \/\/\u8be5\u51fd\u6570\u7684\u529f\u80fd\uff1a\u6c42\u6ee1\u8db3\u5404\u53c2\u6570\u6240\u7ea6\u675f\u7684\u73af\u5883\u4e0b\uff0c\u6709\u591a\u5c11\u89e3\u3002\n                                           \/\/pos\u8868\u793a\u4f4d\u6570\uff0c pre\u8868\u793a\u662f\u5426\u6709\u524d\u5bfc\u96f6\n                                           \/\/limit\u8868\u793a\u5728\u5f53\u524d\u51fd\u6570\u72b6\u6001\u4e0b\uff0c\u7b2cpos\u4f4d\u6570\u7684\u679a\u4e3e\u4e0a\u9650\u662f\u5426\u53d7\u9650\n                                           \/\/\u82e5\u4e0d\u53d7\u9650\uff0c\u5219\u679a\u4e3e\u8303\u56f40-9\uff1b\u5426\u5219\u4f4da[pos].\n    if (pos==-1)    return 1;              \/\/\u5404\u4e2a\u4f4d\u6570\u90fd\u5df2\u679a\u4e3e\u5b8c\u6bd5\uff0c\u9012\u5f52\u7ec8\u6b62\u6761\u4ef6\u56e0\u9898\u800c\u5f02\u3002\n\/**\/if (!limit && dp[pos][pre]!=-1)     return dp[pos][pre];\n                                           \/\/\u524d\u9762\u8bb2\u8fc7dp[i]\u4f4d\u6ca1\u6709limit\u8fd9\u4e2a\u9650\u5236\u4e0b\u7684\u89e3(\u53ef\u80fd\u8fd8\u4f1a\u52a0\u4e0apre\u9650\u5236)\n                                           \/\/\u524d\u4e24\u884c\u662f\u4f18\u5316\uff0c\u770b\u80fd\u5426\u63d0\u524d\u7ed3\u675f\u6389\u8be5\u5c42\u9012\u5f52\n\n    \/* \u9012\u5f52\u4e3b\u4f53 *\/\n    int up = limit? a[pos]:9;              \/\/\u4e0a\u9650\n    ll ans = 0;\n    for (int i=0;i<=up;i++){\n        if (i==4)   continue;              \/\/4\u548c62\u4e3a\u7ea6\u675f\u6761\u4ef6\n        if (pre && i==2)    continue;      \/\/\u8fd9\u91cc\u7684pre\u8868\u793a\u524d\u4e00\u4f4d\u662f\u5426\u4e3a6\uff0c\u82e5\u524d\u4e00\u4f4d\u662f6\uff0c\u8fd9\u4e00\u4f4d\u5c31\u4e0d\u80fd\u4e3a2\u4e86\u3002\n        ans += dfs(pos-1, i==6, limit && i==a[pos]);\n    }\n\/**\/if (!limit) dp[pos][pre] = ans;        \/\/ans\u503c\u662f\u5426\u53ef\u4ee5\u8d4b\u7ed9dp\uff1f ****\n                                          \/\/\u5728\u6ee1\u8db3!limit\u8fd8\u53ef\u80fd\u5305\u542b(!pre)\u7b49\u6761\u4ef6\u4e0b\u624d\u80fd\u8d4b\u503c\uff0c\u8fd9\u91cc\u4e5f\u662f\u6570\u4f4ddp\u7684\u4f18\u5316\u4e4b\u5904\n    return ans;\n}\nll solve(int n){\n    memset (dp, -1, sizeof dp);\n    memset (a, 0, sizeof a);\n    int pos = 0;\n    while (n){\n        a[pos++] = n % 10;\n        n \/= 10;\n    }\n    return dfs(pos-1, 0, true);          \/\/\u4ece\u6700\u540e\u4e00\u4f4d\u5f00\u59cb\u679a\u4e3e\uff0c\u56fa\u7136\u524d\u4e00\u4f4d\u4e0d\u662f6\uff0c limit\u662ftrue\n}\nint main(){\n    while (cin >> l >> r){\n        if (!l && !r)   break;\n        cout << solve(r) - solve(l-1) << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n
\u6d1b\u8c37P2602 \u6570\u5b57\u8ba1\u6570<\/a>
\n\u8f93\u51fa\u533a\u95f4\u5185\u5404\u4e2a\u6570\u7801\u7684\u51fa\u73b0\u6b21\u6570\uff0c\u8fd9\u9053\u9898\u76ee\u597d\u50cf\u6709\u7279\u6b8a\u7684\u7b80\u5355\u505a\u6cd5\uff0c\u4f46\u6211\u8fd8\u662f\u575a\u6301\u7528\u677f\u5b50\u5199\u4e86\uff0c\uff0c\u6709\u5f88\u591a\u503c\u5f97\u6ce8\u610f\u7684\u5730\u65b9\u3002
\n\u5199\u7684\u4e0d\u662f\u5f88\u597d\uff0c\u6211\u662f\u5bf9\u6bcf\u4e2a\u6570\u7801\u4e00\u4e00\u8fdb\u884c\u64cd\u4f5c\u7684\uff0c\uff0c\u540c\u65f6\u8fd8\u8981\u5bf90\u7279\u6b8a\u5224\u522b\u3002<\/p>\n
#include <iostream>\n#include <cstring>\n#include <cmath>\nusing namespace std;\ntypedef long long ll;\nll a[200];\nll dp[200];\nll dfs(int pos, bool pre, bool limit, ll now, int digit){  \/\/pos\u4f4d\u6570\uff0cpre\u662f\u5426\u6709\u524d\u5bfc\u96f6\uff0cnow\u662f\u5728\u524d\u9762\u7684\u9012\u5f52\u4e2d\uff0c\u6570\u7801digit\u51fa\u73b0\u7684\u6b21\u6570\n    if (pos==-1)    return now;\n    if (!limit  && !pre && dp[pos]!=-1)  return now*pow(10,pos+1)+dp[pos];\n                                                \/\/\u9012\u5f52\u7ec8\u6b62\u6761\u4ef6\u4e00\u5b9a\u8981\u591a\u6ce8\u610f\u4e00\u4e0b\uff0c\u56e0\u4e3a\u6c42\u7684\u662f\u6570\u7801\u7684\u51fa\u73b0\u6b21\u6570\uff0c\u548c\u6c42\u6709\u591a\u5c11\u4e2a\u6570\u4e0d\u540c\u3002\n\n    int up = limit? a[pos]:9;\n    ll ans = 0;\n    for (int i=0;i<=up;i++){\n        int tmp = now;\n        if (digit==0){\n            tmp = (pre?(i==0 && pos==0):now+(i==digit));\n        }else   tmp = now+(i==digit);\n        ans += dfs(pos-1, pre && (i==0) && (pos!=0), limit && i==a[pos], tmp, digit);\n    }\n    if (!limit && (digit!=0 || !pre)) dp[pos] = ans;     \/\/ \u8fd9\u91cc\u548c\u524d\u4e24\u884c\u4e00\u6837\u91cd\u8981\uff01\uff01\uff01  \u56de\u60f3\u677f\u5b50\u5f00\u5934\u63d0\u9192\u7684\uff01\uff01\uff01\uff01\uff01\n    return ans;\n}\nll solve(ll n, int base, int digit){\n    if (n==0){\n        if (digit)  return 0;\n        else    return 1;\n    }\n    memset (dp, -1, sizeof dp);\n    memset (a, 0, sizeof a);\n    int pos = 0;\n    while (n){\n        a[pos++] = n % 10;\n        n \/= 10;\n    }\n    return dfs(pos-1, true, true, 0, digit);\n}\nint main(){\n    ll l,r;\n    while (cin >> l >> r){\n        for (int i=0;i<10;i++){\n            cout << solve(r, 10, i) - solve(l-1, 10, i);\n            if (i!=9)   cout << " ";\n        }\n    }\n    return 0;\n}<\/code><\/pre>\n
P4999 \u70e6\u4eba\u7684\u6570\u5b66\u4f5c\u4e1a<\/a>
\n\u8ba1\u7b97[l, r]\u5185\u6bcf\u4e2a\u6570\u7684\u6570\u4f4d\u548c\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\ntypedef long long ll;\n\nconst ll mod = 1e9+7;\nll dp[25], a[25], Pow[25];\nll dfs(int pos, bool limit, ll n){\n    if (pos==-1)    return 0;\n    if (!limit && dp[pos]!=-1)  return dp[pos];\n\n    int up = limit? a[pos]:9;\n    ll ans = 0;\n    for (int i=0; i<=up; i++){\n        if (limit && i==a[pos]) ans += (n%Pow[pos]+1)%mod*i%mod;\n        else    ans += Pow[pos]%mod*i%mod;\n        ans += dfs(pos-1, limit && i==a[pos], n);\n        ans %= mod;\n    }\n    if (!limit) dp[pos] = ans;\n    return ans;\n}\n\nll solve(ll n){\n    memset (dp, -1, sizeof dp);\n    ll tmp = n;\n    int pos = 0;\n    while (tmp){\n        a[pos++] = tmp%10;\n        tmp \/= 10;\n    }\n    return dfs(pos-1, true, n);\n}\nint main(){\n    int t;\n    ll l, r;\n    Pow[0] = 1;\n    for (int i=1; i<=18; i++)    Pow[i] = 10*Pow[i-1];\n    cin >> t;\n    while (t--){\n        cin >> l >> r;\n        cout << ((solve(r)-solve(l-1))%mod+mod)%mod << endl;\n    }\n    return 0;\n}\n\/*\n0 10000000000000\n0 1000000000000000000\n*\/<\/code><\/pre>\n
P4317 \u82b1\u795e\u7684\u6570\u8bba\u9898<\/a>
\n\u8bbesum(i)\u8868\u793ai\u7684\u4e8c\u8fdb\u5236\u8868\u793a\u4e2d1\u7684\u4e2a\u6570
\n\u8ba1\u7b97\\prod_{i=1}^{N}{sum(i)}<\/code>\uff0c\u5148\u6c42\u51fa1\u7684\u51fa\u73b0\u6b21\u6570\u4e3ax\u7684\u6570\u7684\u4e2a\u6570\uff0c\u518d\u5feb\u901f\u5e42\u6c42\u89e3\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\ntypedef long long ll;\nconst int mod = 10000007;\n\nll n;\nint a[64];\nll dp[64][64];         \/\/ dp[i][j] \u8868\u793a\u524di\u4f4d\u4e2d1\u7684\u4e2a\u6570\u4e3aj\u7684\u6570\u7684\u4e2a\u6570(\u5728\u65e0limit\u9650\u5236\u7684\u60c5\u51b5\u4e0b)\nll sum[64];\nll pow_mod(ll a, ll b){\n    if (!a) return 0;\n    ll ans = 1;\n    while (b){\n        if (b&1)    ans = ans*a%mod;\n        b >>= 1;\n        a = a*a%mod;\n    }\n    return ans;\n}\nll dfs(int pos, bool limit, int x){              \/\/1\u7684\u4e2a\u6570\u4e3ax\u7684\u6570\u7684\u4e2a\u6570\n    if (x<0)    return 0;\n    if (pos==-1)\n        return 0==x;\n    if (!limit && dp[pos][x]!=-1)   return  dp[pos][x];\n\n    int up = limit? a[pos]:1;\n    ll ans = 0;\n    for (int i=0; i<=up; i++){\n        ans += dfs(pos-1, limit && i==a[pos], x-(i==1));\n    }\n    if (!limit) dp[pos][x] = ans;\n    return ans;\n}\nll solve(){\n    ll tmp = n, ans = 1;\n    int pos = 0;\n    while (tmp){\n        a[pos++] = tmp&1;\n        tmp >>= 1;\n    }\n    memset (dp, -1, sizeof dp);\n    memset (sum, 0, sizeof sum);\n    for (int i=2; i<=pos; i++){\n        sum[i] = dfs(pos-1, true, i);\n        ans = ans*pow_mod(i, sum[i])%mod;\n    }\n    return ans;\n}\nint main(){\n    while (cin >> n){\n        cout << solve() << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6570\u4f4ddp \u6570\u4f4ddp\u662f\u4e00\u79cd\u7528\u4e8e\u8ba1\u6570\u7684dp\uff0c\u901a\u5e38\u662f\u7528\u6765\u6c42\u5728\u6ee1\u8db3\u67d0\u79cd\u7ea6\u675f\u6761\u4ef6\u4e0b\uff0c\u6c42\u6709\u591a\u5c11\u4e2a\u6570\u6216\u8005\u5404\u4e2a\u6570\u7801\u7684 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[44],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/481"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=481"}],"version-history":[{"count":14,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/481\/revisions"}],"predecessor-version":[{"id":485,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/481\/revisions\/485"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=481"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=481"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=481"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}