昆山网站建设推荐,wordpress收费模版,网站排名5118,哪个公司的室内设计公司解析
不能在一条思路上死磕#xff01;
首先这题真正考的其实就是 p3p3p3。 乍一看题意#xff1a;给出一张特殊图#xff0c;求哈密顿回路方案数。 然后发现这个图性质不咋地。 然后就不会了。 …
正解根本和哈密顿回路毛关系也没有#xff01; 考虑从1-n依次插入。 注…解析
不能在一条思路上死磕
首先这题真正考的其实就是 p3p3p3。 乍一看题意给出一张特殊图求哈密顿回路方案数。 然后发现这个图性质不咋地。 然后就不会了。 …
正解根本和哈密顿回路毛关系也没有 考虑从1-n依次插入。 注意到插入i的时候我们其实只关注i-3,i-2,i-1不妨称其为“关键元素”互相之间是否相邻。 实现上由于有环所以可能还要记录最左和最右的关键元素是否靠边。 把这个状态状压下来直接转移即可。 口胡一时爽实现火葬场。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N1e6100;
const int inf1e9;
const int mod1e97;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k){ll res1;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}#define add(x,y) (xy,xmod?x-mod:0)int n,m,P;
bool ban[N][10];
int o5;
struct bruteforce{int ans,a[5];int vis[5];void dfs(int k){if(kn){bool flag1;for(int i1;in;i){if(abs(a[i]-a[i%n1])P||ban[a[i]][a[i]-a[i%n1]o]) flag0;}ansflag;return;}for(int i2;in;i){if(vis[i]) continue;a[k]i;vis[i]1;dfs(k1);vis[i]0;}return;}void work(){ans0;a[1]1;dfs(2);printf(%d\n,ans);return;}
}bf;
int aa[N];
inline bool check(){for(int i1;in;i){if(abs(aa[i1]-aa[i])P) return false;if(ban[aa[i]][aa[i]-aa[i1]o]) return false;}return true;
}
void work2(){ aa[1]aa[n1]1;int p,num1;for(p2;;p2){aa[num]p;if(pn){p--;break;}else if(pn-1){p;break;}}while(p1){aa[num]p;p-2;}int res0;rescheck();reverse(aa2,aa1n);rescheck();printf(%d\n,res);
}
const int bas4;
inline int Hash(int *x){int res0;for(int i1;i3;i) resres*basx[i];return res;
}
int a[5],tmp[10];
int tot,p[N][4],op1[N][3],op2[N][3],tr[N][5],vis[5];
//op1: xiang lin
//op2: kao bian
int id[1050][4][4];
void get(int x,int y){tot;for(int i1;i3;i) p[tot][i]a[i];op1[tot][0](x1)1;op1[tot][1]x1;op2[tot][0](y1)1;op2[tot][1]y1;id[Hash(a)][x][y]tot;//print(tot);
}
void dfs(int k,int x,int y){if(k3){get(x,y);return;}for(int i1;i3;i){if(vis[i]) continue;vis[i]1;a[k]i;dfs(k1,x,y);vis[i]0;}return;
}
inline int ins(int x,int pos){ int num0;int cur[4],cnt0;for(int i0;i3;i){ if(i){tmp[num]a[i]-1;}if(ipos){tmp[num]3;} if(i0!op2[x][0]) tmp[num]0;if(i1!op1[x][0]) tmp[num]0;if(i2!op1[x][1]) tmp[num]0;if(i3!op2[x][1]) tmp[num]0; }for(int i1;inum;i){if(tmp[i]) cur[cnt]i;}int f1(0),f2(0);if(cur[1]1cur[2]) f1|2;if(cur[2]1cur[3]) f1|1;if(cur[1]1) f2|2;if(cur[3]num) f2|1;num0;for(int i0;i3;i){if(i){if(a[i]1)tmp[num]a[i]-1;}if(ipos){tmp[num]3;}}return id[Hash(tmp)][f1][f2];
}
void solve(int x){memcpy(a,p[x],sizeof(p[x]));if(op2[x][0]op2[x][1]){tr[x][0]ins(x,0);tr[x][3]ins(x,3);}if(op1[x][0]) tr[x][1]ins(x,1); if(op1[x][1]) tr[x][2]ins(x,2);
}
int f[2][150],now,pre;
void init(int k){if(k3){f[now][id[Hash(a)][3][3]]1;return;}for(int i1;i3;i){if(vis[i]) continue;vis[i]1;a[k]i;init(k1);vis[i]0;}return;
}
inline bool prelink(int x,int pl){if(pl1) return op2[x][0]op2[x][1];else return op1[x][pl-2];
}
inline bool suflink(int x,int pl){if(pl3) return op2[x][0]op2[x][1];else return op1[x][pl-1];
}
void work3(){for(int i0;i3;i){for(int j0;j3;j){dfs(1,i,j);}}//debug(tot%d\n,tot);for(int i1;itot;i) solve(i);now1;pre0;init(1);for(int i4;in;i){swap(now,pre);memset(f[now],0,sizeof(f[now]));for(int j1;jtot;j){if(!f[pre][j]) continue;a[1]p[j][1];a[2]p[j][2];a[3]p[j][3];int pla[1]1?1:(a[2]1?2:3);for(int k0;k3;k){if(!tr[j][k]) continue;int frt kpl-1?4:a[(pl1)%31],sufkpl?4:a[pl%31];if(k0pl3) suf4;if(k3pl1) frt4; if(prelink(j,pl)ban[i-3frt-1][frt-1o]) continue;if(suflink(j,pl)ban[i-3][1-sufo]) continue;add(f[now][tr[j][k]],f[pre][j]);}}}ll ans0;for(int i1;itot;i){ bool flag1;memcpy(a,p[i],sizeof(p[i]));for(int j1;j3flag;j){int pre(j1)%31,sufj%31;if(prelink(i,j)ban[n-3a[pre]][a[pre]-a[j]o]){flag0;}else if(suflink(i,j)ban[n-3a[j]][a[j]-a[suf]o]){flag0;}}if(flag) add(ans,f[now][i]);}ansans*ksm(n,mod-2)%mod;printf(%lld\n,ans);return;
}
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();mread();Pread();for(int i1;im;i){int xread(),yread();if(abs(x-y)P) ban[x][x-yo]1;}if(n3){bf.work();return 0;}if(P1){printf(0);return 0;}else if(P2){work2();return 0;}else work3();return 0;
}
/*
*/
