神奇的代码
2023-08-31 17:18:57
发布于：广东
0阅读
0回复
0点赞
#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;
}
这里空空如也
有帮助，赞一个