{"id":263,"date":"2010-05-29T10:49:00","date_gmt":"2010-05-29T02:49:00","guid":{"rendered":"http:\/\/localhost\/?p=263"},"modified":"2010-05-29T10:49:00","modified_gmt":"2010-05-29T02:49:00","slug":"hnoi2008cards","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=263","title":{"rendered":"[HNOI2008]Cards"},"content":{"rendered":"\n<p>[HNOI2008]Cards<\/p>\n<p>Time Limit:10000MS&#160; Memory Limit:165536K<br \/>Total Submit:114 Accepted:65 <br \/>Case Time Limit:1000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> \u5c0f\u6625\u73b0\u5728\u5f88\u6e05\u95f2,\u9762\u5bf9\u4e66\u684c\u4e0a\u7684N\u5f20\u724c,\u4ed6\u51b3\u5b9a\u7ed9\u6bcf\u5f20\u67d3\u8272,\u76ee\u524d\u5c0f\u6625\u53ea\u67093\u79cd\u989c\u8272:\u7ea2\u8272,\u84dd\u8272,\u7eff\u8272.\u4ed6\u8be2\u95eeSun\u6709\u591a\u5c11\u79cd\u67d3\u8272\u65b9\u6848,Sun\u5f88\u5feb\u5c31\u7ed9\u51fa\u4e86\u7b54 \u6848.\u8fdb\u4e00\u6b65,\u5c0f\u6625\u8981\u6c42\u67d3\u51faSr\u5f20\u7ea2\u8272,Sb\u5f20\u84dd\u8272,Sg\u5f20\u7edd\u8272.\u4ed6\u53c8\u8be2\u95ee\u6709\u591a\u5c11\u79cd\u65b9\u6848,Sun\u60f3\u4e86\u4e00\u4e0b,\u53c8\u7ed9\u51fa\u4e86\u6b63\u786e\u7b54\u6848. <br \/>\u6700\u540e\u5c0f\u6625\u53d1\u660e\u4e86M\u79cd\u4e0d\u540c\u7684\u6d17\u724c\u6cd5,\u8fd9\u91cc\u4ed6\u53c8\u95eeSun\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u67d3\u8272\u65b9\u6848.\u4e24\u79cd\u67d3\u8272\u65b9\u6cd5\u76f8\u540c\u5f53\u4e14\u4ec5\u5f53\u5176\u4e2d\u4e00\u79cd\u53ef\u4ee5\u901a\u8fc7\u4efb\u610f\u7684\u6d17\u724c\u6cd5(\u5373\u53ef\u4ee5\u4f7f\u7528 \u591a\u79cd\u6d17\u724c\u6cd5,\u800c\u6bcf\u79cd\u65b9\u6cd5\u53ef\u4ee5\u4f7f\u7528\u591a\u6b21)\u6d17\u6210\u53e6\u4e00\u79cd.Sun\u53d1\u73b0\u8fd9\u4e2a\u95ee\u9898\u6709\u70b9\u96be\u5ea6,\u51b3\u5b9a\u4ea4\u7ed9\u4f60,\u7b54\u6848\u53ef\u80fd\u5f88\u5927,\u53ea\u8981\u6c42\u51fa\u7b54\u6848\u9664\u4ee5P\u7684\u4f59\u6570(P\u4e3a\u8d28\u6570). <\/p>\n<p>\u7b2c\u4e00\u884c\u8f93\u5165\u4e94\u4e2a\u6574\u6570:Sr,Sb,Sg,M,P(M&lt;=60,M+1<\/p>\n<p>&lt;100). <br \/>N=Sr+Sb+Sg.\u63a5\u4e0b\u6765M\u884c,\u6bcf\u884c\u63cf\u8ff0\u4e00\u79cd\u6d17\u724c\u6cd5,\u6bcf\u884c\u6709N\u4e2a\u7528\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570X1X2&#8230;Xn. <br \/>\u6070\u4e3a1\u5230N\u7684\u4e00\u4e2a\u6392\u5217,\u8868\u793a\u4f7f\u7528\u8fd9\u79cd\u6d17\u724c\u6cd5,\u7b2cI\u4f4d\u53d8\u6210\u539f\u6765\u7684Xi\u4f4d\u7684\u724c. <br \/>\u8f93\u5165\u6570\u636e\u4fdd\u8bc1\u4efb\u610f\u591a\u6b21\u6d17\u724c\u90fd\u53ef\u4ee5\u7528M\u79cd\u6d17\u724c\u6cd5\u4e2d\u7684\u4e00\u79cd\u4ee3\u66ff,\u4e14\u5bf9\u6bcf\u79cd\u6d17\u724c\u6cd5,\u90fd\u5b58\u5728\u4e00\u79cd\u6d17\u724c\u6cd5\u4f7f\u5f97\u80fd\u56de\u5230 <br \/>\u539f\u72b6\u6001. <br \/>20%\u7684\u6570\u636e\u4fdd\u8bc1Sr+Sb+Sg&lt;=20 <br \/>100%\u7684\u6570\u636e\u4fdd\u8bc1Max(Sr,Sb,Sg)&lt;=20<\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u7b2c\u4e00\u884c\u8f93\u5165\u4e94\u4e2a\u6574\u6570:Sr,Sb,Sg,M,P(M&lt;=60,M+1<\/p>\n<p>&lt;100).N=Sr+Sb+Sg. <br \/>\u63a5\u4e0b\u6765M\u884c,\u6bcf\u884c\u63cf\u8ff0\u4e00\u79cd\u6d17\u724c\u6cd5,\u6bcf\u884c\u6709N\u4e2a\u7528\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570X1X2&#8230;Xn. <br \/>\u6070\u4e3a1\u5230N\u7684\u4e00\u4e2a\u6392\u5217,\u8868\u793a\u4f7f\u7528\u8fd9\u79cd\u6d17\u724c\u6cd5,\u7b2cI\u4f4d\u53d8\u6210\u539f\u6765\u7684Xi\u4f4d\u7684\u724c. <br \/>\u8f93\u5165\u6570\u636e\u4fdd\u8bc1\u4efb\u610f\u591a\u6b21\u6d17\u724c\u90fd\u53ef\u4ee5\u7528M\u79cd\u6d17\u724c\u6cd5\u4e2d\u7684\u4e00\u79cd\u4ee3\u66ff,\u4e14\u5bf9\u6bcf\u79cd\u6d17\u724c\u6cd5 <br \/>\u90fd\u5b58\u5728\u4e00\u79cd\u6d17\u724c\u6cd5\u4f7f\u5f97\u80fd\u56de\u5230\u539f\u72b6\u6001. <br \/>20%\u7684\u6570\u636e\u4fdd\u8bc1Sr+Sb+Sg&lt;=20 <br \/>100%\u7684\u6570\u636e\u4fdd\u8bc1Max(Sr,Sb,Sg)&lt;=20<\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u4e0d\u540c\u67d3\u6cd5\u9664\u4ee5P\u7684\u4f59\u6570 <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>1 1 1 2 7<br \/>2 3 1<br \/>3 1 2<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>2<\/p>\n<p><strong>Hint <\/strong><\/p>\n<p> \u67092 \u79cd\u672c\u8d28\u4e0a\u4e0d\u540c\u7684\u67d3\u8272\u6cd5RGB \u548cRBG\uff0c\u4f7f\u7528\u6d17\u724c\u6cd5231 \u4e00\u6b21\u53ef\u5f97GBR \u548cBGR\uff0c\u4f7f\u7528\u6d17\u724c\u6cd5312 \u4e00\u6b21  <br \/>\u53ef\u5f97BRG \u548cGRB\u3002 <\/p>\n<p><strong>Source<br \/>\u6628\u5929\u5f88\u7d2f\u554a\uff0c\u505a\u4e86\u8fd9\u9898\u5dee\u4e0d\u591a\u5c31\u7761\u4e86\u3002\u3002\u4eca\u5929\u624d\u5199\u8fd9\u4e2a\uff0c\u8fd9\u9898\u5c31\u662fPolya\u8ba1\u6570\u6cd5\u7684\u6269\u5c55\u5e94\u7528\u4e86\u3002<br \/>\u672c\u8d28\u4e0a\u4e0a\u662f\u5bf9\u6bcf\u4e2a\u7f6e\u6362\u7684\u4e0d\u52a8\u70b9\u6570\u91cf\u6c42\u51fa\u5e73\u5747\u503c\uff0c\u4e0d\u52a8\u70b9\u6570\u91cf\u7531\u4e8e\u9700\u8981\u6ee1\u8db3\u989c\u8272\u7684\u8981\u6c42\u53ea\u80fd\u7528Dp\u6765\u641e\uff0c\u540c\u65f6\u6c42\u51fa\u5e73\u5747\u503c\u9700\u8981\u9664\u6cd5\uff0c\u5e78\u597dP\u662f\u7d20\u6570\uff0c\u6240\u4ee5\u76f4\u63a5\u4e58\u4ee5\u62df\u5143\u5c31\u53ef\u4ee5\u4e86\u3002\u3002<br \/><\/strong><\/p>\n<p>#include &lt;vector&gt;<br \/>#include &lt;algorithm&gt;<br \/>#include &lt;utility&gt;<br \/>#include &lt;iostream&gt;<br \/>#include &lt;cstdio&gt;<br \/>#include &lt;cmath&gt;<br \/>#include &lt;cstdlib&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>#define pb push_back<br \/>const int inf=~0U&gt;&gt;1,maxn=60;<br \/>typedef long long ll;<br \/>using namespace std;<br \/>int a,b,c,m,p,n;ll ret;<br \/>int M[maxn];<br \/>void Plus(int&amp;a,int b)<br \/>{<br \/>    a+=b;if(a&gt;=p)a-=p;<br \/>}<br \/>int Cal(int A[maxn])<br \/>{<br \/>    static int B[maxn],s;<br \/>    static bool V[maxn];<br \/>    static int Dp[2][maxn][maxn];<br \/>    s=0;memset(V,0,sizeof(V));<br \/>    rep(i,n)if(!V[i])<br \/>    {<br \/>        int t=0,x=i;<br \/>        while(!V[x])V[x]=true,x=A[x],t++;<br \/>        B[s++]=t;<br \/>    }<br \/>    int now=0,next=1;<br \/>    memset(Dp,0,sizeof(Dp));Dp[next][0][0]=1;<br \/>    rep(o,s)<br \/>    {<br \/>        swap(now,next);memset(Dp[next],0,sizeof(Dp[next]));<br \/>        int t=B[o],tmp;<br \/>        rep(i,a+1)rep(j,b+1)if(tmp=Dp[now][i][j])<br \/>        {<br \/>            Plus(Dp[next][i+t][j],tmp);<br \/>            Plus(Dp[next][i][j+t],tmp);<br \/>            Plus(Dp[next][i][j],tmp);<br \/>        }<br \/>    }<br \/>    return Dp[next][a][b];<br \/>}<br \/>int pow_mod(int a,int b)<br \/>{<br \/>    if(b==1)return a;<br \/>    ll tmp=pow_mod(a,b\/2);tmp*=tmp;tmp%=p;<br \/>    if(b&amp;1)tmp*=a,tmp%=p;<br \/>    return tmp;<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    cin&gt;&gt;a&gt;&gt;b&gt;&gt;c&gt;&gt;m&gt;&gt;p;n=a+b+c;<br \/>    rep(i,m)<br \/>    {<br \/>        rep(j,n)scanf(&quot;%d&quot;,M+j),M[j]&#8211;;<br \/>        ret+=Cal(M);<br \/>    }<br \/>    rep(i,n)M[i]=i;ret+=Cal(M);<br \/>    ret=ret*pow_mod(m+1,p-2);ret%=p;<br \/>    cout&lt;&lt;ret&lt;&lt;endl;<br \/>}<\/p>\n<p><strong><br \/> <\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>[HNOI2008]Cards Time Limit:10000MS&#160; Memory Limit:165536KTotal Submit:114 Accepted:65 Case Time Limit:1000MS Description \u5c0f\u6625\u73b0\u5728\u5f88\u6e05\u95f2,\u9762\u5bf9\u4e66\u684c\u4e0a\u7684N\u5f20\u724c,\u4ed6\u51b3\u5b9a\u7ed9\u6bcf\u5f20\u67d3\u8272,\u76ee\u524d\u5c0f\u6625\u53ea\u67093\u79cd\u989c\u8272:\u7ea2\u8272,\u84dd\u8272,\u7eff\u8272.\u4ed6\u8be2\u95eeSun\u6709\u591a\u5c11\u79cd\u67d3\u8272\u65b9\u6848,Sun\u5f88\u5feb\u5c31\u7ed9\u51fa\u4e86\u7b54 \u6848.\u8fdb\u4e00\u6b65,\u5c0f\u6625\u8981\u6c42\u67d3\u51faSr\u5f20\u7ea2\u8272,Sb\u5f20\u84dd\u8272,Sg\u5f20\u7edd\u8272.\u4ed6\u53c8\u8be2\u95ee\u6709\u591a\u5c11\u79cd\u65b9\u6848,Sun\u60f3\u4e86\u4e00\u4e0b,\u53c8\u7ed9\u51fa\u4e86\u6b63\u786e\u7b54\u6848. \u6700\u540e\u5c0f\u6625\u53d1\u660e\u4e86M\u79cd\u4e0d\u540c\u7684\u6d17\u724c\u6cd5,\u8fd9\u91cc\u4ed6\u53c8\u95eeSun\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u67d3\u8272\u65b9\u6848.\u4e24\u79cd\u67d3\u8272\u65b9\u6cd5\u76f8\u540c\u5f53\u4e14\u4ec5\u5f53\u5176\u4e2d\u4e00\u79cd\u53ef\u4ee5\u901a\u8fc7\u4efb\u610f\u7684\u6d17\u724c\u6cd5(\u5373\u53ef\u4ee5\u4f7f\u7528 \u591a\u79cd\u6d17\u724c\u6cd5,\u800c\u6bcf\u79cd\u65b9\u6cd5\u53ef\u4ee5\u4f7f\u7528\u591a\u6b21)\u6d17\u6210\u53e6\u4e00\u79cd.Sun\u53d1\u73b0\u8fd9\u4e2a\u95ee\u9898\u6709\u70b9\u96be\u5ea6,\u51b3\u5b9a\u4ea4\u7ed9\u4f60,\u7b54\u6848\u53ef\u80fd\u5f88\u5927,\u53ea\u8981\u6c42\u51fa\u7b54\u6848\u9664\u4ee5P\u7684\u4f59\u6570(P\u4e3a\u8d28\u6570). \u7b2c\u4e00\u884c\u8f93\u5165\u4e94\u4e2a\u6574\u6570:Sr,Sb,Sg,M,P(M&lt;=60,M+1 &lt;100). N=Sr+Sb+Sg.\u63a5\u4e0b\u6765M\u884c,\u6bcf\u884c\u63cf\u8ff0\u4e00\u79cd\u6d17\u724c\u6cd5,\u6bcf\u884c\u6709N\u4e2a\u7528\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570X1X2&#8230;Xn. \u6070\u4e3a1\u5230N\u7684\u4e00\u4e2a\u6392\u5217,\u8868\u793a\u4f7f\u7528\u8fd9\u79cd\u6d17\u724c\u6cd5,\u7b2cI\u4f4d\u53d8\u6210\u539f\u6765\u7684Xi\u4f4d\u7684\u724c. \u8f93\u5165\u6570\u636e\u4fdd\u8bc1\u4efb\u610f\u591a\u6b21\u6d17\u724c\u90fd\u53ef\u4ee5\u7528M\u79cd\u6d17\u724c\u6cd5\u4e2d\u7684\u4e00\u79cd\u4ee3\u66ff,\u4e14\u5bf9\u6bcf\u79cd\u6d17\u724c\u6cd5,\u90fd\u5b58\u5728\u4e00\u79cd\u6d17\u724c\u6cd5\u4f7f\u5f97\u80fd\u56de\u5230 \u539f\u72b6\u6001. 20%\u7684\u6570\u636e\u4fdd\u8bc1Sr+Sb+Sg&lt;=20 100%\u7684\u6570\u636e\u4fdd\u8bc1Max(Sr,Sb,Sg)&lt;=20 Input \u7b2c\u4e00\u884c\u8f93\u5165\u4e94\u4e2a\u6574\u6570:Sr,Sb,Sg,M,P(M&lt;=60,M+1 &lt;100).N=Sr+Sb+Sg. \u63a5\u4e0b\u6765M\u884c,\u6bcf\u884c\u63cf\u8ff0\u4e00\u79cd\u6d17\u724c\u6cd5,\u6bcf\u884c\u6709N\u4e2a\u7528\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570X1X2&#8230;Xn. \u6070\u4e3a1\u5230N\u7684\u4e00\u4e2a\u6392\u5217,\u8868\u793a\u4f7f\u7528\u8fd9\u79cd\u6d17\u724c\u6cd5,\u7b2cI\u4f4d\u53d8\u6210\u539f\u6765\u7684Xi\u4f4d\u7684\u724c. \u8f93\u5165\u6570\u636e\u4fdd\u8bc1\u4efb\u610f\u591a\u6b21\u6d17\u724c\u90fd\u53ef\u4ee5\u7528M\u79cd\u6d17\u724c\u6cd5\u4e2d\u7684\u4e00\u79cd\u4ee3\u66ff,\u4e14\u5bf9\u6bcf\u79cd\u6d17\u724c\u6cd5 \u90fd\u5b58\u5728\u4e00\u79cd\u6d17\u724c\u6cd5\u4f7f\u5f97\u80fd\u56de\u5230\u539f\u72b6\u6001. 20%\u7684\u6570\u636e\u4fdd\u8bc1Sr+Sb+Sg&lt;=20 100%\u7684\u6570\u636e\u4fdd\u8bc1Max(Sr,Sb,Sg)&lt;=20 Output \u4e0d\u540c\u67d3\u6cd5\u9664\u4ee5P\u7684\u4f59\u6570 Sample Input 1 1 1 2 72 3 13 1 2 Sample Output 2 Hint \u67092 \u79cd\u672c\u8d28\u4e0a\u4e0d\u540c\u7684\u67d3\u8272\u6cd5RGB \u548cRBG\uff0c\u4f7f\u7528\u6d17\u724c\u6cd5231 \u4e00\u6b21\u53ef\u5f97GBR \u548cBGR\uff0c\u4f7f\u7528\u6d17\u724c\u6cd5312 \u4e00\u6b21 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/263"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=263"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/263\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=263"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=263"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=263"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}