P6870 题解
Wangxun
·
·
题解
前置芝士：容斥原理
简记为：奇加偶减。
分析：
一道裸的计数 DP 题。
记 dp_{i,j,k} 为前 i 个人中，已经分配了 j 道题，恰好使 k 个人满足的方案数。
容易发现 dp_{1,0,0}=1。
有两组决策，让 i 满足或者不让 i 满足。
$dp_{i+1,j,k} = dp_{i+1,j,k} + dp_{i,j,k}$。
根据容斥原理，最后的答案为，$\sum\limits_{j=1}^n\sum\limits_{k=1}^n (-1)^{k+1} \times dp_{n,j,k}$。
时间复杂度: $O(n^3)$。
空间复杂度：$O(n^3)$。
注意这样会爆空间，应采用滚动数组进行优化。
优化后空间复杂度：$O(n^2)$。
### 代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(register T &x)
{
register T p = 1,num = 0;
char c = getchar();
while(c < '0'||c > '9')
{
if(c == '-') p = -1;
c = getchar();
}
while('0' <= c&&c <= '9')
{
num = (num<<3)+(num<<1)+(c^48);
c = getchar();
}
x = p * num;
}
template<typename T>inline void write(register T x)
{
if(x < 0) putchar('-'),x = -x;
if(x > 9) write(x/10);
putchar(x%10^48);
}
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define D(i,a,b) for(register int i=b;i>=a;--i)
#define ll long long
#define N 355
const int mod = 1e9 + 7;
int n;
ll fac[N],inv[N],pw[N],ans = 0;
inline ll qp(ll x,int y)
{
ll ret = 1;
while(y)
{
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll dp[2][N][N];
int main()
{
read(n);
inv[0] = inv[1] = fac[0] = fac[1] = pw[0] = 1;
F(i,2,n) fac[i] = fac[i-1] * i % mod;
F(i,2,n) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
F(i,2,n) inv[i] = inv[i] * inv[i-1] % mod;
dp[1][0][0] = 1;
F(i,1,n)
{
memset(dp[i+1&1],0,sizeof(dp[i+1&1]));
F(j,0,n)
F(k,0,n)
{
if(j+i <= n) dp[i+1&1][j+i][k+1] = (dp[i+1&1][j+i][k+1] + dp[i&1][j][k]*fac[n-j]%mod*inv[n-j-i]%mod*inv[i]) % mod;
dp[i+1&1][j][k] = (dp[i+1&1][j][k] + dp[i&1][j][k]) % mod;
}
}
F(j,1,n)
F(k,1,n)
{
dp[n+1&1][j][k] = dp[n+1&1][j][k] * qp(n-k,n-j) % mod;
if(k & 1) ans = (ans + dp[n+1&1][j][k]) % mod;
else ans = (ans - dp[n+1&1][j][k] + mod) % mod;
}
write(ans);
return 0;
}
```
### 最后
可以发现，输入只有 $n$ 一个数，又是一道打表好题。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,ans[]={0,1,3,16,147,1756,25910,453594,9184091,211075288,427652759,380254172,88525330,594308696,594582617,496808516,230533631,930048563,734906046,145824550,963104287,792576272,20842121,926710860,624063170,435324673,941196758,100412345,829823320,16604011,119246612,467453588,296507940,19474275,437566401,580597104,325614134,114081039,16970316,54942632,953074343,664503025,963474561,463988230,901088598,552316694,370315853,363024430,361814615,987969955,356909604,72317551,362905861,844210242,74494960,267374090,9829229,80574666,190779497,993501688,667880842,25921000,891056540,820027654,988133379,860424629,164712123,638551214,64068242,852828384,594849040,713709588,713810843,796807000,639934368,445930895,853650080,686849288,687485088,204732826,938270531,233180167,680119887,798575300,221191668,719754542,183970632,65159363,102009420,106900582,603406815,547850988,69043888,441404069,178108361,171613595,194519530,846734478,733143650,732291535,534460323,424030598,293484626,18815201,585676643,912726223,510270289,151012819,929291571,529049185,117076206,900078971,614777735,348106199,423774249,574430766,526570315,748176803,31818969,501560666,705499512,806457493,862367692,255090341,812275285,136149440,140879753,956968322,984467061,121221372,826702704,995609955,640463338,795423206,438017231,104878010,715195281,87713761,472145514,512444087,528010597,448216404,715864432,365209471,998258892,47038284,945845611,742836670,874752539,351178973,115572999,85498210,750445820,566986136,507422951,263280651,363746668,721379342,657233523,368070024,365517137,557356212,405385770,702731018,726524565,582672271,713823066,172539263,452254713,108837529,685050929,112599223,950160771,537791717,196634339,765215429,723039551,992336331,495498388,734598160,166618212,690246061,613497507,91548173,34919956,30705717,150505766,252695495,997416620,426419436,299460599,841765395,170108584,130185332,573662799,620823933,366877355,870627156,903422770,826307196,361255220,710936088,447319974,885230522,664999650,227183665,35153803,597619983,251027027,953802478,83703267,961654121,351763496,571777475,19373724,564323159,525846126,988983101,113976315,976654852,957177092,547018849,207894228,385473127,401477473,894388178,414921794,285963181,179455247,584525294,721286723,628695619,608638999,599226595,806938357,465644549,296878851,573944747,201107705,585546352,487718852,205357994,277758478,969139685,461220859,461004882,132504633,615131412,824346063,924255686,759290174,358422542,635725603,176609609,917792915,257455569,746184536,316402317,783793186,500434871,517428456,451399654,409643100,482863842,176126614,820640574,657068590,362058002,242650619,186901373,515265982,89328722,942695111,540996271,90622012,138665430,818615553,784975850,417957865,721662199,737792977,495770091,951382091,316267089,374149589,284673490,916782568,790954001,602629711,531192034,664953974,624778690,283568537,34602368,376162450,10239950,812647987,99619518,509861236,256514260,341204270,899013232,614243782,535500022,518807185,472039848,306389369,965790287,155402774,825826404,381603778,307185930,856889200,248603369,192940893,25534731,193328908,438514397,782463496,892910780,686315937,919983254,111131855,299340566,255665989,470190823,983178320,961595576,279565492,63447508,69379637,540261561,887203349,350550553,701031556,754173085,251426123,533498405,443766626,741119012,897485842,708580238,529660266,493526336,813446619,453474512,927471565,937547684,981739148,653129658,688023819};
int main()
{
scanf("%d",&n);
printf("%d",ans[n]);
return 0;
}
```