https://ac.nowcoder.com/acm/contest/625/B
Analysis:
All status is only 1<< 18, so we can preprocess f[u][j], and then build a state diagram of all the states that u can transfer;
There is a priority queue to search
There is a pitfall to be noted here, the array f[i][j], yes Can not open to long long, this will burst the memory; but f[i][j-1]* f[i][j-1] This operation will burst int, so we need to change
< p>f[i][j-1]* f[i][j-1] becomes long long 1ll*f[i][j-1]* f[i][j-1] Then go to mod
#include; bool vabook[maxn],vis[maxn]; int f[maxn][20]; int fa[maxn]; int dis[maxn]; struct no {int v; int val; bool operator <(const no &x) const {return< /span> x.val<val;} }P; vector
using namespace std; #define ll long long
const int maxn = 1<<18; const int mod = 19260817; const int INF = < span style="color: #800080;">0x3f3f3f3fG[maxn]; priority_queue ; int x; for(int< /span> i=1; i<=n; i++) {scanf(< span style="color: #800000;">"%d",&x); if(vabook[x]) T=1; vabook[x]=1< /span>;} if(T) {puts("0");return 0;} /// If the given number repeats, it must be 0 betterque; int main() {int n;scanf("%d",& n); bool T=< span style="color: #800080;">0
for(int i=0; i/// preprocess all F[i][j]
{f[i][0]=i; for(int j= 1; j<18; j++)/// a^4=a^2 * a^2, a^8=a^4*a^4;
{f[i][j] = (1ll*f[i][j-1]* f[i][j-1]) %mod;/ // first convert to long long and then go to mod
}} for(int u=0; u) { for(int j=0 ; j<18; j++) {int v=u^(1<<j); x = max(u,v); G[u].push_back({v, f[x][j]+1});///Create one Picture, record the status and value of u can be transferred
} if(vabook[u])///This is the point I own
{fa[u]=u; dis[u]=< span style="color: #800080;">0; que.push({u,0});} else {fa[u]=-1; dis[u ]=INF;}} ll ans=0x3f3f3f3f; //DJ shortest path
while(!que.empty()) {P=que.top(); que.pop(); int u=Pv; if(P.val>=ans) break;///If the smallest value of the current state is less than ans, then No need to update it
if(vis[u]) continue; vis[u]=1; for(int i=0 ; i) {int span> v=G[u][i].v; int w=< span style="color: #000000;">G[u][i].val; if(fa[v]!=- 1 && fa[v]!=fa[u]) {ans=min( ans,1ll*(dis[v]+w+dis[u])); // span>ans%=mod;
} if(dis[v]> w+dis[u]) {dis[v]=w+dis[u]; fa[v]=< span style="color: #000000;">fa[u]; que.push({v,dis[v]});}}} printf("%lld ",ans%mod); return 0< span style="color: #000000;">; }
View Code< /span>
#include; bool vabook[maxn],vis[maxn]; int f[maxn][20]; int fa[maxn]; int dis[maxn]; struct no {int v; int val; bool operator <(const no &x) const {return< /span> x.val<val;} }P; vector
using namespace std; #define ll long long
const int maxn = 1<<18; const int mod = 19260817; const int INF = < span style="color: #800080;">0x3f3f3f3fG[maxn]; priority_queue ; int x; for(int< /span> i=1; i<=n; i++) {scanf(< span style="color: #800000;">"%d",&x); if(vabook[x]) T=1; vabook[x]=1< /span>;} if(T) {puts("0");return 0;} /// If the given number repeats, it must be 0 betterque; int main() {int n;scanf("%d",& n); bool T=< span style="color: #800080;">0
for(int i=0; i/// preprocess all F[i][j]
{f[i][0]=i; for(int j= 1; j<18; j++)/// a^4=a^2 * a^2, a^8=a^4*a^4;
{f[i][j] = (1ll*f[i][j-1]* f[i][j-1]) %mod;/ // first convert to long long and then go to mod
}} for(int u=0; u) { for(int j=0 ; j<18; j++) {int v=u^(1<<j); x = max(u,v); G[u].push_back({v, f[x][j]+1});///Create one Picture, record the status and value of u can be transferred
} if(vabook[u])///This is the point I own
{fa[u]=u; dis[u]=< span style="color: #800080;">0; que.push({u,0});} else {fa[u]=-1; dis[u ]=INF;}} ll ans=0x3f3f3f3f; //DJ shortest path
while(!que.empty()) {P=que.top(); que.pop(); int u=Pv; if(P.val>=ans) break;///If the smallest value of the current state is less than ans, then No need to update it
if(vis[u]) continue; vis[u]=1; for(int i=0 ; i) {int span> v=G[u][i].v; int w=< span style="color: #000000;">G[u][i].val; if(fa[v]!=- 1 && fa[v]!=fa[u]) {ans=min( ans,1ll*(dis[v]+w+dis[u])); // span>ans%=mod;
} if(dis[v]> w+dis[u]) {dis[v]=w+dis[u]; fa[v]=< span style="color: #000000;">fa[u]; que.push({v,dis[v]});}}} printf("%lld ",ans%mod); return 0< span style="color: #000000;">; }
View Code< /span>
#include; bool vabook[maxn],vis[maxn]; int f[maxn][20]; int fa[maxn]; int dis[maxn]; struct no {int v; int val; bool operator <(const no &x) const {return< /span> x.val<val;} }P; vector
using namespace std; #define ll long long
const int maxn = 1<<18; const int mod = 19260817; const int INF = < span style="color: #800080;">0x3f3f3f3fG[maxn]; priority_queue ; int x; for(int< /span> i=1; i<=n; i++) {scanf(< span style="color: #800000;">"%d",&x); if(vabook[x]) T=1; vabook[x]=1< /span>;} if(T) {puts("0");return 0;} /// If the given number repeats, it must be 0 betterque; int main() {int n;scanf("%d",& n); bool T=< span style="color: #800080;">0
for(int i=0; i/// preprocess all F[i][j]
{f[i][0]=i; for(int j= 1; j<18; j++)/// a^4=a^2 * a^2, a^8=a^4*a^4;
{f[i][j] = (1ll*f[i][j-1]* f[i][j-1]) %mod;/ // first convert to long long and then go to mod
}} for(int u=0; u) { for(int j=0 ; j<18; j++) {int v=u^(1<<j); x = max(u,v); G[u].push_back({v, f[x][j]+1});///Create one Picture, record the status and value of u can be transferred
} if(vabook[u])///This is the point I own
{fa[u]=u; dis[u]=< span style="color: #800080;">0; que.push({u,0});} else {fa[u]=-1; dis[u ]=INF;}} ll ans=0x3f3f3f3f; //DJ shortest path
while(!que.empty()) {P=que.top(); que.pop(); int u=Pv; if(P.val>=ans) break;///If the smallest value of the current state is less than ans, then No need to update it
if(vis[u]) continue; vis[u]=1; for(int i=0 ; i) {int span> v=G[u][i].v; int w=< span style="color: #000000;">G[u][i].val; if(fa[v]!=- 1 && fa[v]!=fa[u]) {ans=min( ans,1ll*(dis[v]+w+dis[u])); // span>ans%=mod;
} if(dis[v]> w+dis[u]) {dis[v]=w+dis[u]; fa[v]=< span style="color: #000000;">fa[u]; que.push({v,dis[v]});}}} printf("%lld ",ans%mod); return 0< span style="color: #000000;">; }