基础理解:
- 不是一种算法，而是一种思路，一种优化方式。用同余来构造某些状态，来优化时间空间复杂度（多用来优化dp）
-
最短路常用spfa，不会被卡，因为同余的特殊构造，可保证spfa的时间复杂度（听大佬说的，我不会证）
- 主要用于给定 n个整数，求这 n个整数能拼凑出多少的其他整数（n个整数可以重复取），以及给定 n个整数，求这 n个整数不能拼凑出的最小（最大）的整数，或者至少要拼几次才能拼出模 K余 p 的数的问题。
难度：简单（易理解易实现）
例题引入：https://www.luogu.com.cn/problem/P3403
- 简要题意：给你4个数h,x,y,z。求满足ax+by+cz=jg中a,b,c都是非负整数且小于h的jg的个数。
- 考虑bfs,每出队列一个数就加x或加y或加z,再重新加入队列，只要不大于h且没有被标记。一看数据范围h<2^63-1,直接炸开。
- 考虑选定x,每一个符合条件的数%x在0到x之间。则每一个符合条件的数可以写成kx+r(r为%x的余数)，对于每一个余数i，只用求出用x,y,z凑出最小的%x==i的数s，答案+=(h-s)/x+1，表示统计s,s+x,s+2*x,s+3*x.....
- 正确性显然，每个%x==i的都统计完了，且不同i之间一定不重复。
- 考虑实现，设dp[i]存凑出的最小的%x==i的数，显然有dp[(i+y)%x]=min(dp[(i+y)%x],dp[i]+y)和dp[(i+z)%x]=min(dp[(i+z)%x],dp[i]+z)。观察式子，发现与求最短路相同极为相似，再要从i向(i+y)%x和(i+z)%x连边跑最短即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define ll long long
ll h,dp[N],ans,nxt[2*N],go[2*N],jz[2*N],hd[N],x,y,z;
int tot;
bool vis[N];
queue<int> q;
void add(int x,int y,int z)
{
nxt[++tot]=hd[x];go[tot]=y;jz[tot]=z;hd[x]=tot;
return ;
}
void spfa()
{
q.push(1%x);
vis[1%x]=1;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=0;
for(int i=hd[u];i;i=nxt[i])
{
int v=go[i];
if(dp[v]>dp[u]+jz[i])
{
dp[v]=dp[u]+jz[i];
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
}
int main()
{
memset(dp,0x3f,sizeof(dp));
scanf("%lld",&h);
scanf("%lld%lld%lld",&x,&y,&z);
if(x==1||y==1||z==1)
{
printf("%lld",h);
return 0;
}
for(int i=0;i<x;i++)
{
add(i,(i+y)%x,y);
add(i,(i+z)%x,z);
}
dp[1%x]=1;
spfa();
for(int i=0;i<x;i++)if(dp[i]<=h)ans+=(h-dp[i])/x+1;
printf("%lld\n",ans);
return 0;
}
举一反三：
https://www.luogu.com.cn/problem/P2371
发现上面的问题只是从3个数变成n个数，仿造做即可
#include <bits/stdc++.h>
using namespace std;
const int N=20,M=5e5+10;
const long long INF=1e12+10;
int n,tot,nxt[20*M],hd[M],go[20*M],jz[20*M],a[N],mi=0x3f3f3f3f;
long long ans1,ans2,dp[M],l,r;
bool vis[M];
void add(int x,int y,int z)
{
nxt[++tot]=hd[x];go[tot]=y;jz[tot]=z;hd[x]=tot;
return ;
}
queue<int> q;
void spfa()
{
dp[0]=0;
q.push(0);
vis[0]=1;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=0;
for(int i=hd[u];i;i=nxt[i])
{
int v=go[i];
if(dp[v]>dp[u]+jz[i])
{
dp[v]=dp[u]+jz[i];
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
}
int main()
{
scanf("%d%lld%lld",&n,&l,&r);l--;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]<mi)mi=a[i];
}
for(int i=0;i<mi;i++)
{
dp[i]=INF;
for(int j=1;j<=n;j++)
{
add(i,(i+a[j])%mi,a[j]);
}
}
spfa();
for(int i=0;i<mi;i++)
{
if(l>=dp[i])ans1+=(l-dp[i])/mi+1;
if(r>=dp[i])ans2+=(r-dp[i])/mi+1;
}
printf("%lld\n",ans2-ans1);
return 0;
}
https://www.luogu.com.cn/problem/P2662
这道题与上面有所不同，求最大的不能被凑成的数，考虑从dp[i]中快速求出，因为定义dp[i]为最小的%x==i的数，所以%x==i最大的不能被凑出的数是dp[i]-x，对每一个i取最大值就是结果。再判一下无解即可。
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,a[5000010],mi=0x3f3f3f3f,cnt;
long long ans1,dp[5000010];
bool vis[5000010];
queue<int> q;
void spfa()
{
dp[0]=0;
q.push(0);
vis[0]=1;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=0;
for(int j=1;j<=cnt;j++)
{
if(a[j]==mi)continue;
int v=(u+a[j])%mi;
if(dp[v]>dp[u]+a[j])
{
dp[v]=dp[u]+a[j];
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[++cnt]);
int x=a[cnt];
for(int i=1;i<=m;i++)
{
if(x>=i)
{
a[++cnt]=x-i;
if(x-i<mi)mi=x-i;
}
}
}
if(mi<=1)
{
printf("-1\n");
return 0;
}
for(int i=0;i<mi;i++)dp[i]=INF;
spfa();
for(int i=0;i<mi;i++)
{
if(dp[i]==INF)
{
printf("-1\n");
return 0;
}
ans1=max(ans1,dp[i]-mi);
}
printf("%lld\n",ans1);
return 0;
}
实现上的优化:
- 选用所有值中最小的一个做模数会提高时间复杂度
- 空间开不下时，不存边，在spfa时枚举使用。
- 一定注意赋的极大值和变量的类型。
标签：jz,int,短路,tot,vis,long,dp,同余 From： https://www.cnblogs.com/storms11/p/17761396.html