题目大意
有 Q 种操作。
1、加入一个魔力为 x 的宝石；
2、删去一个魔力为 x 的宝石（保证操作合法）；
3、询问有多少种选取宝石的方法，使得选取的魔力和为 x；（不同下标的宝石视为不同，即两种方法不同当且仅当两种方法选取的宝石有不同）
4、询问有多少种选取宝石的方法，使得选取的魔力和为 x。（不同魔力的宝石视为不同，即两种方法不同当且仅当某一种魔力值的宝石数量不同）
Q, x<=10^4，时限 3s。
解法1
这种东西肯定先想到 dp。
设 f[i] 表示操作3条件下，魔力和为 i 的方案数；设 g[i] 表示操作4的方案数。f 是个01背包，而 g 是个多重背包。
然后这就是个动态dp了。
f 的维护比较简单，插入就倒着扫一遍，删除就正着扫一遍。
g 的维护比较麻烦，主要是它的转移跟数量有关。实现程序时瞎搞一下也可以使其成为线性。
一次dp是 O(x) 的，所以总时间是 O(Qx)。
解法2
考虑dp的生成函数。贴题解了。
以下的 $cnt[i]$ 表示魔力值为 i 的宝石数量，$f[i][j]$ 表示01背包的dp
代码
解法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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include<cstdio>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long LL;
const int maxn=1e4+5;
const LL mo=1e9+7;
int n,cnt[maxn];
LL f[maxn],g[maxn];
int ReadInt()
{
char ch=getchar();
int data=0;
while (ch<'0' || ch>'9') ch=getchar();
do{
data=data*10+ch-'0';
ch=getchar();
} while (ch>='0' && ch<='9');
return data;
}
char ReadChar()
{
char ch=getchar();
while (ch!='i' && ch!='q' && ch!='d' && ch!='R' && ch!='T') ch=getchar();
return ch;
}
LL gj[maxn],gp[maxn];
void NewG(int x,int z)
{
if (cnt[x])
{
fo(i,0,x-1) gj[i]=g[i];
fo(i,x,n)
{
g[i]=(g[i]-gj[i-x]+mo)%mo;
gj[i]=(gj[i-x]+g[i])%mo;
if (i-cnt[x]*x>=0) gj[i]=(gj[i]-g[i-cnt[x]*x]+mo)%mo;
}
}
cnt[x]+=z;
if (cnt[x])
{
memcpy(gp,g,sizeof(g));
fo(i,0,x-1) gj[i]=gp[i];
fo(i,x,n)
{
g[i]=(g[i]+gj[i-x])%mo;
gj[i]=(gj[i-x]+gp[i])%mo;
if (i-cnt[x]*x>=0) gj[i]=(gj[i]-gp[i-cnt[x]*x]+mo)%mo;
}
}
}
int Q;
int main()
{
n=10000;
f[0]=g[0]=1;
scanf("%d",&Q);
while (Q--)
{
char ty=ReadChar();
if (ty=='i')
{
int x=ReadInt();
fd(i,n,x) f[i]=(f[i]+f[i-x])%mo;
NewG(x,1);
} else if (ty=='d')
{
int x=ReadInt();
fo(i,x,n) f[i]=(f[i]-f[i-x]+mo)%mo;
NewG(x,-1);
} else
{
char now=ReadChar();
int x=ReadInt();
printf("%lld\n",(now=='T') ?f[x] :g[x] );
}
}
}
|
