Home
Problem
Status
Contest
User
Group
Forum
Register
Login
{"likeCnt":0,"createTime":"Sep 3, 2018 3:02:56 PM","author":"YT201758501114","viewCnt":1190,"id":626,"title":"2的幂","trustable":false,"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注：有规律！！！！！"}
