首页 > 其他分享 >LOJ #6089. 小 Y 的背包计数问题 题解

LOJ #6089. 小 Y 的背包计数问题 题解

时间:2024-08-31 22:49:02浏览次数:12  
标签:kMod LOJ 题解 sqrt int ret bs 物品 计数问题

Description

小 Y 有一个大小为 \(n\) 的背包,并且小 Y 有 \(n\) 种物品。

对于第 \(i\) 种物品,共有 \(i\) 个可以使用,并且对于每一个 \(i\) 物品,体积均为 \(i\)。

求小 Y 把该背包装满的方案数为多少,答案对于 \(23333333\) 取模。

定义两种不同的方案为:当且仅当至少存在一种物品的使用数量不同。

\(1\leq n\leq 10^5\)。

Solution

首先有个暴力的做法是设 \(f_{i,j}\) 表示前 \(i\) 种物品,体积为 \(j\) 的方案数,那么可以得到转移:

\[f_{i,j}=\sum_{k=0}^{i}{f_{i-1,j-ik}} \]

注意到转移到 \(j\) 的一定是与 \(j\) 模 \(i\) 同余的数的连续段,用前缀和维护即可做到 \(O(n^2)\)。

容易发现上面那个做法慢在没有利用到某些物品出现次数不多的性质。

可以考虑对于 \(\leq\sqrt n\) 的数可以暴力做。而 \(>\sqrt n\) 的数不可能达到次数限制并且这部分最多选 \(\sqrt n\) 个,要单独处理。

如果直接 dp 显然无法用到选的个数不多的性质。

注意到如果把第 \(i\) 种物品看成长度为 \(i\) 的竖条,那么刚才那个做法是横着进行 dp。又因为列数是不多的,所以可以考虑竖着 dp。这样相当于就是对不超过 \(\sqrt n\) 个物品进行多重背包。

具体的,可以从高向低枚举,每次有两种操作:加入一个高度为 \(\sqrt n+1\) 的长条,和将当前已经加进去的长条整体长度加 \(1\)。显然这两种操作可以构造出所有合法的序列。

设 \(f_{i,j}\) 表示当前有 \(i\) 个长条,长度之和为 \(j\) 的方案数,转移如下:\(f_{i,j+i}\leftarrow f_{i,j},f_{i+1,j+\sqrt n+1}\leftarrow f_{i,j}\)。

最后求答案就将两个部分拼起来即可。

时间复杂度:\(O(n\sqrt n)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5, kMaxB = 325, kMod = 23333333;

int n, b;
int f[kMaxN], g[kMaxN];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void solve1() {
  static int sum[kMaxN];
  f[0] = 1;
  for (int i = 1; i <= b; ++i) {
    for (int j = 0; j <= n; ++j) {
      sum[j] = add(f[j], (j < i) ? 0 : sum[j - i]);
      int p = j - i * (i + 1);
      f[j] = sub(sum[j], (p < 0) ? 0 : sum[p]);
    }
  }
}

void solve2() {
  static int f[kMaxB][kMaxN];
  f[0][0] = 1;
  for (int i = 0; i <= n / b; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i && j + i <= n) inc(f[i][j + i], f[i][j]);
      if (j + b + 1 <= n) inc(f[i + 1][j + b + 1], f[i][j]);
      inc(g[j], f[i][j]);
    }
  }
}

void dickdreamer() {
  std::cin >> n;
  b = sqrt(n);
  solve1(), solve2();
  int ans = 0;
  for (int i = 0; i <= n; ++i) inc(ans, 1ll * f[i] * g[n - i] % kMod);
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:kMod,LOJ,题解,sqrt,int,ret,bs,物品,计数问题
From: https://www.cnblogs.com/Scarab/p/18390883

相关文章

  • 学校训练赛的一些题解
    第二十一届宁波大学程序设计竞赛(重现赛链接)C游戏开发部的小游戏(C)赛时并没有写出来,果然dp还得多练)将所有石头视为容量为\(n\)的背包,每堆石头的数量即背包中物品的质量,对于\(a_i\leqf_i\leqb_i\),由于\(f_i\)最终取值唯一,可当作分组背包处理。将大小为\(i\)的\(t\)......
  • CCF-CSP 2024 --重塑矩阵1,2c语言题解
     创作想法是因为像我当初大一时候想参加一些比赛但是奈何只学了c和c相关数据结构,但是对于许多竞赛的题目的题解往往都是c++或者其他面向对象的编程语言,让我们难以在c语言基础上入手这些比较复杂的题目。 创造的目的是为了帮助各位同时提高我对c语言编程的理解和锻炼个人......
  • CSP-J 2020 初赛试题解析(第一部分:单项选择题(5-10))
    ......
  • 【秋招笔试】8.30饿了么秋招(算法岗)-三语言题解
    ......
  • Leetcode 第 408 场周赛题解
    Leetcode第408场周赛题解Leetcode第408场周赛题解题目1:3232.判断是否可以赢得数字游戏思路代码复杂度分析题目2:3233.统计不是特殊数字的数字数量思路代码复杂度分析题目3:3234.统计1显著的字符串的数量思路代码复杂度分析题目4:3235.判断矩形的两个角落是否......
  • 【C语言进阶】C语言指针进阶实战:优化与难题解析
    ......
  • 【题解】拆分
    题目描述【题目描述】鸡尾酒又带着大家学习新定义啦!今天要学习的内容是集合的mex,集合的mex指的是一个集合没有出现过的最小自然数。例如,mex({1,2})=0、mex({0,1,2,3})=4。现在你有一个包含n个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合......
  • 题解:CF916D Jamie and To-do List
    题意维护一个数据结构,支持以下几种操作:setaixi:设置任务\(a_i\)的优先级为\(x_i\),如果该列表中没有出现则加入该任务。removea_i:删除该任务。querya_i:求优先级比\(a_i\)小的任务个数,如果没有则输出\(-1\)。undosum:删除此次操作之前的\(sum\)次操作。分析前......
  • 题解:CF916B Jamie and Binary Sequence (changed after round)
    题意把一个数分解成恰好\(k\)个\(2^{a_i}\)次方的和,可以重复,要求保证最大的\(a_i\)要尽可能的小时,\(a\)的字典序尽可能大,输出序列\(a\)。分析首先我们借助二进制拆出一个满足\(n=\sum2^{a_i}\)序列\(a\),满足\(a\)的长度最小。若此时\(a\)的长度大于\(k\),显......
  • 题解:CF914C Travelling Salesman and Special Numbers
    题意定义\(\operatorname{popcount}(x)\)为\(x\)二进制下\(1\)的个数。定义对\(x\)的一次操作:\(x\gets\operatorname{popcount}(x)\),显然任意正整数经过若干次操作后会变为\(1\)。给定\(n\)和\(k\),其中\(n\)是在二进制下被给出,求出所有不大于\(n\)且将其变为......