15011418730 LV 7 @ 2025-8-24 22:17:08

自动搬运

来自洛谷，原作者为

	Karry5307 兄弟会背叛你，女人会离开你，金钱会诱惑你，生活会刁难你，只有数学不会，不会就是不会，怎么学都不会

搬运于2025-08-24 22:17:08，当前版本为作者最后更新于2020-02-10 09:59:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面

我相信我讲的很清楚。

前言

~~国家队队爷并不会 general 情况下的做法，如果有人想出来了请联系我，并且他可以吊打国家队队爷~~

~~顺便提一句，那个题目叫做 Epic Convolution II~~

题解

$\texttt{Subtask 1(4 pts)}$

人口普查分。

我们来推式子。

f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}

现在考虑把这个东西拆成两半，于是得到

$$f_n=\sum\limits_{k=0}^{m-1}k^ng_kh_{n-k}+\sum\limits_{k=m}^{n}k^ng_kh_{n-k} $$

然后代入，由于 $g_k$ 在 $k\geq m$ 的时候为 $0$ ，所以原式化为

f_n=\sum\limits_{k=0}^{m-1}k^n

由于 $n$ 在每组询问中是不变的，所以预处理一下每个数的 $n$ 次幂即可。

$\texttt{Subtask 2(16 pts)}$

推式子。

先不考虑当 $k\lt m$ 时 $h_k=0$ 的限制，直接让 $h_k=\frac{(-1)^{k-m}}{(k-m)!}$ ，然后开始推式子。

$$f_n=\sum\limits_{k=0}^{n}k^n\frac{1}{(k+m+1)!}\frac{(-1)^{n-k-m}}{(n-k-m)!} $$

注意到 $(k+m+1)+(n-k-m)=n+1$ ，所以等式两边同时乘上 $(n+1)!$ ，可以把右边写成二项式的形式。于是我们有

$$(n+1)!f_n=\sum\limits_{k=0}^{n}k^n(-1)^{n-k-m}\binom{n+1}{k+m+1} $$

然后感觉是不是有点不知所措了？

其实，我们接下来的一步是要拆右边的二项式。（这一步需要眼力以及很多的技巧）

考虑到有这样一个式子：

$$\binom{n+1}{k+m+1}=\sum\limits_{j=0}^{n}\binom{j}{k}\binom{n-j}{m} $$

我们来证明一下。你会发现右边那个东西特别像卷积形式，所以可以用生成函数的思想。

考虑在右边乘上一个 $x^n$ 并且把它拆成 $x^j$ 与 $x^{n-j}$ 的乘积，于是等式右边变成如下式子：

$$\sum\limits_{j=0}^{n}x^j\binom{j}{k}x^{n-j}\binom{n-j}{m} $$

然后你会发现我们如果设 $F(x)=\sum\limits_{i=0}^{\infty}\binom{i}{k}x^i$ 和 $G(x)=\sum\limits_{i=0}^{\infty}\binom{i}{m}x^i$ ，那么等式右边就是两个生成函数的乘积的 $x^n$ 的系数。

幸运的是，这两个生成函数都有简单的封闭形式，这里以 $F(x)$ 为例。（其实 $F(x)$ 和 $G(x)$ 形式是一样的，知道一个就知道另一个）

考虑到当 $i\lt k$ 的时候 $x^i$ 的系数为 $0$ ，所以我们可以考虑平移一下。

我们构造 $F^\prime(x)=\sum\limits_{i=0}^{\infty}\binom{i+k}{k}x^i$，那么可以发现 $F(x)=x^kF^\prime(x)$ 。

然而 $F^\prime(x)$ 的封闭形式非常简单，是 $\frac{1}{(1-x)^{k+1}}$ 。

所以， $F(x)=\frac{x^k}{(1-x)^{k+1}}$ ，同理有 $G(x)=\frac{x^m}{(1-x)^{m+1}}$ ，于是得到 $F(x)G(x)=\frac{x^{k+m}}{(1-x)^{k+m+2}}$ 。

现在我们来求它的 $x^n$ 的系数。

根据上面的推导，我们发现 $\frac{x^{k+m}}{(1-x)^{k+m+1}}$ 中 $x^n$ 的系数很好求，而我们发现

$$\frac{x^{k+m}}{(1-x)^{k+m+2}}=\frac{x^{k+m}}{(1-x)^{k+m+1}}\frac{1}{1-x} $$

而这个 $\frac{1}{1-x}$ 相当于将系数做前缀和。（但凡是学过一点生成函数的都知道吧），所以我们的答案为

\sum\limits_{i=0}^{n}\binom{i}{k+m}

这就是个裸的上指标求和，因此答案为 $\binom{n+1}{k+m+1}$ 。

啊哈！回到正题，把我们刚刚证明的式子代入一下，可得

$$(n+1)!f_n=\sum\limits_{k=0}^{n}k^n(-1)^{n-k-m}\sum\limits_{j=0}^{n}\binom{j}{k}\binom{n-j}{m} $$

然后我们发现可以调整一下求和的上下界，所以有

$$(n+1)!f_n=\sum\limits_{k=0}^{n}\sum\limits_{j=k}^{n}k^n(-1)^{n-k-m}\binom{j}{k}\binom{n-j}{m} $$

然后交换一下求和顺序，得到

$$(n+1)!f_n=\sum\limits_{j=0}^{n}\sum\limits_{k=0}^{j}k^n(-1)^{n-k-m}\binom{j}{k}\binom{n-j}{m} $$

接着拆 $(-1)^{n-k-m}$ ，拆成 $(-1)^{j-k}$ 和 $(-1)^{n-j-m}$ ，得到（这一步需要眼力以及很多的技巧）

$$(n+1)!f_n=\sum\limits_{j=0}^{n}\sum\limits_{k=0}^{j}k^n(-1)^{j-k}(-1)^{n-j-m}\binom{j}{k}\binom{n-j}{m} $$

然后我们写的清楚点

$$(n+1)!f_n=\sum\limits_{j=0}^{n}(-1)^{n-j-m}\binom{n-j}{m}\sum\limits_{k=0}^{j}k^n(-1)^{j-k}\binom{j}{k} $$

然后发现右边那个东西是斯特林数的形式啥的，就可以化开了，所以推出来有

$$(n+1)!f_n=\sum\limits_{j=0}^{n}\begin{Bmatrix}n\\j\end{Bmatrix}\binom{n-j}{m}(-1)^{n-j-m}j! $$

接下来，右边是一个很经典的公式，证明可以看我 P5825 的题解，由于证明过程太长了，所以不写在这里。（因为后面还有好几个 $\texttt{Subtask}$ ）

所以我们得到

$$f_n=\frac{\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle}{(n+1)!} $$

考虑到当 $n\leq m$ 的时候 $f_n$ 为 $0$ ，所以它确实是正确答案。

但是，我们发现 $m$ 很小（很大的时候做不做得出还是问题），所以可以考虑另外一个很经典的公式：（P5825 题解有人证明了这个式子，证明过程跟之前的式子一样，都是数学归纳法）

$$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k=0}^{m}\binom{n+1}{k}(m+1-k)^n(-1)^k $$

然后预处理一下幂即可，时间复杂度 $O(nm+qm)$ 。

特别的是，如果你不预处理幂时间复杂度是 $O(qm\log n)$ ，如果写的不好可能不会通过。

$\texttt{Subtask 3(16 pts)}$

一些技巧性的东西。

$n$ 的范围变成了 $998244353$ 而不是 $10^5$ ，所以我们需要比较快速的来处理 $(n+1)!$ 。

由于快速阶乘算法太慢，并且模数固定，所以我们考虑分块打表，可以考虑每 $10^6$ 打一次。

然而可能会很卡常，幂也要分块打表一下。

时间复杂度 $O(m\sqrt{M}+q(m+l))$ 。（这里用 $M$ 表示模数， $l$ 表示阶乘分块打表的块长），如果幂不分块打表而是直接快速幂的话时间复杂度是 $O(q(m\log n+l))$ ，可能无法通过。

$\texttt{Subtask 4(32 pts)}$

大量的 dirty works 以及一些技巧性的东西。

首先先推式子。

$$f_n=\sum\limits_{k=0}^{n}k^n\frac{k^m}{k!}\frac{(-1)^k}{k} $$

眼尖的神仙可以发现这就是个斯特林数，所以

f_n=\begin{Bmatrix}n+m\\n\end{Bmatrix}

接下来使用二阶欧拉数进行计算。我们有以下两个恒等式：

$$\begin{Bmatrix}x\\x-n\end{Bmatrix}=\sum\limits_{k}\left\langle\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\right\rangle\binom{x+n-1-k}{2n} $$

和

$$\begin{bmatrix}x\\x-n\end{bmatrix}=\sum\limits_{k}\left\langle\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\right\rangle\binom{x+k}{2n} $$

证明可以使用数学归纳法对 $n$ 进行归纳。

然后考虑斯特林多项式，根据定义，有

$$\sigma_n(x)=\frac{\begin{bmatrix}x\\x-n\end{bmatrix}}{x(x-1)\cdots(x-n)} $$

我们知道， $\sigma_n(x)$ 的次数是 $n-1$ ，而分母的次数为 $n+1$ ，所以说， $\begin{bmatrix}x\\x-n\end{bmatrix}$ 的次数为 $2n$ 。

类似地，由于 $\binom{x+n-1-k}{2n}$ 与 $\binom{x+k}{2n}$ 次数总是相同，所以 $\begin{Bmatrix}x\\x-n\end{Bmatrix}$ 的次数也为 $2n$ ，也就是说 $\begin{Bmatrix}x+n\\x\end{Bmatrix}$ 的次数也为 $2n$ 。

于是我们可以使用一些手段算出 $x$ 很小的时候的一些值然后带进去插值就可以得到通项公式。

接下来就是手算斯特林数这种 dirty works 了，算完之后再插值就可以打表求出这些多项式了。为什么刚刚说明了多项式的次数呢，是方便你手算的。（我在这个子任务上用了一个下午）

时间复杂度 $O(qm)$ ，如果不使用秦九韶直接快速幂的话时间复杂度为 $O(qm\log n)$ ，可能无法通过。

后面 $10$ 个测试点，由于 $n$ 的范围非常大，所以边读入边取模。

$\texttt{Subtask 5(32 pts)}$

比 $\texttt{Subtask 3}$ 更难，形式更隐蔽的数学推导。

考虑先交换求和顺序

$$ans=\sum\limits_{i=0}^{m}\sum\limits_{k=0}^{m-i}\frac{(k+1)^{m+n+1-i}}{(k+1)!}\frac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!} $$

然后改变一下内层和式的上下界（也就是将原来的 $k+1$ 变成了现在的 $k$ ）

$$ans=\sum\limits_{i=0}^{m}\sum\limits_{k=1}^{m-i+1}\frac{k^{m+n+1-i}}{k!}\frac{\binom{2n+1}{i}(-1)^{m-k+1}}{(m-k+1-i)!} $$

考虑到当 $k=0$ 时里面的和式为 $0$ ，所以改一下下界。接下来拆 $(-1)^{m-k+1}$ ，拆成 $(-1)^{i}$ 和 $(-1)^{m-k+1-i}$ ，并且把与 $k$ 无关的项提出来

$$ans=\sum\limits_{i=0}^{m}\binom{2n+1}{i}(-1)^i\sum\limits_{k=0}^{m-i+1}\frac{k^{m+n+1-i}}{k!}\frac{(-1)^{m-k+1-i}}{(m-k+1-i)!} $$

发现右边是个斯特林数，于是有

$$ans=\sum\limits_{i=0}^{m}\binom{2n+1}{i}(-1)^i\begin{Bmatrix}n+m+1-i\\m+1-i\end{Bmatrix} $$

这是一个非常经典的公式，是二阶欧拉数的通项公式，证明的话可以使用数学归纳法，类似于之前提到的一样。

这个东西有个组合意义，就是多重集 $\{1,1,2,2,\cdots,n,n\}$ 的满足对于 $1\leq m\leq n$ ， $m$ 的两次出现之间的所有数都大于 $m$ 的排列个数。

$\texttt{dp}$ 一下就好了，时间复杂度 $O(n^2+q)$ 。

哎，算了，与鰰达成协议，把代码放出来吧。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51,MOD=998244353;
ll taskId; 
ll factBlock[1051]={1,373341033,45596018,834980587,623627864,428937595,442819817,499710224,833655840,83857087,295201906,788488293,671639287,849315549,597398273,813259672,732727656,244038325,122642896,310517972,160030060,483239722,683879839,712910418,384710263,433880730,844360005,513089677,101492974,959253371,957629942,678615452,34035221,56734233,524027922,31729117,102311167,330331487,8332991,832392662,545208507,594075875,318497156,859275605,300738984,767818091,864118508,878131539,316588744,812496962,213689172,584871249,980836133,54096741,417876813,363266670,335481797,730839588,393495668,435793297,760025067,811438469,720976283,650770098,586537547,117371703,566486504,749562308,708205284,932912293,939830261,983699513,206579820,301188781,593164676,770845925,247687458,41047791,266419267,937835947,506268060,6177705,936268003,166873118,443834893,328979964,470135404,954410105,117565665,832761782,39806322,478922755,394880724,821825588,468705875,512554988,232240472,876497899,356048018,895187265,808258749,575505950,68190615,939065335,552199946,694814243,385460530,529769387,640377761,916128300,440133909,362216114,826373774,502324157,457648395,385510728,904737188,78988746,454565719,623828097,686156489,713476044,63602402,570334625,681055904,222059821,477211096,343363294,833792655,461853093,741797144,74731896,930484262,268372735,941222802,677432735,474842829,700451655,400176109,697644778,390377694,790010794,360642718,505712943,946647976,339045014,715797300,251680896,70091750,40517433,12629586,850635539,110877109,571935891,695965747,634938288,69072133,155093216,749696762,963086402,544711799,724471925,334646013,574791029,722417626,377929821,743946412,988034679,405207112,18063742,104121967,638607426,607304611,751377777,35834555,313632531,18058363,656121134,40763559,562910912,495867250,48767038,210864657,659137294,715390025,865854329,324322857,388911184,286059202,636456178,421290700,832276048,726437551,526417714,252522639,386147469,674313019,274769381,226519400,272047186,117153405,712896591,486826649,119444874,338909703,18536028,41814114,245606459,140617938,250512392,57084755,157807456,261113192,40258068,194807105,325341339,884328111,896332013,880836012,737358206,202713771,785454372,399586250,485457499,640827004,546969497,749602473,159788463,159111724,218592929,675932866,314795475,811539323,246883213,696818315,759880589,4302336,353070689,477909706,559289160,79781699,878094972,840903973,367416824,973366814,848259019,462421750,667227759,897917455,81800722,956276337,942686845,420541799,417005912,272641764,941778993,217214373,192220616,267901132,50530621,652678397,354880856,164289049,781023184,105376215,315094878,607856504,733905911,457743498,992735713,35212756,231822660,276036750,734558079,424180850,433186147,308380947,18333316,12935086,351491725,655645460,535812389,521902115,67016984,48682076,64748124,489360447,361275315,786336279,805161272,468129309,645091350,887284732,913004502,358814684,281295633,328970139,395955130,164840186,820902807,761699708,246274415,592331769,913846362,866682684,600130702,903837674,529462989,90612675,526540127,533047427,110008879,674279751,801920753,645226926,676886948,752481486,474034007,457790341,166813684,287671032,188118664,244731384,404032157,269766986,423996017,182948540,356801634,737863144,652014069,206068022,504569410,919894484,593398649,963768176,882517476,702523597,949028249,128957299,171997372,50865043,20937461,690959202,581356488,369182214,993580422,193500140,540665426,365786018,743731625,144980423,979536721,773259009,617053935,247670131,843705280,30419459,985463402,261585206,237885042,111276893,488166208,137660292,720784236,244467770,26368504,792857103,666885724,670313309,905683034,259415897,512017253,826265493,111960112,633652060,918048438,516432938,386972415,996212724,610073831,444094191,72480267,665038087,11584804,301029012,723617861,113763819,778259899,937766095,535448641,593907889,783573565,673298635,599533244,655712590,173350007,868198597,169013813,585161712,697502214,573994984,285943986,675831407,3134056,965907646,401920943,665949756,236277883,612745912,813282113,892454686,901222267,624900982,927122298,686321335,84924870,927606072,506664166,353631992,165913238,566073550,816674343,864877926,171259407,908752311,874007723,803597299,613676466,880336545,282280109,128761001,58852065,474075900,434816091,364856903,149123648,388854780,314693916,423183826,419733481,888483202,238933227,336564048,757103493,100189123,855479832,51370348,403061033,496971759,831753030,251718753,272779384,683379259,488844621,881783783,659478190,445719559,740782647,546525906,985524427,548033568,333772553,331916427,752533273,730387628,93829695,655989476,930661318,334885743,466041862,428105027,888238707,232218076,769865249,730641039,616996159,231721356,326973501,426068899,722403656,742756734,663270261,364187931,350431704,671823672,633125919,226166717,386814657,237594135,451479365,546182474,119366536,465211069,605313606,728508871,249619035,663053607,900453742,48293872,229958401,62402409,69570431,71921532,960467929,537087913,514588945,513856225,415497414,286592050,645469437,102052166,163298189,873938719,617583886,986843080,962390239,580971332,665147020,88900164,89866970,826426395,616059995,443012312,659160562,229855967,687413213,59809521,398599610,325666688,154765991,159186619,210830877,386454418,84493735,974220646,820097297,2191828,481459931,729073424,551556379,926316039,151357011,808637654,218058015,786112034,850407126,84202800,94214098,30019651,121701603,176055335,865461951,553631971,286620803,984061713,888573766,302767023,977070668,110954576,83922475,51568171,60949367,19533020,510592752,615419476,341370469,912573425,286207526,206707897,384156962,414163604,193301813,749570167,366933789,11470970,600191572,391667731,328736286,30645366,215162519,604947226,236199953,718439098,411423177,803407599,632441623,766760224,263006576,757681534,61082578,681666415,947466395,12206799,659767098,933746852,978860867,59215985,161179205,439197472,259779111,511621808,145770512,882749888,943124465,872053396,631078482,166861622,743415395,772287179,602427948,924112080,385643091,794973480,883782693,869723371,805963889,313106351,262132854,400034567,488248149,265769800,791715397,408753255,468381897,415812467,172922144,64404368,281500398,512318142,288791777,955559118,242484726,536413695,205340854,707803527,576699812,218525078,875554190,46283078,833841915,763148293,807722138,788080170,556901372,150896699,253151120,97856807,918256774,771557187,582547026,472709375,911615063,743371401,641382840,446540967,184639537,157247760,775930891,939702814,499082462,19536133,548753627,593243221,563850263,185475971,687419227,396799323,657976136,864535682,433009242,860830935,33107339,517661450,467651311,812398757,202133852,431839017,709549400,99643620,773282878,290471030,61134552,129206504,929147251,837008968,422332597,353775281,469563025,62265336,835064501,851685235,21197005,264793769,326416680,118842991,84257200,763248924,687559609,150907932,401832452,242726978,766752066,959173604,390269102,992293822,744816299,476631694,177284763,702429415,374065901,169855231,629007616,719169602,564737074,475119050,714502830,40993711,820235888,749063595,239329111,612759169,18591377,419142436,442202439,941600951,158013406,637073231,471564060,447222237,701248503,599797734,577221870,69656699,51052704,6544303,10958310,554955500,943192237,192526269,897983911,961628039,240232720,627280533,710239542,70255649,261743865,228474833,776408079,304180483,63607040,953297493,758058902,395529997,156010331,825833840,539880795,234683685,52626619,751843490,116909119,62806842,574857555,353417551,40061330,822203768,681051568,490913702,9322961,766631257,124794668,37844313,163524507,729108319,490867505,47035168,682765157,53842115,817965276,757179922,339238384,909741023,150530547,158444563,140949492,993302799,551621442,137578883,475122706,443869843,605400098,689361523,769596520,801661499,474900284,586624857,349960501,134084537,650564083,877097974,379857427,887890124,159436401,133274277,986182139,729720334,568925901,459461496,499309445,493171177,460958750,380694152,168836226,840160881,141116880,225064950,109618190,842341383,85305729,759273275,97369807,669317759,766247510,829017039,550323884,261274540,918239352,29606025,870793828,293683814,378510746,367270918,481292028,813097823,798448487,230791733,899305835,504040630,162510533,479367951,275282274,806951470,462774647,56473153,184659008,905122161,664034750,109726629,59372704,325795100,486860143,843736533,924723613,880348000,801252478,616515290,776142608,284803450,583439582,274826676,6018349,377403437,244041569,527081707,544763288,708818585,354033051,904309832,589922898,673933870,682858433,945260111,899893421,515264973,911685911,9527148,239480646,524126897,48259065,578214879,118677219,786127243,869205770,923276513,937928886,802186160,12198440,638784295,34200904,758925811,185027790,80918046,120604699,610456697,573601211,208296321,49743354,653691911,490750754,674335312,887877110,875880304,308360096,414636410,886100267,8525751,636257427,558338775,500159951,696213291,97268896,364983542,937928436,641582714,586211304,345265657,994704486,443549763,207259440,302122082,166055224,623250998,239642551,476337075,283167364,211328914,68064804,950202136,187552679,18938709,646784245,598764068,538505481,610424991,864445053,390248689,278395191,686098470,935957187,868529577,329970687,804930040,84992079,474569269,810762228,573258936,756464212,155080225,286966169,283614605,19283401,24257676,871831819,612689791,846988741,617120754,971716517,979541482,297910784,991087897,783825907,214821357,689498189,405026419,946731704,609346370,707669156,457703127,957341187,980735523,649367684,791011898,82098966,234729712,105002711,130614285,291032164,193188049,363211260,58108651,100756444,954947696,346032213,863300806,36876722,622610957,289232396,667938985,734886266,395881057,417188702,183092975,887586469,83334648,797819763,100176902,781587414,841864935,371674670,18247584};
inline ll read()
{
    register ll num=0;
    register char ch=getchar();
    while(!isdigit(ch))
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num;
}
inline ll readm()
{
    register li num=0;
    register char ch=getchar();
    while(!isdigit(ch))
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=((num<<3)+(num<<1)+(ch-'0'))%MOD;
        ch=getchar();
    }
    return num;
}   
inline ll qpow(ll base,ll exponent)
{
    ll res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=(li)res*base%MOD;
        }
        base=(li)base*base%MOD,exponent>>=1;
    }
    return res;
}
inline ll calcFact(ll x)
{
	ll res=factBlock[x/1000000];
	for(register int i=x/1000000*1000000+1;i<=x;i++)
	{
		res=(li)res*i%MOD;
	}
	return res;
}
namespace Subtask1{
	ll p,qcnt,x;
	ll pw[MAXN];
	inline void main()
	{
		p=read()-1,qcnt=read(); 
		for(register int i=1;i<=p;i++)
		{
			pw[i]=(pw[i-1]+qpow(i,p+1))%MOD;
		}
		for(register int i=0;i<qcnt;i++)
		{
			printf("%d\n",pw[read()-1]);
		}
	}
} 
namespace Subtask2{
	ll n,m,qcnt,numer,cur,hi,lo;
	li res; 
	ll block[22][32768],pw[22][32768],fact[MAXN],finv[MAXN];	
	inline void setup(ll cnt)
	{
		fact[0]=finv[0]=1;
		block[1][1]=1;
		block[2][1]=167578608;
		block[3][1]=192671909;
        block[4][1]=683753077;
        block[5][1]=21763235;
        block[6][1]=791422997;
        block[7][1]=326153078;
        block[8][1]=883105292;
        block[9][1]=84695472;
        block[10][1]=823499382;
        block[11][1]=659299615;
        block[12][1]=359937775;
        block[13][1]=647360147;
        block[14][1]=699980812;
        block[15][1]=695403701;
        block[16][1]=918327899;
        block[17][1]=48786078;
        block[18][1]=285585793;
        block[19][1]=698289863;
        block[20][1]=63206045;
        block[21][1]=995343487;
		for(register int i=1;i<cnt;i++)
		{
			fact[i]=(li)fact[i-1]*i%MOD;
		}
		for(register int i=1;i<=21;i++)
		{
			pw[i][0]=block[i][0]=1,pw[i][1]=i;
			for(register int j=1;j<32768;j++)
			{
				pw[i][j]=(li)pw[i][j-1]*i%MOD;
				block[i][j]=(li)block[i][j-1]*block[i][1]%MOD;
			}
		} 
		finv[cnt-1]=qpow(fact[cnt-1],MOD-2);
		for(register int i=cnt-2;i;i--)
		{
			finv[i]=(li)finv[i+1]*(i+1)%MOD;
		}
	}
	inline void solve()
	{
		if(!m)
		{
			return (void)(puts("1"));	
		}	
		numer=1,res=0,hi=n>>15,lo=n&32767;
		for(register int i=m+1,sgn=1,j=n+1;i;i--,sgn^=1,j--)
		{
			cur=(li)block[i][hi]*pw[i][lo]%MOD*numer%MOD*finv[m+1-i]%MOD;
			res=sgn?res+cur:res-cur+MOD;
			numer=(li)numer*j%MOD;
		}
		printf("%d\n",res%MOD*finv[n+1]%MOD);
	}
	inline void main()
	{
		setup(200011),qcnt=read();
		for(register int i=0;i<qcnt;i++)
		{
			n=read(),m=read(),solve();
		}
	}
}
namespace Subtask3{
	ll qcnt,n,m,hi,lo,numer,res,cur;
	ll block[22][32768],pw[22][32768],finv[22];
	inline void setup()
	{
		block[1][1]=1;
		block[2][1]=167578608;
		block[3][1]=192671909;
        block[4][1]=683753077;
        block[5][1]=21763235;
        block[6][1]=791422997;
        block[7][1]=326153078;
        block[8][1]=883105292;
        block[9][1]=84695472;
        block[10][1]=823499382;
        block[11][1]=659299615;
        block[12][1]=359937775;
        block[13][1]=647360147;
        block[14][1]=699980812;
        block[15][1]=695403701;
        block[16][1]=918327899;
        block[17][1]=48786078;
        block[18][1]=285585793;
        block[19][1]=698289863;
        block[20][1]=63206045;
        block[21][1]=995343487;
        finv[0]=finv[1]=1;
        finv[2]=499122177;
        finv[3]=166374059;
        finv[4]=291154603;
        finv[5]=856826403;
        finv[6]=641926577;
        finv[7]=376916469;
        finv[8]=421456191;
        finv[9]=712324701;
        finv[10]=370705776;
        finv[11]=305948985;
        finv[12]=275056837;
        finv[13]=405098354;
        finv[14]=314148269;
        finv[15]=154042465;
        finv[16]=945481735;
        finv[17]=407938109;
        finv[18]=632701444;
        finv[19]=33300076;
        finv[20]=400962745;
        finv[21]=637054254;
		for(register int i=1;i<=21;i++)
		{
			pw[i][0]=block[i][0]=1,pw[i][1]=i;
			for(register int j=1;j<32768;j++)
			{
				pw[i][j]=(li)pw[i][j-1]*i%MOD;
				block[i][j]=(li)block[i][j-1]*block[i][1]%MOD;
			}
		} 
	}
	inline void solve()
	{
		if(!m)
		{
			return (void)(puts("1"));	
		}	
		numer=1,res=0,hi=n>>15,lo=n&32767;
		for(register int i=m+1,sgn=1,j=n+1;i;i--,sgn^=1,j--)
		{
			cur=(li)block[i][hi]*pw[i][lo]%MOD*numer%MOD*finv[m+1-i]%MOD;
			res=sgn?(res+cur)%MOD:(res-cur+MOD)%MOD;
			numer=(li)numer*j%MOD;
		}
		printf("%d\n",(li)res*qpow(calcFact(n+1),MOD-2)%MOD);
	}
	inline void main()
	{
		setup(),qcnt=read();
		for(register int i=0;i<qcnt;i++)
		{
			n=read(),m=read(),solve();
		}
	}
}
namespace Subtask4{
	ll qcnt,n,m,res,cur;
	ll poly[100][100]={
		{1},
		{0,499122177,499122177},
		{0,582309206,623902721,915057324,873463809},
		{0,0,873463809,977447596,977447596,519918934,644699478},
		{0,141417950,107449913,842268673,94451940,544875043,965316154,967049217,330148523},
		{0,0,353544875,838455934,703623624,535949768,653451447,349558830,851800520,771646351,931434770},
		{0,550618909,178158888,58789352,129719774,797050168,796364164,791624030,488052236,941404697,659322198,354368080,243993623},
		{0,0,429799652,399743386,554801643,742853433,722665655,404016728,60088290,522271464,226257407,315863991,413266952,110861881,88731284},
		{0,70708975,419637300,526847060,645516780,37819976,686120930,268400327,256931840,479065066,996185375,206740503,38492104,987371789,694986290,916901540,754228970},
		{0,0,817312564,426355808,1832508,826402119,209769896,439803051,551557285,364677809,974827794,179093010,86072836,94912195,751433324,437960094,280979498,724651150,818313884}
	};
	inline void solve()
	{
		n=readm(),m=read(),res=0,cur=1;
		for(register int i=0;i<=(m<<1);i++)
		{
			res=(res+(li)poly[m][i]*cur%MOD)%MOD,cur=(li)cur*n%MOD;
		}
		printf("%d\n",res);
	}
	inline void main()
	{
		qcnt=read();
		for(register int i=0;i<qcnt;i++)
		{
			solve();
		}
	}
}
namespace Subtask5{
	ll qcnt,n,m;
	ll dp[2051][2051];
	inline void main()
	{
		dp[0][0]=1;
		for(register int i=1;i<=2000;i++)
		{
			dp[i][0]=1;
			for(register int j=1;j<=i;j++)
			{
				dp[i][j]=(li)(j+1)*dp[i-1][j]%MOD;
				dp[i][j]=(dp[i][j]+(li)((i<<1)-1-j)*dp[i-1][j-1]%MOD)%MOD;
			}
		}
		qcnt=read();
		for(register int i=0;i<qcnt;i++)
		{
			n=read(),m=read(),printf("%d\n",dp[n][m]);
		}
	}
}
int main()
{
	taskId=read();
	if(taskId==1)
	{
		Subtask1::main();
	}
	if(taskId==2)
	{
		Subtask2::main();
	}
	if(taskId==3)
	{
		Subtask3::main();
	}
	if(taskId==4)
	{
		Subtask4::main();
	}
	if(taskId==5)
	{
		Subtask5::main();
	}
}

ID

5032

时间

400ms

内存

500MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

题面

前言

题解

$\texttt{Subtask 1(4 pts)}$

$\texttt{Subtask 2(16 pts)}$

$\texttt{Subtask 3(16 pts)}$

$\texttt{Subtask 4(32 pts)}$

$\texttt{Subtask 5(32 pts)}$

代码

『MdOI R1』Epic Convolution

信息

1 条题解

自动搬运

以下是正文

题面

前言

题解

Subtask 1(4 pts)\texttt{Subtask 1(4 pts)}Subtask 1(4 pts)

Subtask 2(16 pts)\texttt{Subtask 2(16 pts)}Subtask 2(16 pts)

Subtask 3(16 pts)\texttt{Subtask 3(16 pts)}Subtask 3(16 pts)

Subtask 4(32 pts)\texttt{Subtask 4(32 pts)}Subtask 4(32 pts)

Subtask 5(32 pts)\texttt{Subtask 5(32 pts)}Subtask 5(32 pts)

代码

『MdOI R1』Epic Convolution

信息

还没有账户？

登录

$\texttt{Subtask 1(4 pts)}$

$\texttt{Subtask 2(16 pts)}$

$\texttt{Subtask 3(16 pts)}$

$\texttt{Subtask 4(32 pts)}$

$\texttt{Subtask 5(32 pts)}$