Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"YT201758501114","updateTime":1535958176000,"title":"2的幂","dislikeCnt":2,"content":"****************\n题目描述\n输入一个正整数n,输出用2的幂组合出n的方案数。\n 对于正整数7,它有6种表示方式:\n1) 1+1+1+1+1+1+1\n 2) 1+1+1+1+1+2\n 3) 1+1+1+2+2\n 4) 1+1+1+4\n 5) 1+2+2+2\n 6) 1+2+4\n输入\n一个正整数n,1\u003c\u003dn\u003c\u003d1000000\n输出\n一个正整数,代表用2的幂组合出n的方案数,由于结果可能很大,仅保留后九位数字。\n样例输入 样例输出\n7 6\n**完全背包裸题**\n#include\u003cstdio.h\u003e\nconst int mod \u003d 1e9;\nconst int maxn \u003d 1e6 + 10;\nint n,dp[maxn] \u003d {1};\nint main() {\n scanf(\"%d\",\u0026n);\n for(int i\u003d1;i\u003c\u003dn;i\u003c\u003c\u003d1)\n for(int j\u003di;j\u003c\u003dn;j++) {\n dp[j]+\u003ddp[j-i];\n if(dp[j]\u003e\u003dmod) dp[j]%\u003dmod; \n }\n printf(\"%d\\n\",dp[n]);\n return 0;\n}\n注:有规律!!!!!","threadId":34212,"likeCnt":0,"createTime":1535958176000,"isWorkbook":false,"viewCnt":2263,"openness":2,"fav":false,"id":626,"trustable":false}