Description小Y有一个大小为\(n\)的背包，并且小Y有\(n\)种物品。对于第\(i\)种物品，共有\(i\)个可以使用，并且对于每一个\(i\)物品，体积均为\(i\)。求小Y把该背包装满的方案数为多少，答案对于\(23333333\)取模。定义两种不同的方案为：当且仅当至少存在一种物品的

此优化针对以下计数问题：n件物品，背包容量为m，第i件物品体积为\(a_i\)，求装满的方案数。（01背包）n种物品，背包容量为m，第i件物品体积为\(a_i\)，数量无限，求装满的方案数。（完全背包）n种物品，背包容量为m，第i件物品体积为\(a_i\)，数量为\(b_i\)，求装满的方案数。（多重背包）\((1\l

https://class.51nod.com/Html/Textbook/ChapterIndex.html#chapterId=335&textbookId=126https://class.51nod.com/Html/Challenge/Problem.Html#problemId=1597如有限背包计数问题发现对于物品\(i\)最多填充\(i*i\)，而对于\(i>\sqrtn\)可以视为完全背包，所以我们分为两类

数位统计DP定义数位DP（DigitalDP）是一种用于解决与数字的数位相关问题的动态规划算法。它将数字的每一位看作一个状态，通过转移状态来计算满足特定条件的数字个数或其他相关统计信息。运用情况统计满足特定条件的数字个数，例如在给定范围内有多少个数字满足某些数位特征。计算

描述试计算在区间[1,n]的所有整数中，数字x（0<=x<=9）共出现了多少次？例如，在1到11中，即在1、2、3、4、5、6、7、8、9、10、11中，数字1出现了4次。输入描述共1行，包含2个正整数n、x，之间用一个空格隔开。输出描述共一行，包含一个整数，表示x出现的次数。用例输入1111用例输出14

原题链接：https://www.luogu.com.cn/record/160821231题意解读：统计1~n中x的个数。解题思路：枚举每个数，提取每一位，判断是否等于x。100分代码：#include<bits/stdc++.h>usingnamespacestd;intn,x,ans;intmain(){cin>>n>>x;for(inti=1;i<=n;i++)

Prüfer序列\(n\)个点的有标号无根树可以与一个长度为\(n-2\)的Prüfer序列对应。从树到Prüfer序列\(f\)为空序列。如果当前树上多于两个节点，假设当前标号最小的叶子为\(x\)，与\(x\)相连的节点标号为\(y\)，那么把\(x\)从树上删除，把\(y\)加入\(f\)末尾。

statement给定数列\(w_1,w_2\cdotsw_n,w_i\in[1,m]\)，考虑一个\(n\)个点的图，节点\(i,j\)之间的边的个数为\(\sum\limits_{k=1}^ma_{k,w_i}b_{k,w_j}c_k\)，你需要求出这个图的生成树个数。solution设度数矩阵为\(D\)，邻接矩阵为\(G\)，由矩阵树定理，我们要计算\(\det(D-G

模拟题，复读一下EI老师的营业日志。题意：给出\(n,m,u,v\)，试计算：\[[x^n]\prod_{i=1}^{m}\frac{1}{1-(ui+v)x}\bmod998244353\]其中\(n\le10^{18},m\le5\times10^5\)。直接分治NTT算出分式，再套bostan-mori的话复杂度是\(O(m\logm\logn)\)的，难以通过。考虑使用部

UPD2023.12.31：失手把原来的博文删掉了，这篇是补档。引入在一类序列计数问题中，状态转移的过程可能与相邻的已插入元素的具体信息相关（e.g.插入一个新元素时，需要知道与其插入位置相邻的两个元素的值是多少，才可进行状态转移，如「JOIOpen2016」摩天大楼）。这类问题通常的特点是，如

LinkT399753countingproblem（计数问题）Question给出一个正整数\(n\)，求\(AB+CD=n\)的方案数，\(A,B,C,D\)都是要求是正整数Solution考虑直接枚举\(ABCD\)显然是不切实际的那么就折半枚举设\(F_i\)表示两个数的乘积为\(i\)的方案数答案就是\(\sum\limits_{i=1

鉴于我之前每次考试计数问题都会错一大堆,所以我滚过来写总结了先膜拜贡献了这个题单的@feecle6418以下题目笔者没有事先做过,和大家一起做,所以会有一些不成熟的思路,但是同时也会更好的展示思维路径.我们先来看几道题来醒醒脑子洛谷P6146HelpYourselfG题意简述:现

[NOIP2013普及组]计数问题题目描述试计算在区间到的所有整数中，数字（）共出现了多少次？例如，在到中，即在中，数字出现了次。输入格式个整数，之间用一个空格隔开。输出格式个整数，表示出现的次数。样例#1样例输入#1111样例输出#14提示对于的数据，，。思路求每个数字的

MyBlogs开个新坑，目前大多数是蓝书上的题。不会更高级的东西，只写怎么数数，不考虑高级优化。状态设计：这里满足的要求不再是无后效性，而是要求一个阶段的所有状态能不重不漏的覆盖掉所有情况。转移：寻找合适的基准点，围绕这个基准点把大的状态拆出一个小的不可划分的状态，和剩下的状

约定\(K\)维空间中，整点的坐标以\(K\)个整数表示，形如\[Point\left(X_1,X_2,\cdots,X_k\right)\]定义两个点的曼哈顿距离为每一维坐标差的绝对值之和，记为\[MD\left(A,B\right)=\sum_{i=1}^{K}\left|{X_{i_A}-X_{i_B}}\right|\]定义两个点\(A\),\(B\)相邻当且仅当

/*先是建图，跑一次缩点建立一个最初的阵营加上0代表认识，1代表不认识ans=0因为划分了两个独立的阵营，所以一次是只能交换一个人的如果对方阵营我只认识一个，并且我认识的哪一个可以来到我的阵营，那么就将两者进行交换（0，1）如果对方阵营的我都不敌对，或不认识，那我就可以直接过

题意一个长度为\(n\)且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。要求复杂度为\(O(n^3)\)分析由题意可知，我们可以这样定义括号匹配序列：空序列是括号匹配序列。如果S是括号匹配序列，那么\((S)\)也是括号匹配序列。如果

方式1List<AggregationOperation>operations=newArrayList<>();operations.add(Aggregation.match(Criteria.where("created_at").gte(begin).lte(end)));operatio

导读^_^数位DP数位DP，即是对数的每一位进行统计操作的DP问题。计数问题思路（分类讨论）首先，如果一遍遍枚举，显示是不行的，因为1e8次这样，明显会超时。这类问题的关键是

二维树状数组板子，C[color][x][y] #include<bits/stdc++.h>usingnamespacestd;constintN=403,M=2e5+4;#defineintlonglongintA[N][N],c[101][N

题目链接：https://www.luogu.com.cn/problem/P1980术语以下的英文术语均可以翻译为数字。digit:一个数字字符，十进制就是0-9之间的一个字符；numeral:用来表示数字的

题目链接：https://www.acwing.com/problem/content/340/题目描述给定两个整数a和b，求a和b之间的所有数字中0∼9的出现次数。例如，a=1024，b=1032，则a和b之间共

传送门二维树状数组板子题（大概？）只要再多开一维\(c\)来存储该点的权值就可以了。这里的树状数组\(a[i][j][c]\)表示以第\(i\)行，第\(j\)列为右下角，权值为\(c\)的点

类型1：单个边界范围f(i)<d(j)这种格式的不等式，算法题经常询问我们满足这样的数对有多少。中间的符号也可换成任何等号不等号，也同样适用怎么计算呢？本质上，使用归并排序就是下面

最近感觉学了好多东西，感觉人有点混乱了。今天下午暂时不做题了，写个总结吧。思维框架主动转化问题：强化限制，给问题加上一些限制来简化问题模型。通俗地来讲就是枚举和分