{"id":348,"date":"2018-11-05T22:02:03","date_gmt":"2018-11-05T14:02:03","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=348"},"modified":"2018-11-05T22:02:59","modified_gmt":"2018-11-05T14:02:59","slug":"lp2822-noip2016-%e7%bb%84%e5%90%88%e6%95%b0%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/11\/05\/lp2822-noip2016-%e7%bb%84%e5%90%88%e6%95%b0%e9%97%ae%e9%a2%98\/","title":{"rendered":"lp2822 NOIP2016 \u7ec4\u5408\u6570\u95ee\u9898"},"content":{"rendered":"

\u57fa\u7840\u6570\u8bba\u9898\u3002
\n\u9996\u5148\u6211\u4eec\u77e5\u9053\uff0c\u4efb\u4f55\u6570\u7684\u9006\u5143\u6a21k\uff0c\u90fd\u4e0d\u53ef\u80fd\u7b49\u4e8e\u96f6\u3002
\n\u6545\u800c\u6211\u4eec\u4e0d\u5fc5\u8003\u8651k\u662f\u5426\u662f\u8d28\u6570\u3002
\n\u7136\u540e\u6211\u4eec\u8003\u8651\u5148\u9884\u5904\u7406\u51fa\u54ea\u4e9b\\(n,m\\)\u6ee1\u8db3\\(C_{n}^{m}\u22610(mod\\ k)\\)
\n\u63a5\u7740\u524d\u7f00\u548c\u5373\u53ef\u3002
\n\u7531\u4e8e\\(n,m\\)\u8f83\u5c0f\uff0c\u53ef\u4ee5\u8003\u8651\u7528\u9012\u63a8\u3002<\/p>\n

#include<iostream>\r\n#include<cstdio> \r\n#include<cstring>\r\nusing namespace std;\r\nint sm[2005][2005],C[2005][2005];\r\nint n,m,k;\r\nvoid prpr(){\r\n    memset(sm,0,sizeof(sm));\r\n    C[0][0]=C[1][1]=1;\r\n    for(int i=1;i<=2000;++i){\r\n        C[i][0]=1,C[i][i]=1;\r\n    }\r\n    for(int i=2;i<=2000;++i){\r\n        for(int j=1;j<=i;++j){\r\n            C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;\r\n        }\r\n    }\r\n    for(int i=2;i<=2000;++i){\r\n        for(int j=1;j<=i;++j){\r\n            sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];\r\n            if(C[i][j]==0){\r\n                ++sm[i][j];\r\n            }\r\n        }\r\n        sm[i][i+1]=sm[i][i];\r\n    }\r\n}\r\nvoid init(){\r\n    scanf(\"%d%d\",&n,&m);\r\n    printf(\"%d\\n\",(m>n)?(sm[n][n]):(sm[n][m]));\r\n}\r\nint main(){\r\n    int T;\r\n    scanf(\"%d%d\",&T,&k);\r\n    prpr();\r\n    while(T--){\r\n        init();\r\n    }\r\n    return 0;\r\n}<\/code><\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u57fa\u7840\u6570\u8bba\u9898\u3002 \u9996\u5148\u6211\u4eec\u77e5\u9053\uff0c\u4efb\u4f55\u6570\u7684\u9006\u5143\u6a21k\uff0c\u90fd\u4e0d\u53ef\u80fd\u7b49\u4e8e\u96f6\u3002 \u6545\u800c\u6211\u4eec\u4e0d\u5fc5\u8003\u8651k\u662f\u5426\u662f\u8d28\u6570\u3002 \u7136\u540e\u6211\u4eec\u8003\u8651\u5148 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp2822 NOIP2016 \u7ec4\u5408\u6570\u95ee\u9898\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10,42,24,27,8,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/348"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=348"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/348\/revisions"}],"predecessor-version":[{"id":349,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/348\/revisions\/349"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=348"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}