首页 > 其他分享 >[题解] [ABC221H] Count Multiset - DP

[题解] [ABC221H] Count Multiset - DP

时间:2024-07-11 10:31:08浏览次数:13  
标签:int 题解 sum 样例 long 集合 ABC221H Multiset dp

[ABC221H] Count Multiset

题面翻译

输入两个正整数 \(N,M\),并存在一个集合,问你一个长度为 \(k\) 的合法集合存在多少个?你需要回答 \(k\) 的值为 \(1\) 到 \(N\) 的每种情况。

一个合法的集合定义指长度为 \(k\),元素和为 \(N\),每一个数字在集合中出现的次数都小于等于 \(M\) 的集合。

题目描述

正の整数 $ N $, $ M $ が与えられます。

$ k=1,2,\ldots,N $ について以下の値を求め、$ 998244353 $ で割ったあまりをそれぞれ出力してください。

  • $ k $ 個の正整数からなる多重集合 $ A $ のうち、以下の $ 2 $ つの条件をすべて満たすものの個数
    • $ A $ に含まれる要素の総和は $ N $
    • 任意の正整数 $ x $ について、$ A $ は $ x $ を高々 $ M $ 個しか含まない

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $

输出格式

$ N $ 行に渡って出力せよ。$ i\ (1\ \leq\ i\ \leq\ N) $ 行目には、$ k=i $ の場合の答えを出力すること。

样例 #1

样例输入 #1

4 2

样例输出 #1

1
2
1
0

样例 #2

样例输入 #2

7 7

样例输出 #2

1
3
4
3
2
1
1

提示

制約

  • $ 1\ \leq\ M\ \leq\ N\ \leq\ 5000 $
  • 入力はすべて整数

Sample Explanation 1

- $ k=1 $ のとき、問題文中の条件を満たすような多重集合 $ A $ は $ {4} $ の $ 1 $ 通りです。 - $ k=2 $ のとき、問題文中の条件を満たすような多重集合 $ A $ は $ {1,3} $ と $ {2,2} $ の $ 2 $ 通りです。 - $ k=3 $ のとき、問題文中の条件を満たすような多重集合 $ A $ は $ {1,1,2} $ の $ 1 $ 通りです。 - $ k=4 $ のとき、問題文中の条件を満たすような多重集合 $ A $ は $ 1 $ つも存在しません。

解析

一道神奇的 dp 题。有个神奇的转移方式。

看到题目直接联想到背包,但发现 相同元素不超过 \(m\) 这个限制条件很毒瘤。无法用背包转移。然后死活想不出来其他方法。

根据题解,我们不按照背包的思路想,就把他看成一段序列,元素为非负整数(如果有负数,那么每一种情况都有无穷种方案)。令 \(dp[i][j]\) 表示集合里有 \(i\) 个元素,和为 \(j\) 的方案数。考虑在整个序列里添加 \(0\),那么它只对 \(i\) 有贡献,可以得到:\(dp[i][j]+=\sum\limits_{k=1}^{m}dp[i-k][j]\)。但只有 0 不够,考虑在序列里的每一个数加 \(1\),那么它只对 \(j\) 有贡献,可以得到:\(dp[i][j]+=dp[i][j-i]\)。

但还有个 相同元素不超过 \(m\) 这个限制条件,我们不知道一个 \(dp\) 序列里有多少个 \(0\),所以需要再开个数组 \(g[i][j]\) 表示没有元素为 \(0\) 的方案数。如何让元素不为 \(0\) 呢?把每个元素 \(+1\) 即可。于是有:

\[\begin{split} dp[i][j]&=dp[i][j-i]+\sum_{k=1}^{m}dp[i-k][j]\\ g[i][j]&=dp[i][j-1] \end{split} \]

如果直接 for 硬套的话,复杂度为 \(O(N^2M)\)。会超。

70 TLE 代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 5010, M = 998244353;
int n, m, dp[N][N], g[N][N];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; ++i) dp[i][0] = 1ll;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			if(j >= i){
				g[i][j] = (g[i][j] + dp[i][j-i]) % M;
				dp[i][j] = (dp[i][j] + dp[i][j-i]) % M; 
			}
			for(int k=1; k<=m && i-k>=0; ++k){
				dp[i][j] = (dp[i][j] + g[i-k][j]) % M;
			}
		}
	}
	for(int i=1; i<=n; ++i) cout<<g[i][n]<<'\n';
	return 0;
}

对于那个最内层循环,可以使用前缀和优化,使复杂度分摊到每一次循环 \(O(1)\),于是总复杂度 \(O(N^2)\),对了,本题不能开 long long,会爆空间。

AC code

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 5001, M = 998244353;
int n, m, dp[N][N], g[N][N], sum[N][N];
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; ++i) dp[i][0] = 1ll;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			if(j >= i){
				g[i][j] = (g[i][j] + dp[i][j-i]) % M;
				dp[i][j] = (dp[i][j] + dp[i][j-i]) % M; 
			}
			sum[i][j] = (sum[i-1][j] + g[i][j]) % M;
			dp[i][j] = (__int128)(dp[i][j] + sum[i-1][j] - sum[max(i-m-1, 0)][j]) % M;
		}
	}
	for(int i=1; i<=n; ++i) cout<<g[i][n]<<'\n';
	return 0;
}

小结:

  • 不要过于思维定式。如果发现一个方案不可行或很难行要跳出来另找其他方案。
  • 对于求转移方程,可以考虑控制变量,即只对某一变量产生贡献,最后再将贡献合并。很好的思路,只是比较难想。
  • define int long long 不要再用了。
  • 计算空间复杂度。

标签:int,题解,sum,样例,long,集合,ABC221H,Multiset,dp
From: https://www.cnblogs.com/xiaolemc/p/18295512

相关文章

  • CF506D题解
    Mr.Kitayuta'sColorfulGraph算法:根号分治。题目大意先说一下:给一个\(n\)点\(m\)边的无向图,边有颜色。\(q\)组询问,每次给出\(u,v\),求有多少种颜色\(c\),使得存在一条\(u\)到\(v\)的路径,这个路径中每条边的颜色都为\(c\)。先考虑一个朴素的暴力,暴力对每个颜色加边,......
  • UVA12683 Odd and Even Zeroes 题解
    题目简述定义\(\operatorname{count}(num)\)表示\(num\)末尾\(0\)的个数。给出\(n\)(\(n\leq10^{18}\)),求\(\sum\limits_{i=0}^{n}[2\mid\operatorname{count}(i!)]\)。题目分析对于一个\(i\),以下记成\(n\)。\(n!\)末尾\(0\)的个数取决于\(1\simn\)......
  • [ARC080F] Prime Flip 题解
    Description有无限枚硬币,其中有\(n\)枚硬币\(x_{1\ldotsn}\)。初始时正面朝上,其余均为背面朝上,每次可以选择一段区间\([l,r]\),将区间内所有硬币翻转,其中\(r-l+1\)为一个奇质数。问最少多少次能将所有硬币全部翻为背面朝上。\(1\leqn\leq100,1\leqx_1\leqx_2\leq\ld......
  • CF369D Valera and Fools 题解
    传送门LuoguCodeforces题意简述有\(n\)个傻子智者站成一排,每人手中有\(k\)发子弹,每次每人会向除自己外编号最小的人开枪,第\(i\)个人开枪的命中率为\(p_i\%\),剩余最多一人时结束,问有多少种可能的局面。解法说明从题目要求中可以发现,每次一定是编号最小的人向编号第二......
  • 优化爬虫体验:揭秘IP重复率过高问题解决方案
    在当今信息爆炸的时代,网络中蕴藏着大量宝贵的数据,而爬虫技术成为我们提取这些数据的重要工具。然而,随着爬虫的广泛使用,IP重复率高的问题也随之而来。本篇博文将揭秘解决这一问题的关键方法——使用IP代理。一、IP高重复问题带来的挑战&nbsp;被封禁风险:当一个IP在短时间内频......
  • 优化爬虫体验:揭秘IP重复率过高问题解决方案
    在当今信息爆炸的时代,网络中蕴藏着大量宝贵的数据,而爬虫技术成为我们提取这些数据的重要工具。然而,随着爬虫的广泛使用,IP重复率高的问题也随之而来。本篇博文将揭秘解决这一问题的关键方法——使用IP代理。一、IP高重复问题带来的挑战&nbsp;被封禁风险:当一个IP在短时间内频......
  • 优化爬虫体验:揭秘IP重复率过高问题解决方案
    在当今信息爆炸的时代,网络中蕴藏着大量宝贵的数据,而爬虫技术成为我们提取这些数据的重要工具。然而,随着爬虫的广泛使用,IP重复率高的问题也随之而来。本篇博文将揭秘解决这一问题的关键方法——使用IP代理。一、IP高重复问题带来的挑战&nbsp;被封禁风险:当一个IP在短时间内频......
  • 题解:P10732 [NOISG2019 Prelim] Palindromic FizzBuzz
    题解:P10732[NOISG2019Prelim]PalindromicFizzBuzz题意题意十分明了,给予你一个区间,判断区间中每一个数是否是回文数。思路思路比较简单,首先将每一个数按每一位放入一个数组中,顺序无论由前到后和由后到前都可以。接下来将数组折半循环,判断前后是否一样。一样的话是回文数,......
  • 题解:P8144 [JRKSJ R4] BBWWBB
    思路分析题意可得,白方必定不会胜利,只能尽量让游戏无限进行下去。那么我们只考虑黑方能否胜利。若想让戏能无限进行下去,必须满足以下条件。白方先手。若黑方先手必然可以吃掉一个白方,白方仅有一个棋子,必输。白方第一轮可以吃掉一颗黑方。因为只有\(3,4\)是白方,所以......
  • 洛谷CF1342B Binary Period题解
    原题解和原题。这道题比较水。这道题分两种情况,分别为$t$由一种字符构成和由两种字符构成两种情况。$t$只有$0$或$1$。此时的$k$就是$1$,直接输出$t$就是最好的选择。$t$既有$0$又有$1$。此时的$k$为$2$,字符串由01或10构成。我们设$a_i$为字符串......