OI - 货币系统(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 货币系统(LOJ)

发表于 分类于 Valine：

一道不算难的题居然可以挖出这么多东西……

# 题面

点击展开/折叠题面

一共有 n 种面额不同的货币，第 i 种面额为 $a_i$；这 n 种货币构成一个货币系统。如果这 n 种货币（每种货币使用任意多次）恰好能够支付金额 b，则称“该货币系统可以表示 b”。

现给出该货币系统，求出一个包含货币种类数最少的货币系统，使得任意金额要么两个系统都不能表示，要么两个系统都可以表示。输出最少的货币种类数。

# 解析

- 线性空间（用来证明一些性质）

对于货币系统 $\{a_i\}$，定义它的“表示集合”：

其实就是一个线性空间，数集 $F$ 是非负整数集、$V=\{a_i\}$ 是定义在 $F$ 上的线性空间，那么 $B$ 就是 $V$ 的张成 $\operatorname{span}(V)$。

要求出另一个 $V’$ 使得 $\operatorname{span}(V’)=\operatorname{span}(V)$，则根据线性空间的性质，$V’$ 是 $V$ 的极大线性无关组——基。

也就是说 $V’\subset V$ 且对于任意 $a\in V’$ 不能被 $V-\{a\}$ 线性表出。

- 完全背包

有了线性空间的性质，背包起来就容易多了——其实只需要删去 $a\in V$ 且可以被 $V-\{a\}$ 线性表出的 a 即可。

由于数集是非负整数，a 一定是被比它小的数线性表出的。则我们从小到大枚举 $a_i$，顺便维护当前能够线性表出的集合——就是一个完全背包，每次用 $a_i$ 去更新背包状态，这里可以用 bitset 优化，但是没啥必要……如果枚举到的 $a_i$ 已经可以被线性表出，那么就删掉它。

设 $m=\max\{a_i\}$，则复杂度为 $O(nm)$，比较简单、也是网上常见的做法，就不提供代码了。

- 生成函数

完全背包本质上就是个生成函数——我们可以定义如下生成函数：

那么 $H(x)$ 第 $i$ 次项系数就是 $i$ 能够被多少种方案线性表出。根据线性空间的结论，$a_i\in V’$ 不能被 $V-\{a_i\}$ 线性表出，那么如果 $a_i\in V’$，则 $a_i$ 只能被 $V$ 用一种方法线性表出——即它本身。对应到 $H(x)$ 则是第 $a_i$ 次项系数为 1。

但是直接上 NTT 是 $O(nm\log m)$，并跑不过（本来常数就大）。

然后就有一个比较常规但是挺巧妙的操作：

只写到这一步还不够——根据泰勒展开（也可以用微积分硬推，但是tly告诉我这就是泰勒展开）：

于是

然后可以调和级数 $O(m\log m)$ 处理出 exp 后面的式子，然后再 $O(m\log m)$ 做个 exp。但是……多项式常数还是大啊，LOJ 卡 80pt。

- 同余最短路

第一次见到 :)

同余最短路的一个用法就是求哪些数可以被 $\{a_i\}$ 表示（可以用无限多次）。

首先非常显然的，如果 $x$ 可以被 $V$ 表示，那么 $x+a_i$ 也可以被表示。定义 $a_i$ 的剩余系 $[a_i]=\{0,1,\dots,a_i-1\}$，则设 $d(x)$ 表示 $V$ 的张成中最小的模 $a_i$ 余 x 的数，即 $d(x)=\min\limits_{b\bmod a_i=x}b(b\in\operatorname{span}(V))$，则有

并且我们发现，$\operatorname{span}(V)=\operatorname{span}(V’)$ 当且仅当 V 和 V’ 在 $a_i$（$a_i\in V\cap V’$）的剩余系下 $d(x)$ 完全相同。证明非常简单，因为 $d(x)\bmod a_i=x$，如果存在 $d(x)$ 在 V 和 V’ 中不同，例如 V 中 $d(x)$ 比 V’ 中小，则 V 的 $d(x)$ 一定不能在 V’ 中被表示。换句话说，$d(x)$ 是 V 中能够被表示出的模 $a_i$ 余 x 的最小的数。

如何求 $d(x)$？可以想到最短路——点集 $V$、有向边集 $E$：

比较直观，以 $v_i$ 为源点跑一个最短路，$v_i$ 与 $v_{x}$ 的距离就是 $d(x)$。

根据线性空间，现在要从 V 中删除一些数得到 V’ 使得 $\operatorname{span}(V)=\operatorname{span}(V’)$。我们知道 $a_1$（假设 ${a_i}$ 是升序）一定同时在 $V$ 和 $V’$ 中，所以选定 $a_1$ 作为剩余系模数，建图。相当于在原图上删掉一些边，使得最短路不变，求剩下的边中不同长度的边的数量最小是多少。

那么在做最短路的时候，我们储存一下点 $v_x$ 的最短距离是从哪种边权的边转移过来的，记作 tra[x]。如果有多种转移方式，则取边权最小的作为 tra[x]，这样可以使剩下的边权的数量最小。特别的，tra[0]=-1（初始值，没有任何转移的边）。

最后求 tra[] 数组有多少种不同的值即可。

# 源代码

- 生成函数 80pt

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=524288,MOD=998244353;

#define cs const int &
#define mem(a) (memset(a,0,sizeof a))
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}

namespace POLY{
	const int G=3;
	#define clean(A,l,r) std::fill(A+(l),A+(r),0)
	int rev[N],powg[30],invg[30],lg2[N],inv[N];
	int fac[N],ifac[N];
	void Init(int siz){
		for(int i=2;i<=siz;i++) lg2[i]=lg2[i>>1]+1;
		for(int i=0;i<=20;i++) powg[i]=Pow(G,(MOD-1)>>i),invg[i]=Pow(powg[i],MOD-2);
		inv[1]=1;
		fac[0]=1;for(int i=1;i<=siz;i++) fac[i]=Mul(fac[i-1],i);
		ifac[siz]=Pow(fac[siz],MOD-2);for(int i=siz-1;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
		for(int i=1;i<=siz;i++) inv[i]=Mul(ifac[i],fac[i-1]);
	}
	inline void NTT(int *A,cs len,cs typ){
		int lgl=lg2[len];
		register int i,j;
		for(i=1;i<len;i++){
			rev[i]=rev[i>>1]>>1|((i&1)<<(lgl-1));
			if(i<rev[i]) std::swap(A[i],A[rev[i]]);
		}
		for(register int l=2,t=1,lgn=1;l<=len;l<<=1,lgn++,t<<=1){
			int per=typ==1?powg[lgn]:invg[lgn];
			for(j=i=0;i<len;j=(i+=l))
				for(int cur=1;j<i+t;j++,cur=Mul(cur,per)){
					int tmp=Mul(cur,A[j+t]);
					A[j+t]=Sub(A[j],tmp);
					A[j]=Add(A[j],tmp);
				}
		}
		if(typ==1) return;
		int invn=inv[len];
		for(i=0;i<len;i++) A[i]=Mul(A[i],invn);
	}
	void Copy(int *A,int *B,cs len){for(register int i=0;i<len;i++) B[i]=A[i];}
	void InvPoly(int len,int *A,int *B){
		if(len==1){B[0]=Pow(A[0],MOD-2);return;}
		InvPoly((len+1)>>1,A,B);
		int Len=1;
		while(Len<(len<<1)) Len<<=1;
		static int tmp[N];
		Copy(A,tmp,len),clean(tmp,len,Len);
		clean(B,(len+1)>>1,Len);
		NTT(tmp,Len,1),NTT(B,Len,1);
		for(register int i=0;i<Len;i++) B[i]=Mul(Sub(2,Mul(tmp[i],B[i])),B[i]);
		NTT(B,Len,-1);
		clean(B,len,Len);
	}
	void Derv(int *A,int *B,cs len){
		for(int i=0;i<len-1;i++) B[i]=Mul(A[i+1],i+1);
		B[len-1]=0;
	}
	void Inte(int *A,int *B,cs len){
		for(int i=1;i<=len;i++) B[i]=Mul(inv[i],A[i-1]);
		B[0]=0;
	}
	void Ln(int *A,int len,int *B){
		static int tmp1[N],tmp2[N];mem(tmp1),mem(tmp2);
		Derv(A,tmp1,len);
		InvPoly(len,A,tmp2);
		int Len=1;
		while(Len<len*2) Len<<=1;
		NTT(tmp1,Len,1),NTT(tmp2,Len,1);
		for(int i=0;i<Len;i++) tmp1[i]=Mul(tmp1[i],tmp2[i]);
		NTT(tmp1,Len,-1),clean(tmp1,len-1,Len);
		Inte(tmp1,B,len-1);
	}
	void EXP(int len,int *A,int *B){
		static int tmp3[N];
		if(len==1){B[0]=1;return;}
		EXP((len+1)>>1,A,B);
		Ln(B,len,tmp3);
		for(int i=0;i<len;i++) tmp3[i]=Sub(A[i],tmp3[i]);
		tmp3[0]=Add(tmp3[0],1);
		int Len=1;
		while(Len<(len<<1)) Len<<=1;
		clean(tmp3,len,Len),NTT(tmp3,Len,1);
		clean(B,len,Len),NTT(B,Len,1);
		for(int i=0;i<Len;i++) B[i]=Mul(B[i],tmp3[i]);
		NTT(B,Len,-1);
		clean(B,len,Len);
	}
}

int n;
int A[N];
int p1[N],p2[N];

inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
int main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	POLY::Init(N-1);
	for(register int cas=Ri();cas;cas--){
		int n=Ri();
		for(register int i=1;i<=n;i++) A[i]=Ri();
		sort(A+1,A+1+n);
		int len=A[n]+1;
		mem(p1),mem(p2);
		for(register int i=1;i<=n;i++)
			for(register int j=1;j*A[i]<len;j++)
				p1[j*A[i]]+=POLY::inv[j];
		POLY::EXP(len,p1,p2);
		int ans=n;
		for(register int i=1;i<=n;i++)
			if(p2[A[i]]>1)
				ans--;
		printf("%d\n",ans);
	}
	return 0;
}

- 同余最短路

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
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=105,M=2.5E4+10;

int n,A[N];
int dis[M],tra[M];
bool fix[M];

struct GRAPH{
	int head[M],nxt[N*M],to[N*M],val[N*M],ncnt;
	void AddEdge(int u,int v,int key){
		ncnt++;
		nxt[ncnt]=head[u],to[ncnt]=v,val[ncnt]=key,head[u]=ncnt;
	}
	int operator [](const int &u){return head[u];};
	void Clear(int siz){
		for(int i=0;i<=siz;i++){
			dis[i]=(1<<29);
			tra[i]=(1<<29);
			head[i]=0;
			fix[i]=false;
		}
		ncnt=0;
	}
}Gr;

inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
priority_queue< pair<int,int> > que;
void Dijkstra(){
	que.push(make_pair(dis[0]=0,0));
	while(!que.empty()){
		int u=que.top().second;que.pop();
		if(fix[u]) continue;
		fix[u]=true;
		for(int it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it];
			if(dis[v]<=dis[u]+Gr.val[it]){
				if(dis[v]==dis[u]+Gr.val[it]) tra[v]=min(tra[v],Gr.val[it]);
				continue;
			}
			dis[v]=dis[u]+Gr.val[it];
			tra[v]=Gr.val[it];
			que.push(make_pair(-dis[v],v));
		}
	}
}
int main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	for(int cas=Ri();cas;cas--){
		n=Ri();
		for(int i=1;i<=n;i++) A[i]=Ri();
		sort(A+1,A+1+n);
		Gr.Clear(A[1]);
		for(int i=2;i<=n;i++)
			for(int u=0;u<A[1];u++)
				Gr.AddEdge(u,(u+A[i])%A[1],A[i]);
		Dijkstra();
		sort(tra,tra+A[1]);
		int ans=unique(tra,tra+A[1])-tra;
		printf("%d\n",ans);
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 离忧-网易云