{"id":512,"date":"2017-04-27T16:19:30","date_gmt":"2017-04-27T08:19:30","guid":{"rendered":"http:\/\/kylelv.com\/?p=512"},"modified":"2018-01-18T17:11:42","modified_gmt":"2018-01-18T09:11:42","slug":"bzoj-2483-pku2279-mr-youngs-picture-permutations-%e9%92%a9%e5%ad%90%e5%85%ac%e5%bc%8f","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=512","title":{"rendered":"bzoj 2483: Pku2279 Mr. Young&#8217;s Picture Permutations  &#8212; \u94a9\u5b50\u516c\u5f0f"},"content":{"rendered":"<p>&nbsp;<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fdef6ce8223\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fdef6ce8223\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.kylelv.com\/?p=512\/#2483_Pku2279_Mr_Youngs_Picture_Permutations\" title=\"2483: Pku2279 Mr. Young&#8217;s Picture Permutations\">2483: Pku2279 Mr. Young&#8217;s Picture Permutations<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=512\/#Description\" title=\"Description\">Description<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=512\/#Input\" title=\"Input\">Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=512\/#Output\" title=\"Output\">Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=512\/#Sample_Input\" title=\"Sample Input\">Sample Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=512\/#Sample_Output\" title=\"Sample Output\">Sample Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=512\/#HINT\" title=\"HINT\">HINT<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"2483_Pku2279_Mr_Youngs_Picture_Permutations\"><\/span>2483: Pku2279 Mr. Young&#8217;s Picture Permutations<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p style=\"text-align: center;\"><span class=\"green\">Time Limit:\u00a01 Sec\u00a0\u00a0Memory Limit:\u00a0128 MB<\/span><\/p>\n<h2><span class=\"ez-toc-section\" id=\"Description\"><\/span>Description<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div class=\"plm\"><\/div>\n<div class=\"ptx\" lang=\"en-US\">\n<p>Mr. Young wishes to take a picture of his class. The students will stand in rows with each row no longer than the row behind it and the left ends of the rows aligned. For instance, 12 students could be arranged in rows (from back to front) of 5, 3, 3 and 1 students.<\/p>\n<pre>X X X X X\r\n\r\nX X X\r\n\r\nX X X\r\n\r\nX<\/pre>\n<p>In addition, Mr. Young wants the students in each row arranged so that heights decrease from left to right. Also, student heights should decrease from the back to the front. Thinking about it, Mr. Young sees that for the 12-student example, there are at least two ways to arrange the students (with 1 as the tallest etc.):<\/p>\n<pre> 1  2  3  4  5     1  5  8 11 12\r\n\r\n 6  7  8           2  6  9\r\n\r\n 9 10 11           3  7 10\r\n\r\n12                 4<\/pre>\n<p>Mr. Young wonders how many different arrangements of the students there might be for a given arrangement of rows. He tries counting by hand starting with rows of 3, 2 and 1 and counts 16 arrangements:<\/p>\n<pre>123 123 124 124 125 125 126 126 134 134 135 135 136 136 145 146\r\n\r\n45  46  35  36  34  36  34  35  25  26  24  26  24  25  26  25\r\n\r\n6   5   6   5   6   4   5   4   6   5   6   4   5   4   3   3<\/pre>\n<p>Mr. Young sees that counting by hand is not going to be very effective for any reasonable number of students so he asks you to help out by writing a computer program to determine the number of different arrangements of students for a given set of rows.<\/p>\n<\/div>\n<p>\u6768\u5148\u751f\u8981\u7ed9\u4ed6\u7684\u5b66\u751f\u4eec\u62cd\u7167\u7247\u3002\u9996\u5148\uff0c\u7ad9\u961f\u72b6\u51b5\u662f\u786e\u5b9a\u7684\uff0c\u82e5\u7b2ci\u884c\u7ad9\u4e86a[i]\u4e2a\u4eba\uff0c\u5219\u6709a[1] \u2265 a[2] \u2265 &#8230; \u2265 a[n]\uff0c\u6240\u6709\u7684\u884c\u90fd\u662f\u9760\u5de6\u5bf9\u9f50\u7684\u3002\u5e76\u4e14\uff0c\u5728\u540c\u4e00\u884c\u548c\u540c\u4e00\u5217\u91cc\u9762\uff0c\u4ece\u5de6\u5230\u53f3\u6216\u8005\u4ece\u4e0a\u5230\u4e0b\u8eab\u9ad8\u90fd\u662f\u9012\u51cf\u7684\u3002\u73b0\u5728\u6240\u6709\u5b66\u751f\u7684\u8eab\u9ad8\u90fd\u4e0d\u76f8\u540c\uff0c\u5b66\u751f\u6570\u4e0d\u8d85\u8fc730\u4e2a\uff0c\u884c\u6570\u4e0d\u8d85\u8fc75\u3002\u4f60\u9700\u8981\u6c42\u51fa\u6240\u6709\u53ef\u80fd\u7684\u6392\u961f\u65b9\u6cd5\u7684\u603b\u6570\u3002<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Input\"><\/span>Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div class=\"ptx\" lang=\"en-US\">The input for each problem instance will consist of two lines. The first line gives the number of rows, k, as a decimal integer. The second line contains the lengths of the rows from back to front (n1, n2,&#8230;, nk) as decimal integers separated by a single space. The problem set ends with a line with a row count of 0. There will never be more than 5 rows and the total number of students, N, (sum of the row lengths) will be at most 30.<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Output\"><\/span>Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div class=\"ptx\" lang=\"en-US\">The output for each problem instance shall be the number of arrangements of the N students into the given rows so that the heights decrease along each row from left to right and along each column from back to front as a decimal integer. (Assume all heights are distinct.) The result of each problem instance should be on a separate line. The input data will be chosen so that the result will always fit in an unsigned 32 bit integer.<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Input\"><\/span>Sample Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\"><span class=\"sampledata\">1<br \/>\n30<br \/>\n5<br \/>\n1 1 1 1 1<br \/>\n3<br \/>\n3 2 1<br \/>\n4<br \/>\n5 3 3 1<br \/>\n5<br \/>\n6 5 4 3 2<br \/>\n2<br \/>\n15 15<br \/>\n0<\/span><\/span>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Output\"><\/span>Sample Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\"><span class=\"sampledata\">1<br \/>\n1<br \/>\n16<br \/>\n4158<br \/>\n141892608<br \/>\n9694845<\/span><\/span>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"HINT\"><\/span>HINT<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u5148\u4ecb\u7ecd\u4e00\u4e0b\u4ec0\u4e48\u662f\u6768\u6c0f\u77e9\u9635\uff08<a class=\" wrap external\" href=\"https:\/\/link.zhihu.com\/?target=https%3A\/\/en.wikipedia.org\/wiki\/Young_tableau\" target=\"_blank\" rel=\"nofollow noopener noreferrer\">Young tableau<\/a>\uff09\/\/\u5141\u8bb8\u6211\u8f6c\u8f7d\u4e00\u4e0b QwQ \u00a0 \u51fa\u5904\uff1a<a href=\"https:\/\/www.zhihu.com\/question\/52335435\/answer\/130097881\" target=\"_blank\" rel=\"noopener\">https:\/\/www.zhihu.com\/question\/52335435\/answer\/130097881<\/a><\/p>\n<div>\n<div>\n<p>\u6768\u6c0f\u77e9\u9635\u662f\u8fd9\u6837\u4e00\u7c7b\u5e26\u9650\u5236\u7684\u77e9\u9635\uff1a<\/p>\n<ol>\n<li>\u77e9\u9635\u91cc\u540c\u4e00\u884c\u7684\u5143\u7d20\uff0c\u5de6\u8fb9\u7684\u5143\u7d20\u5c0f\u4e8e\u53f3\u8fb9\u7684\u5143\u7d20\u3002<\/li>\n<li>\u77e9\u9635\u91cc\u540c\u4e00\u5217\u7684\u5143\u7d20\uff0c\u4e0a\u8fb9\u7684\u5143\u7d20\u5c0f\u4e8e\u4e0b\u8fb9\u7684\u5143\u7d20\u3002<\/li>\n<\/ol>\n<p>\u800c\u95ee\u9898\u4e2d\u6240\u6c42\u7684\u662f\u6392\u5217\uff0c\u53ef\u4ee5\u53cc\u5c04\u5230\u5b83\u7684\u9006\u6392\u5217\uff0c\u7edf\u8ba1\u9006\u6392\u5217\u7684\u4e2a\u6570\uff0c\u5177\u4f53\u6765\u8bf4\uff0c\u5c31\u662f\u6c42<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=%28i%2Cj%29\" alt=\"(i,j)\" \/>\u5728\u6392\u5217\u91cc\u7684\u6392\u540d\uff0c\u4ece\u800c\u8f6c\u5316\u4e3a\u5c06<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=1\" alt=\"1\" \/>\u5230<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=N\" alt=\"N\" \/>\u586b\u5145\u5230\u77e9\u9635\u4e2d\uff0c\u95ee\u6709\u591a\u5c11\u79cd\u65b9\u6cd5\u6ee1\u8db3\u6768\u6c0f\u77e9\u9635\u7684\u9650\u5236\u3002<\/p>\n<p>\u56fa\u5b9a\u77e9\u9635\u5f62\u6001\uff0c\u6c42\u6709\u591a\u5c11\u79cd\u672c\u8d28\u4e0d\u540c\u7684\u6768\u6c0f\u77e9\u9635\uff0c\u8fd9\u4e2a\u95ee\u9898\u662f\u975e\u5e38\u7ecf\u5178\u7684\uff0c\u53ef\u4ee5\u4f7f\u7528\u94a9\u5b50\u516c\u5f0f\uff08<a class=\" wrap external\" href=\"https:\/\/link.zhihu.com\/?target=https%3A\/\/en.wikipedia.org\/wiki\/Hook_length_formula\" target=\"_blank\" rel=\"nofollow noopener noreferrer\">Hook length formula<\/a>\uff09\u6c42\u89e3\u3002<br \/>\n\u5b9a\u4e49<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=h_%7B%5Clambda%7D%28i%2Cj%29\" alt=\"h_{\\lambda}(i,j)\" \/>\u8868\u793a\u77e9\u9635\u91cc\u6ee1\u8db3<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=i%3Dx%2Cj%5Cleq+y\" alt=\"i=x,j\\leq y\" \/>\u6216<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=i%5Cleq+x%2Cj%3Dy\" alt=\"i\\leq x,j=y\" \/>\u7684<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=%28x%2Cy%29\" alt=\"(x,y)\" \/>\u4f4d\u7f6e\u4e2a\u6570\uff0c\u5219\u672c\u8d28\u4e0d\u540c\u7684\u6768\u6c0f\u77e9\u9635\u4e2a\u6570\u662f<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=%5Cfrac%7BN%21%7D%7B%5Cprod_%7Bi%2Cj%7D%7Bh_%7B%5Clambda%7D%28i%2Cj%29%7D%7D\" alt=\"\\frac{N!}{\\prod_{i,j}{h_{\\lambda}(i,j)}}\" \/>\u3002<\/p>\n<p>\u90a3\u4e48\u5bf9\u4e8e\u8fd9\u4e2a\u95ee\u9898\uff0c\u6ee1\u8db3\u6761\u4ef6\u7684\u6392\u5217\u6570\u5c31\u662f<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=%5Cfrac%7BN%21%7D%7B%5Cprod_%7Bi+%3D+0%7D%5E%7Bm+-+1%7D%7B%5Cfrac%7B%28n%2Bi%29%21%7D%7Bi%21%7D%7D%7D\" alt=\"\\frac{N!}{\\prod_{i = 0}^{m - 1}{\\frac{(n+i)!}{i!}}}\" \/>\uff0c\u662f<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%28%5Cexp%28N%5Clog+N%29%29\" alt=\"O(\\exp(N\\log N))\" \/>\u7684\u3002<\/p>\n<\/div>\n<div>\n<pre class=\"lang:c++ decode:true \">#include&lt;map&gt;\r\n#include&lt;cmath&gt;\r\n#include&lt;queue&gt;\r\n#include&lt;cstdio&gt;\r\n#include&lt;cstring&gt;\r\n#include&lt;iostream&gt;\r\n#include&lt;algorithm&gt;\r\nusing namespace std;\r\n#define ll long long\r\ninline int read()\r\n{\r\n    int x=0,f=1;char ch=getchar();\r\n    while(ch&lt;'0'||ch&gt;'9'){if(ch=='-')f=-1;ch=getchar();}\r\n    while(ch&gt;='0'&amp;&amp;ch&lt;='9'){x=x*10+ch-'0';ch=getchar();}\r\n    return x*f;\r\n}\r\nint n,a[6],sum,ji[33];\r\nbool mp[33][33];\r\nll ans=1;\r\nll ksm(ll a,int b)\r\n{\r\n    ll s=1;\r\n    for(;b;b&gt;&gt;=1,a*=a) if(b&amp;1) s*=a;\r\n    return s;\r\n}\r\nint main()\r\n{\r\n    int i,j,h,k;\r\n    while(n=read())\r\n    {\r\n        ans=1;sum=0;\r\n        memset(ji,0,sizeof(ji));\r\n        memset(mp,0,sizeof(mp));\r\n        for(i=1;i&lt;=n;i++)\r\n        {\r\n            a[i]=read();sum+=a[i];\r\n            for(j=1;j&lt;=a[i];j++) mp[i][j]=1;\r\n        }\r\n        for(i=1;i&lt;=sum;i++)\r\n        {\r\n            int tp=i;\r\n            for(j=2;j&lt;=tp;j++)\r\n                while(tp%j==0) tp\/=j,ji[j]++;\r\n        }\r\n        for(i=1;i&lt;=n;i++)\r\n        {\r\n            for(j=1;j&lt;=a[i];j++)\r\n            {\r\n                h=a[i]-j;\r\n                for(k=i;k&lt;=n;k++) if(mp[k][j]) h++;\r\n                int tp=h;\r\n                for(k=2;k&lt;=tp;k++)\r\n                    while(tp%k==0) tp\/=k,ji[k]--;\r\n            }\r\n        }\r\n        for(i=2;i&lt;=30;i++) ans*=ksm((ll)i,ji[i]);\r\n        printf(\"%lld\\n\",ans);\r\n    }\r\n    return 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; 2483: Pku2279 Mr. Young&#8217;s Picture Permutat [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,7],"tags":[8,55],"class_list":["post-512","post","type-post","status-publish","format-standard","hentry","category-bzoj","category-poj","tag-8","tag-55"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/512","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=512"}],"version-history":[{"count":2,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/512\/revisions"}],"predecessor-version":[{"id":514,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/512\/revisions\/514"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}