十分神奇的思路。
为了优化要选择minnum作为模数。
复杂度十分神奇 并不会证qaqq
1 #include<bits/stdc++.h> 2 #define re register int 3 #define LL long long 4 #define maxn 12+5 5 #define maxn1 500000+5 6 #define maxn2 6000000+5 7 using namespace std; 8 9 10 11 int n; 12 int num[maxn]; 13 bool vis[maxn1]; 14 LL bmin,bmax; 15 LL dis[maxn1]; 16 struct edge 17 { 18 int nex,to,w; 19 }ed[maxn2]; 20 int head[maxn1]; 21 int cnt,mintmp; 22 void add(int x,int y,int w) 23 { 24 ed[++cnt].to=y; 25 ed[cnt].nex=head[x]; 26 ed[cnt].w=w; 27 head[x]=cnt; 28 } 29 queue<int>q; 30 void spfa() 31 { 32 for(re i=0;i<mintmp;i++) 33 dis[i]=1926081700000; 34 q.push(0); 35 vis[0]=true; 36 dis[0]=0; 37 //cout<<dis[1]<<endl; 38 while(!q.empty()) 39 { 40 int u=q.front(); 41 q.pop(); 42 vis[u]=false; 43 for(re i=head[u];i;i=ed[i].nex) 44 if(dis[ed[i].to]>dis[u]+ed[i].w) 45 { 46 dis[ed[i].to]=dis[u]+ed[i].w; 47 if(!vis[ed[i].to]) { 48 q.push(ed[i].to); 49 vis[ed[i].to]=true; 50 } 51 } 52 } 53 } 54 LL query(LL x)//LL x 55 { 56 LL ans=0; 57 for(re i=0;i<mintmp;i++) 58 if(dis[i]<=x) ans+=(x-dis[i])/mintmp+1; 59 //是<=而不是！=1926081700000 60 return ans; 61 } 62 int main() 63 { 64 ios::sync_with_stdio(false); 65 cin>>n>>bmin>>bmax; 66 mintmp=maxn1; 67 for(re i=1;i<=n;i++) 68 { 69 cin>>num[i]; 70 if(num[i]) 71 mintmp=min(mintmp,num[i]); 72 } 73 for(re j=0;j<mintmp;j++) 74 for(re i=1;i<=n;i++) 75 if(num[i]!=mintmp) 76 add(j,(num[i]+j)%mintmp,num[i]); 77 //由j向（num[i]+j)%mintmp连边 78 spfa(); 79 LL sum=query(bmax)-query(bmin-1); 80 // cout<<query(bmax)<<endl; 81 // cout<<query(bmin-1)<<endl; 82 cout<<sum; 83 return 0; 84 }