D.小红不想做完全背包 (hard)
多源同余最短路做法:
考虑到以所有a[i]%p为起点,初始化使dis[a[i]%p]=1
那么终点即为dis[0]
具体代码如下:
#include<bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10,mod=1e9+7,inf=0x3f3f3f3f3f3f3f3f,P=131;
vector<PII>e[N];
int dis[N],vis[N];
void dijkstra(int n)
{
priority_queue<PII,vector<PII>,greater<PII>> q;
for(int i=0;i<n;i++)
{
if(dis[i])q.push({dis[i],i});
else dis[i]=inf;
}
while(q.size())
{
int t=q.top().y;
q.pop();
if(vis[t])continue;
vis[t]=1;
for(auto i:e[t])
{
if(dis[t]+i.y<dis[i.x])
{
dis[i.x]=dis[t]+i.y;
q.push({dis[i.x],i.x});
}
}
}
}
void solve(int T)
{
int n,p;
cin>>n>>p;
vector<int>a(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(int j=0;j<p;j++)
{
e[j].push_back({(j+a[i])%p,1});
}
dis[a[i]%p]=1;
}
dijkstra(p);
cout<<dis[0]<<endl;
}
signed main()
{
bool multitest=0;
//cout<<setiosflags(ios::fixed),cout.precision(2);
ios::sync_with_stdio(false),cin.tie(nullptr);
int _t=1;
if(multitest)cin>>_t;
for(int i=1;i<=_t;i++)
{
solve(i);
}
return 0;
}