{"id":384,"date":"2018-08-04T15:53:15","date_gmt":"2018-08-04T15:53:15","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=384"},"modified":"2018-08-04T16:55:08","modified_gmt":"2018-08-04T16:55:08","slug":"%e7%89%9b%e5%ae%a2%e5%a4%9a%e6%a0%a1%e7%ac%ac%e5%85%ad%e5%9c%ba-problem-c-generation-i","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=384","title":{"rendered":"\u725b\u5ba2\u591a\u6821\u7b2c\u516d\u573a Problem  C  Generation I"},"content":{"rendered":"<h2>\u9898\u610f<\/h2>\n<p>\u7565<\/p>\n<h2>\u9898\u89e3<\/h2>\n<p>\u6392\u5217\u7ec4\u5408\u9898<br \/>\n\u6709$A^m_k$\u79cd\u6392\u5217\u65b9\u6cd5\uff0cn\u4e2a\u4f4d\u7f6e\u653ek\u79cd\u7403\u6709${n-1}\\choose{k-1}$\u79cd\u65b9\u6848<br \/>\n\u6240\u4ee5\u7b54\u6848\u662f<br \/>\n$\\displaystyle\\sum_{k=1}^{min(n-1,m)}A^m_k {{n-1}\\choose{k-1}}$<\/p>\n<h2>AC\u4ee3\u7801<\/h2>\n<pre><code class=\"language-cpp  line-numbers\">#include&lt;bits\/stdc++.h&gt;\n#define LL long long\n#define MAXN 1000010\n#define MOD 998244353\nusing namespace std;\n\nLL qpow(LL a,LL b)\n{\n    LL res=1;\n    while(b)\n    {\n        if(b&amp;1) res=res*a%MOD;\n        a=a*a%MOD;\n        b&gt;&gt;=1;\n    }\n    return res;\n}\n\nLL n,m;\nLL inv[MAXN];\n\nint main()\n{\n    inv[0]=inv[1]=1;\n    int T,kase=0;\n    scanf(\"%d\",&amp;T);\n    for(int i=2;i&lt;MAXN;++i) inv[i]=(MOD-MOD\/i)*inv[MOD%i]%MOD;\n    while(T--)\n    {\n        scanf(\"%lld%lld\",&amp;n,&amp;m);\n        LL ans=m%MOD,sum=m%MOD;\n        LL m1=m%MOD,n1=n%MOD;\n        for(int i=1;i&lt;n &amp;&amp; i&lt;m;++i)\n        {\n            sum=sum*(m1-i)%MOD*(n1-i)%MOD*inv[i]%MOD;\n            ans=(ans+sum)%MOD;\n        }\n        while(ans&lt;0) ans+=MOD;\n        printf(\"Case #%d: %lld\\n\",++kase,ans);\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u610f \u7565 \u9898\u89e3 \u6392\u5217\u7ec4\u5408\u9898 \u6709$A^m_k$\u79cd\u6392\u5217\u65b9\u6cd5\uff0cn\u4e2a\u4f4d\u7f6e\u653ek\u79cd\u7403\u6709${n-1}\\choose{k-1} [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,44,49,22],"tags":[],"class_list":["post-384","post","type-post","status-publish","format-standard","hentry","category-c","category-44","category-49","category-22"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-6c","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/384","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=384"}],"version-history":[{"count":5,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/384\/revisions"}],"predecessor-version":[{"id":392,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/384\/revisions\/392"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}