一个经典的 modular subset
背包，但是我之前完全没听说过这个啊
但是不影响这是喵喵题。
题目链接
题意
给一个质数 和
个在 间的整数。
要求从中挑出 个数，使得和为
的倍数。
构造方案或判断无解。
题解
有解证明
可以证明给定条件下一定有解，证明如下：
首先若某一种数字出现次数 ，则直接选
个这个数字即可。
否则的话，我们每一次将出现次数最大和次大的数字放在一起配一对。
这样所有数字会被配成
对。
可以证明，配成的每一对中，同一对的两个数字不同。
现在设剩余的单点为 ，配成的第
对为 。
考虑构造一个方案，使得每一对里面恰好选了一个数字，并且单点恰好被选了。
显然，这样选的所有方案一定恰好选了 个数字（废话
下面证明，
间的所有整数，都存在至少一种这样的构造。
首先，显然存在一个方案，是 ，我们定义集合 。
好，我们发现这唯一的方案中，如果使用 替换 ，那么会多出一个方案。
那么现在我们就有两个方案，，有
那再来看第二对数字 ，我们发现 中的方案都使用了 而没有使用 。
那么对于部分 中的方案，使用
替换 ，又会得到新方案，我们定义目前所有的方案为
。
......
对于一个方案的集合
来说，我们发现他们在第
对中，都使用了 而不是 。
那么我们就可以将部分
中的方案拿出来，用 替换 ，得到新的方案。
那么我们就可以令当前所有方案构成的集合为 。
那么，这一步会产生多少新方案呢？
假设，这一步不会产生新方案，令 。
因为 ，所以一定存在一个最小的 使得 。
由于这一步不会产生新方案，那么也就是说 。
又因为
也在原来的方案中，并且这种方案替换了后也不会产生新方案，说明 。
同理，可以证明对于任意整数 ，。
因为
为一个质数，所以此时一定有 。
换句话说，若此时
不是满集，则替换后，最少会多出一种方案。
即 。
则 。
也就是说，我们仅用这种构造，可以构造出所有的数字！
所以一定有解。
构造方案
首先一个显然的解法，根据上面的分组完之后，使用 bitset
优化背包，并记录方案。
时间复杂度是
的，期望得分 。
这样暴力转移太不优雅了，那么根据我们上面的过程，我们能不能每一次只转移一个值呢？
设 表示选完了前 对数，使得所有数的和模 余 是否可行。
那么我们上面所说的，其实就是令所有 ，。
并选出一个 进行 。
这里的主要问题，在于找到一个合法的 。
我们发现，在进行第二种转移前，一定有 ，即 。
且必须要有 。
（从以下开始，我们使用
表示原来的 ）
考虑找到一个最小的 满足 ，考虑二分判断是否有 。
则 。
我们可以使用树状数组维护哈希值，来进行判断两个区间是否相等。
但是这样做可能会有一个问题，就是我们找到的 可能出现
的情况。
这个时候我们可以稍微转换一下思路，默认我们之前的方案全部选择了 ，只有这一个方案选择了 ，这样就可以使得后者向前者转移（实际上可以看成交换了
与 的值）。
这样的话，对于每一个 ，我们恰好只转移了一个地方，但是找这个地方所用的时间复杂度为
。
这个 dp 方法构造方案是容易的，总时间复杂度为 。
真是一道喵喵题
代码
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
template<typename A>
using vc=vector<A>;
const int mod=998244353;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int c[300001];
bool dp[300001];
bool def[300001];
ll p[600001];
ll t[600001];
vc<int>pos[300001];
int now[300001];
int cnt[300001];
int a[300001];
int b[300001];
int sum;
int n;
inline void choose(int v)
{
printf("%d ",pos[v][now[v]++]);
}
inline void init()
{
priority_queue<pi>que;
for(int i=0;i<n;i++) que.push(pi(cnt[i],i));
for(int i=1;i<n;i++)
{
auto u=que.top();que.pop();
auto v=que.top();que.pop();
a[i]=u.second,b[i]=v.second;
if(u.first!=1) que.push(pi(u.first-1,u.second));
if(v.first!=1) que.push(pi(v.first-1,v.second));
}
choose(que.top().second);
sum=que.top().second;
}
inline int lowbit(int i)
{
return i&(-i);
}
inline void Add(int id)
{
dp[id]=1;
int x=id+1;
while(x<=2*n)
{
t[x]=(t[x]+p[id])%mod;
x+=lowbit(x);
}
x=id+n+1;
while(x<=2*n)
{
t[x]=(t[x]+p[id+n])%mod;
x+=lowbit(x);
}
}
inline ll get(int x)
{
ll ans=0;
x++;
while(x)
{
ans=(ans+t[x])%mod;
x-=lowbit(x);
}
return ans;
}
inline ll get(int l,int r)
{
return (get(r)-get(l-1)+mod)%mod;
}
inline int check(int v)
{
int ans=-1;
for(int i=262144;i;i>>=1) if(ans+i<n&&get(0,ans+i)*p[v]%mod==get(v,ans+v+i)) ans+=i;
return (ans+1)%n;
}
inline void output(int i,int j)
{
if(!i) return ;
if(c[i]==j)
{
if(def[i]==0) choose(b[i]),output(i-1,(j-b[i]+a[i]+n)%n);
else choose(a[i]),output(i-1,(j+b[i]-a[i]+n)%n);
}
else
{
if(def[i]==0) choose(a[i]),output(i-1,j);
else choose(b[i]),output(i-1,j);
}
}
inline void solve()
{
p[0]=1;
for(int i=1;i<=2*n;i++) p[i]=p[i-1]*3%mod;
Add(0);
for(int i=1;i<n;i++)
{
int v=(b[i]-a[i]+n)%n;
int w=check(v);
int to=(w+v)%n;
if(dp[w])
{
def[i]=0,sum=(sum+a[i])%n;
c[i]=to;
Add(to);
}
else
{
def[i]=1,sum=(sum+b[i])%n;
c[i]=w;
Add(w);
}
}
output(n-1,(n-sum)%n);
}
int main()
{
n=read();
for(int i=1;i<2*n;i++)
{
int a=read()%n;
pos[a].push_back(i);
cnt[a]++;
}
for(int i=0;i<n;i++)
{
if(cnt[i]>=n)
{
for(int j=0;j<n;j++) choose(i);
return 0;
}
}
init();
solve();
return 0;
}
|
感谢观看！