题意

有 $n$ 个不同的人和 $n$ 道不同的题。

第 $i$ 个人开心当且仅当他被分配到 $i$ 道题。

求让至少一个人开心的分配方案数。

思路

显然 dp。

设 $f(i,j)$ 表示前 $i$ 个人分配 $j$ 道题且至少已经有一个人开心的方案数。

考虑转移：

• 使 $i$ 开心：随便給他 $i$ 道，剩下 $j-i$ 道随便分給剩下的 $i-1$ 个人。 方案数：$C(j,i)\times (i-1)^{j-i}$。

• 使 $i$ 不开心：随便給他 $k$ 道，剩下 $j-k$ 道給 $i-1$ 个人并使这 $i-1$ 个人中有人开心。 方案数：$C(j,k)\times f(i-1,j-k)$。

官方题解也是这种思路。

$code$

#include<stdio.h>
#define N 351
#define mod 1000000007
int n,c[N][N],ans[N][N];
inline int ksm(long long a,int b)
{
	long long ans=1;
	for(;b;b>>=1,a*=a,a%=mod)if(b&1)ans*=a,ans%=mod;
	return ans;
}
main()
{
	scanf("%d",&n);
	for(int i=0;i<=n;++i)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;++j)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	ans[1][1]=1;
	for(int i=2;i<=n;++i)for(int j=1;j<=n;++j)
	{
		if(j>=i)ans[i][j]=1ll*c[j][i]*ksm(i-1,j-i)%mod;//使i开心
		for(int k=0;k<=j;++k)if(i!=k)//使i不开心
			ans[i][j]=(ans[i][j]+1ll*ans[i-1][j-k]*c[j][k])%mod;
	}
	printf("%d",ans[n][n]);
}

$O(1)$解法

#include<bits/stdc++.h>
using namespace std;
int a[]={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()
{
	int n;scanf("%d",&n);
	printf("%d\n",a[n]);
	return 0;
}