【动态规划 C++动态规划】P10986 [蓝桥杯 2023 国 Python A] 2023|普及+

本文涉及知识点

C++动态规划 数位dp

[蓝桥杯 2023 国 Python A] 2023

题目背景

建议使用 PyPy3 提交本题。

题目描述

给定 n , m n, m n,m，请求出所有 n n n 位十进制整数中有多少个数中恰好出现了 m m m 个 2023 2023 2023。

例如 00202312023 00202312023 00202312023 是一个 11 11 11 位的出现了 2 2 2 个 2023 2023 2023 的十进制整数。

由于结果可能很大，请输出答案对 998 , 244 , 353 998,244,353 998,244,353 取模的结果。

输入格式

输入一行包含两个整数 n , m n,m n,m，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

5 1 

样例输出 #1

20 

提示

对于 40 % 40\% 40% 的评测用例， n ≤ 10 5 , m ≤ 10 n \le 10^5,m \le 10 n≤105,m≤10；

对于所有评测用例， 4 ≤ n ≤ 10 5 , 0 ≤ 4 m ≤ n 4 \le n \le 10^5,0 \le 4m \le n 4≤n≤105,0≤4m≤n。

P10986 # 数位dp
自定义状态：两部分合成int。第一部分：2023的数量i1，取值范围[0,m+1]，超过m+1个，算m+1个。第二部分：i2,结尾是202，3；20,2,2；1；其它0。
202遇到3，i1++，i2=0。遇到0,i2=2，其它规则1。
20遇到2，i2++。其它规则1。
2遇到0，i2++。其它规则1。
规则1：遇到2，i2=1，否则i2=0。
时间复杂度： 每位的状态m，n位，字符集长度 ∑ \sum ∑是10。O(nm ∑ \sum ∑)，超时。

组合数学 放球问题 容斥原理

f(x)记录至少x个2023的方案数。
x个2023,插入n-4x个数。 i f f iff iff n-4x个相同的球，放到x+1个不同的盒子。n-4x个数，可以从0到9任意选择。
本题答案： f(m)-f(m+1)+f(m+2) ⋯ \cdots ⋯f(n/4)

代码

核心代码

#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<cstring>#include<bitset>usingnamespace std;template<classT=int> vector<T>Read(int n,constchar* pFormat ="%d"){ vector<T>ret(n);for(int i=0;i<n;i++){scanf(pFormat,&ret[i]);}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<classT1,classT2>voidReadTo(pair<T1, T2>& pr){ cin >> pr.first >> pr.second;}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<classT>classCFactorial{public:CFactorial(int n):m_res(n +1){ m_res[0]=1;for(int i =1; i <= n; i++){ m_res[i]= m_res[i -1]* i;}} T Com(int iSel,int iCanSel)const{return m_res[iCanSel]/ m_res[iSel]/ m_res[iCanSel - iSel];} T Com(const vector<int>& cnt)const{ T biRet =1;int iCanSel = std::accumulate(cnt.begin(), cnt.end(),0);for(int j =0; j < cnt.size(); j++){ biRet *=Com(cnt[j], iCanSel); iCanSel -= cnt[j];}return biRet;} vector<T> m_res;};template<classT>classCBallBox{public:CBallBox(CFactorial<T>& fac,int cntBall,int cntBox):m_fac(fac),m_iN(cntBall),m_iM(cntBox){} T NotNotNot(){//球不同盒子不同不能为空returng(m_iM);} T NotIsNot(){//球不同盒子同不能为空returnNotNotNot()/ m_fac.m_res[m_iM];} T IsNotIs(){//球同盒子不同能为空return m_fac.Com(m_iM -1, m_iN + m_iM -1);} T IsNotNot(){//球同盒子不同不能为空if(m_iN < m_iM){return0;}return m_fac.Com(m_iM -1, m_iN -1);}constint m_iM, m_iN;//m_iN球，m_iM盒子protected: T g(int m)const{ T biRet;for(int i =0; i <= m; i++){auto cur = m_fac.Com(i, m)*Pow(T(m - i), m_iN);if(1& i){ biRet -= cur;}else{ biRet += cur;}}return biRet;} CFactorial<T>& m_fac;};classSolution{public:intAns(int n,int m){typedef C1097Int<998244353> BI; CFactorial<BI>fac(n); vector<BI> anss;auto Cnt =[&](int m){constint iBoxCnt = n -4* m; CBallBox<BI>cb(fac, iBoxCnt, m +1); BI c1 = cb.IsNotIs();auto ans = c1 *BI(10).pow(iBoxCnt); anss.emplace_back(ans);}; BI ans;for(int i =0;4*(i + m)<= n; i++){Cnt(m+i);constint sign =(i +1)%2*2-1; ans += anss.back()* sign*fac.Com(m,i+m);}return ans.ToInt();}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUGint n,m;scanf("%d%d",&n,&m);auto res =Solution().Ans(n,m);#ifdef_DEBUG /* Out(pa, "pa="); Out(vm, ",vm="); printf("n=%d", n);*/#endif cout << res << std::endl;return0;}

单元测试

TEST_METHOD(TestMethod11){auto res =Solution().Ans(5,1);AssertEx(20, res);}TEST_METHOD(TestMethod12){auto res =Solution().Ans(4,1);AssertEx(1, res);}TEST_METHOD(TestMethod13){auto res =Solution().Ans(9,2);AssertEx(30, res);}TEST_METHOD(TestMethod14){auto res =Solution().Ans(6,1);AssertEx(300, res);}TEST_METHOD(TestMethod15){auto res =Solution().Ans(14,3);AssertEx(1000, res);}TEST_METHOD(TestMethod16){auto res =Solution().Ans(20,3);AssertEx(525290362, 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++**实现。