牛客手速月赛43 E(dp)

题目 题意: 给定数字1-9的数量cnt[i]。计算出“满意的集合“的个数。 “满意的集合” 定义：选出的数的和为3的倍数。 空集合和为0，视为合法。此处的集合是本质set概念，123和321属于同一集合。 思路: dp. 定义f[i][j]表示只用1-i,将余数为j的集合的数量。 可以考虑暴力，枚举第i个数使用0-cnt[i]次，obviously，是一个不能接受的时间复杂度。 但是%3的结果只会有0、1、2，0-cnt[i]次中有多少个余0、1、2我们可以直接算出来。 选1、4、7个一样;2、5、8个一样;3、6、9个一样 那么我们可以直接O(1)计算出这三种模数，之后枚举前i-1个数的模数取值 时间复杂度: O(9 * 3) 代码:

// Problem: 满意的集合
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11220/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i