题解

关注一下呗

#include<cstdio>
#include<iomanip>
#include<cstring>
#define N 30005
#define M (1<<18)+5
#define ll long long
#define mod 1000000007
#define O4 __inline__ __attribute__((always_inline))
using namespace std;
int las=1,cnt[M][7],tr[M][7];
int n,k,now,he[N][7],su[N][7],vis[M];
const int Mxdt=180000;
O4 char gc() {
	static char buf[Mxdt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
O4 int read() {
	int res=0,bj=0;
	char ch=gc();
	while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=gc();
	while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
	return bj?-res:res;
}
O4 int Mod(int x) {
	return x<=mod?x:x-mod;
}
struct at {
	ll val;
	int cnt;
	at() {
		val=1e18,cnt=0;
	} at(ll _v,int _c):val(_v),cnt(_c) {}
};
O4 at operator *(at a,at b) {
	return (a.val!=b.val)?(a.val<b.val?a:b):(at(a.val,Mod(a.cnt+b.cnt)));
}
O4 at operator +(at a,ll b) {
	return at(a.val+b,a.cnt);
}
struct Node {
	pair<at,bool>val[M];
	int s[M],top;
	Node() {}
	O4 void clear() {
		for(int i=1; i<=top; ++i)val[s[i]].second=0;
		top=0;
	}
	at &operator[](int x) {
		if(!val[x].second)val[x]=make_pair(at(),1),s[++top]=x;
		return val[x].first;
	}
} dp[2];
O4 void Init(ll val=0) {
	for(int st=0,s=0,ct=0; st<(1<<k-1); dp[now][s]=at(val,1),++st,s=ct=val=0)
		for(int t=1; t<k; ++t)((st&(1<<t-1))?val+=he[0][t]:++ct),s|=ct<<(t*3);
}
O4 int Get(int s,int x) {
	return (s>>3*x)&7;
}
O4 int Change(int s,int x,int y) {
	return s^((Get(s,x)^y)<<3*x);
}
O4 void Work(int s,int x) {
	for(int i=0; i<k; ++i)
		if(Get(s,i)==x&&++cnt[s][x]>1)return;
}
O4 void CSH(int s) {
	if(vis[s])return;
	static int cnt,tmp,id[7];
	memset(id,-1,sizeof(id)),cnt=0,tmp=s;
	for(int i=0,x; i<k; ++i)x=Get(s,i),s=Change(s,i,(~id[x])?id[x]:id[x]=cnt++);
	return vis[tmp]=s,void();
}
O4 void Merge(int s,int x) {
	int t1=Get(s,x-1),t2=Get(s,x),tmp=s;
	if(t1==t2)return tr[tmp][x]=s,void();
	for(int i=0; i<k; ++i)if(Get(s,i)==t2)s=Change(s,i,t1);
	tr[tmp][x]=s;
}
O4 void Calc(int s) {
	static int vis[M]= {0};
	if(vis[s])return;
	vis[s]=1,CSH(s);
	for(int i=0; i<k; ++i)CSH(Change(s,i,6));
	for(int i=1; i<k; ++i)Merge(s,i),CSH(tr[s][i]);
	for(int i=0; i<k; ++i)Work(s,i);
	for(int i=1; i<k; ++i)CSH(Change(s,i,Get(s,i-1)));
}
O4 void Update(int s,at x) {
	dp[now][vis[s]]=dp[now][vis[s]]*x;
}
int main() {
	n=read(),k=read();
	for(int i=0; i<n; ++i)for(int j=1; j<k; ++j)he[i][j]=read();
	for(int i=0; i<k; ++i)for(int j=1; j<n; ++j)su[j][i]=read();
	Init();
	for(int i=1; i<n; ++i)
		for(int j=0,x; j<k; ++j) {
			now^=1,las^=1,dp[now].clear();
			for(int t=1,s; t<=dp[las].top; ++t) {
				at atom=dp[las][s=dp[las].s[t]];
				if(Calc(s),!j) {
					Update(s,atom+su[i][j]);
					if(cnt[s][Get(s,j)]>1)Update(Change(s,j,6),atom);
				} else {
					Update(s,atom+su[i][j]);
					if(cnt[s][Get(s,j)]>1)Update(Change(s,j,Get(s,j-1)),atom+he[i][j]),Update(Change(s,j,6),atom);
					if(Get(s,j)!=Get(s,j-1))Update(tr[s][j],atom+(su[i][j]+he[i][j]));
				}
			}
		}
	printf("%d\n",dp[now][0].cnt);
	return 0;
}