【组合数学 动态规划】P6870 [COCI2019-2020#5] Zapina|普及+

本文涉及知识点

组合数学汇总
C++动态规划

[COCI2019-2020#5] Zapina

题目描述

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

第 i i i 个人开心当且仅当他被分配到 i i i 道题，题号不限。

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

输入格式

一个正整数： n n n。

输出格式

一个数字：你的答案 m o d 10 9 + 7 \bmod 10^9+7 mod109+7。

样例 #1

样例输入 #1

1 

样例输出 #1

1 

样例 #2

样例输入 #2

2 

样例输出 #2

3 

样例 #3

样例输入 #3

314 

样例输出 #3

192940893 

提示

数据范围

本题捆绑测试。

• 对于 22 p t s 22 pts 22pts 的数据， 2 ≤ n ≤ 7 2\leq n\leq 7 2≤n≤7。
• 对于另外 33 p t s 33 pts 33pts 的数据， 1 ≤ n ≤ 20 1\leq n\leq 20 1≤n≤20。
• 对于所有的数据， 1 ≤ n ≤ 350 1\leq n\leq 350 1≤n≤350。

样例#2解释

有以下 3 3 3 种方案：

• 第一题給第一个人，第二题給第二个人。第一个人开心。
• 第二题給第一个人，第一题給第二个人。第一个人开心。
• 两题都给第二个人。第二个人开心，期望分配两题，也分配到两题。

动态规划(无法通过）

动态规划之状态表示

dp[i][j][k]记录符合以下条件的方案数。前i个人物已经分配完题目，已经分配j题，有k个人开心。
空间复杂度：O(nnn)，用滚动向量优化空间 pre = dp[i-1],cur= dp[i]。

动态规划之转移方程

枚举后置状态
dp[i][j][k] += ( ∑ p : 0 j d p [ i − 1 ] [ j − p ] [ k ] × C n − ( j − p ) p ) − d p [ i − 1 ] [ j − i ] [ k ] × C n − ( j − i ) i (\sum_{p:0}^{j}dp[i-1][j-p][k] \times C_{n-(j-p)}^{p})-dp[i-1][j-i][k]\times C_{n-(j-i)}^{i} (∑p:0j​dp[i−1][j−p][k]×Cn−(j−p)p​)−dp[i−1][j−i][k]×Cn−(j−i)i​ 第i个人不开心。第二项必须j >= i。由于表达式包括j,p，所以无法利用前缀和优化。
dp[i][j][k] += dp[i-1][j-i][k-1] 第i个人开心，注意：i >= i 且k >0。
单个状态转移时间复杂度:O(1)，总时间复杂度：O(nnn)

动态规划的填表顺序

i = 1 to N k =0 to N j =0 to N

动态规划的初始值

dp[0][0][0]=1，其它全为0。

动态规划的返回值

典型的容斥原理应用，预处理好cnt[i]，然后代入公式。
cnt[i] = dp.back().back()[i]

动态规划二

动态规划状态表示

dp[i][j]记录所有人都不快乐的方案数：i表示前i个人都已经分配完题目，已经分配了j个题目。
空间复杂度：O(nn)

动态规划的转移方程

枚举前置状态
for p = 0 to n-j 且p ≠ \neq = i+1
dp[i+1][j+p] += dp[i][j] × C n − j p \times C_{n-j}^{p} ×Cn−jp​
单个状态转移的时间复杂度O(n)，总时间复杂度O(nnn)

动态规划的初始值

dp[0][0]=1，其它全为0。

动态规划的填表数学

i = 0 to n-1 j = 0 to N

动态规划的返回值

nⁿ-dp.back() 总方案数减去所有人不快乐的方案数。

代码

核心代码

#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<bitset>usingnamespace std;template<classT=int> vector<T>Read(int n,constchar* pFormat ="%d"){ vector<T> ret; T d ;while(n--){scanf(pFormat,&d); ret.emplace_back(d);}return ret;}template<classT=int> vector<T>Read(constchar* pFormat ="%d"){int n;scanf("%d",&n); vector<T> ret; T d;while(n--){scanf(pFormat,&d); ret.emplace_back(d);}return ret;} string ReadChar(int n){ string str;char ch;while(n--){do{scanf("%c",&ch);}while(('\n'== ch)); str += ch;}return str;}template<int MOD =1000000007>classC1097Int{public:C1097Int(longlong llData =0):m_iData(llData% MOD){} C1097Int operator+(const C1097Int& o)const{returnC1097Int(((longlong)m_iData + o.m_iData)% MOD);} C1097Int&operator+=(const C1097Int& o){ m_iData =((longlong)m_iData + o.m_iData)% MOD;return*this;} C1097Int&operator-=(const C1097Int& o){ m_iData =(m_iData + MOD - o.m_iData)% MOD;return*this;} C1097Int operator-(const C1097Int& o){returnC1097Int((m_iData + MOD - o.m_iData)% MOD);} C1097Int operator*(const C1097Int& o)const{return((longlong)m_iData * o.m_iData)% MOD;} C1097Int&operator*=(const C1097Int& o){ m_iData =((longlong)m_iData * o.m_iData)% MOD;return*this;} C1097Int operator/(const C1097Int& o)const{return*this* o.PowNegative1();} C1097Int&operator/=(const C1097Int& o){*this/= o.PowNegative1();return*this;}booloperator==(const C1097Int& o)const{return m_iData == o.m_iData;}booloperator<(const C1097Int& o)const{return m_iData < o.m_iData;} C1097Int pow(longlong n)const{ C1097Int iRet =1, iCur =*this;while(n){if(n &1){ iRet *= iCur;} iCur *= iCur; n >>=1;}return iRet;} C1097Int PowNegative1()const{returnpow(MOD -2);}intToInt()const{return(m_iData + MOD)% MOD;}private:int m_iData =0;;};template<classResult= C1097Int<>>classCCombination{public:CCombination(){ m_v.assign(1,vector<Result>(1,1));} Result Get(int sel,int total){assert(sel <= total);while(m_v.size()<= total){int iSize = m_v.size(); m_v.emplace_back(iSize +1,1);for(int i =1; i < iSize; i++){ m_v[iSize][i]= m_v[iSize -1][i]+ m_v[iSize -1][i -1];}}return m_v[total][sel];}protected: vector<vector<Result>> m_v;};classSolution{public:intAns(int N){ vector<vector<C1097Int<>>>dp(N +1,vector<C1097Int<>>(N +1)); dp[0][0]=1; CCombination com;for(int i =0; i < N; i++){auto& pre = dp[i];auto& cur = dp[i +1];for(int j =0; j <= N; j++)for(int p =0; p <= N - j; p++){if(i +1== p){continue;} cur[j + p]+= pre[j]* com.Get(p, N - j);}} C1097Int<> ans =C1097Int<>(N).pow(N)- dp.back().back();return ans.ToInt();}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUGint n;scanf("%d",&n);auto res =Solution().Ans(n); cout << res << std::endl;return0;}

单元测试

TEST_METHOD(TestMethod11){auto res =Solution().Ans(1);AssertEx(1, res);}TEST_METHOD(TestMethod12){auto res =Solution().Ans(2);AssertEx(3, res);}TEST_METHOD(TestMethod13){auto res =Solution().Ans(314);AssertEx(192940893, res);}TEST_METHOD(TestMethod14){ vector<int> 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};for(int i =0; i <min(200u,ans.size()); i++){auto res =Solution().Ans(i);AssertEx(ans[i], res);}}

扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。