「51nod1597」有限背包计数问题

Description

你有一个大小为nn的背包,你有nn种物品,第ii种物品的大小为ii,且有ii个,求装满这个背包的方案数有多少
两种方案不同当且仅当存在至少一个数ii满足第ii种物品使用的数量不同

Input

第一行一个正整数nn

Output

一个非负整数表示答案,你需要将答案对2333333323333333取模

Sample Input

1
3

Sample Output

1
2

HINT

1n1051\leq n\leq 10^5

Solution

对于ini\leq \sqrt{n},直接fi,jf_{i,j}表示[1,i][1,i]中凑成容量为jj的方案数。用完全背包+容斥来计算有个数限制。
对于in+1i\ge \sqrt{n}+1gi,jg_{i,j}表示用了i\leq i,容量为jj的方案数。每一次加入一个n+1\sqrt{n}+1或者所有使用的数字都+1+1,自己意会一下这个过程吧!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 100010;
ll p = 23333333;
int n;
void add(int &x, int v) {
x += v;
if(x >= p) x %= p;
}
bool c;
int f[2][N];
int g[320][N];
int main() {
n = read();
int t = sqrt(n);
f[0][0] = 1;
f[1][0] = 1;
for(int i = 1; i <= t; ++i) {
c ^= 1;
for(int j = 1; j <= n; ++j) {
f[c][j] = f[c ^ 1][j];
if(j >= i) add(f[c][j], f[c][j - i]);
if(j >= i * i + i) add(f[c][j], p - f[c ^ 1][j - i * i - i]);
}
}
g[0][0] = 1;
for(int i = 0; i <= t; ++i)
for(int j = 0; j <= n; ++j) {
if(i && j + i <= n) add(g[i][j + i], g[i][j]);
if(j + t + 1 <= n) add(g[i + 1][j + t + 1], g[i][j]);
}
++g[1][0];
int ans = 0;
for(int i = 1; i <= t; ++i)
for(int j = 0; j <= n; ++j)
add(ans, (ll)f[c][j] * g[i][n - j] % p);
writeln(ans);
return 0;
}