【hdu 6172】Array Challenge（数列、找规律）

#include <cstdio>
#include <map>
#include <cstdlib>
#include <queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,l,r) for (int i=l;i<r;++i)
typedef unsigned long long ull;
int dx[4]={1,1,-1,-1},dy[4]={0,1,0,-1};
map<ull,bool>vis;
struct Sta{
	int a[6][6],step,x,y;
	Sta(){step=x=y=0;}
};
int gujia(Sta s){
	int ans=0;
	rep(i,0,6)rep(j,0,i+1)
	if(s.a[i][j])ans+=abs(s.a[i][j]-i);
	return ans;
}
ull haxi(Sta s){
	ull ans=0;
	rep(i,0,6)rep(j,0,i+1){
		ans<<=3;ans|=s.a[i][j];
	}
	return ans;
}
int bfs(Sta s){
	vis.clear();
	queue<Sta>q;q.push(s);
	while(!q.empty()){
		Sta now=q.front();q.pop();
		if(gujia(now)==0)return now.step;
		rep(i,0,4){
			int x=now.x,y=now.y;
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=0 && nx<6 && ny>=0 && ny<=nx){
				swap(now.a[x][y],now.a[nx][ny]);
				now.x=nx,now.y=ny,++now.step;
				ull hx=haxi(now);
				if(!vis[hx]&&gujia(now)+now.step<21){
					q.push(now);
					vis[hx]=true;
				}
				swap(now.a[x][y],now.a[nx][ny]);
				now.x-=dx[i],now.y-=dy[i],--now.step;
			}
		}
	}
	return -1;
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		Sta s;
		rep(i,0,6)
		rep(j,0,i+1){
			scanf("%d",&s.a[i][j]);
			if(s.a[i][j]==0)s.x=i,s.y=j;
		}
		int ans=bfs(s);
		if(ans==-1)puts("too difficult");else printf("%d\n",ans);
	}
	return 0;
}

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
const ll mod=1000000007;
ll qpow(ll a,ll b) {ll res=1;for(a%=mod;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;return res;}
VI BM(VI s) {//c[0]s[0]+c[1]s[1]+...=0
	VI C(1,1),B(1,1);
	int L=0,m=1,rev=1;
	rep(n,0,SZ(s)) {
		ll d=0;
		rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
		if (d==0) ++m;
		else if (2*L<=n) {
			VI T=C;
			ll c=mod-d*rev%mod;
			C.resize(SZ(B)+m);
			rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
			L=n+1-L; B=T; rev=qpow(d,mod-2); m=1;
		} else {
			ll c=mod-d*rev%mod;
			C.resize(SZ(B)+m);
			rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
			++m;
		}
	}
	rep(i,0,SZ(C))printf("%dx[%d]%s",C[i],i,i+1==SZ(C)?"=0\n":"+");
	return C;
}
调用：BM(VI{31,197,1255,7997})