【集训队互测 2023】森林游戏
He_Ren orz
把得分重新定义：先手选一个数，增加得分，后手减小得分，先手想最大化得分，后手想最小化得分。
先考虑一个特殊情况：森林中的每一棵树都是一条链，且每条链从前往后不增。两个人的策略都是选择能选的点中权值最大的，也就是说这个森林等价于将所有权值归并起来形成的一条链。
再考虑在一条不增的链的最前面加上一个比较小的数 \(x\) 会发生什么：设原链头（最大值）为 \(y(x \lt y)\)，有如下两种情况：
- 新的链只有 \(x,y\) 两个数，那么在最优策略下玩家都不希望选 \(x\)，即这两个点可以看做对答案有 \((-1)^{n} (x-y)\) 的贡献，我们可以将贡献加到答案里并删去这两个节点。
- \(y\) 后面还有一个数，令这个数为 \(z\)，玩家会主动去选 \(x\)，当且仅当他希望得到 \(z\)，也就是说，\(x \rightarrow y \rightarrow z\) 这条链等价于一个权值为 \(x-y+z\) 的节点。
我们可以利用这几条结论解决原问题，总体思想是将树转化成一条不增的链，具体的，在处理节点 \(u\) 的时候先将它的每个儿子的子树变成一条不增的链，然后将这些链启发式合并起来，再尝试加入 \(A_u\)，不断和链首和链的第二个节点合并，复杂度 \(O(n \log^2 n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n;
int a[200005];
vector <int> g[200005];
priority_queue <int> pq[200005];
int ans2;
void dfs(int u,int fa)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
dfs(v,u);
if(pq[u].size()<pq[v].size()) swap(pq[u],pq[v]);
while(pq[v].size()) pq[u].push(pq[v].top()),pq[v].pop();
}
bool in=0;
while(1)
{
if(!pq[u].size()||a[u]>=pq[u].top())
{
pq[u].push(a[u]);
in=1;
break;
}
if(pq[u].size()<2) break;
int x=pq[u].top();
pq[u].pop();
int y=pq[u].top();
pq[u].pop();
a[u]=a[u]+y-x;
}
if(!in)
{
if(n%2==0) ans2+=a[u],ans2-=pq[u].top();
else ans2-=a[u],ans2+=pq[u].top();
pq[u].pop();
}
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int sum=0;
for(int i=1;i<=n;i++) sum+=a[i];
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].pb(v),g[v].pb(u);
}
dfs(1,-1);
int op=0;
while(pq[1].size())
{
if(!op) ans2+=pq[1].top();
else ans2-=pq[1].top();
op^=1;
pq[1].pop();
}
cout<<(sum+ans2)/2;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【GDCPC 2023】Swapping Operation
把令前缀 \(\&\) 减小的位置 \(B=\{b_1,b_2,\cdots, b_{|B|}\}\) 拿出来，令后缀 \(\&\) 减小的位置 \(C=\{c_1,c_2,\cdots ,c_{|C|}\}\) 拿出来，枚举 \(F(A)\) 中的分界点 \(k\)，此时只有在左右两边各选择一个才会对答案有影响，令在左边选择的位置为 \(i\)，右边选择的位置为 \(j\)，分如下几种情况讨论。
- \(i \in B, j \in C\)，令 \(V\) 是值域，由于 \(|B|,|C| \le \log V\)，这部分可以暴力枚举计算。
- \(i \notin B,j \notin C\)，这样交换会使得前一半的 \(\&\) 不增，后一半也不增，可以不考虑。
- \(i \in B, j \notin C\)，事实上这种情况，无论从右面拿什么数出来，后面的 \(\&\) 都不会改变，令 \(g(l,r)\) 表示 \([l,r]\) 的 \(\&\)，我们要在后面选出一个不在 \(C\) 里面的数 \(x\)，最大化 \(g(1,i-1) \& g(i+1,k) \& x\)，这个通过 Trie 等常见套路不方便维护。观察到固定 \(i\) 后，也只会有 \(O(\log V)\) 个 \(k\) 令 \(g(1,i-1) \& g(i+1,k)\) 改变，改变的时候暴力重算，或者暴力更新这 \(O(\log^2 V)\) 个可能的 \(g(1,i-1) \& g(i+1,k)\) 即可。
- \(i \notin B,j \in C\)，和上面是对称的情况，不再赘述。
用 st 表维护 \(g(l,r)\) 可以做到 \(O(n \log^2 V)\)。
Code
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,a[100005];
int Lg[100005],st[17][100005];
void build()
{
Lg[1]=0,Lg[2]=1;
for(int i=3;i<=n;i++) Lg[i]=Lg[i/2]+1;
for(int i=1;i<=n;i++) st[0][i]=a[i];
for(int k=1;k<17;k++) for(int i=1;i+(1<<k)-1<=n;i++)
st[k][i]=(st[k-1][i]&st[k-1][i+(1<<(k-1))]);
}
int query(int l,int r)
{
if(l>r) return (1<<30)-1;
int s=Lg[r-l+1];
return (st[s][l]&st[s][r-(1<<s)+1]);
}
gp_hash_table <int,int> ma;
vector <int> pre,suf,vals;
bool isp[100005],iss[100005];
int ans=0;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],isp[i]=iss[i]=0;
ans=0;
build();
ma.clear(),pre.clear(),suf.clear(),vals.clear();
pre.pb(1),isp[1]=1;
for(int i=2;i<=n;i++) if(query(1,i)!=query(1,i-1)) pre.pb(i),isp[i]=1;
suf.pb(n),iss[n]=1;
for(int i=n-1;i>=1;i--) if(query(i,n)!=query(i+1,n)) suf.pb(i),iss[i]=1;
reverse(suf.begin(),suf.end());
for(int i=0;i<pre.size();i++)
{
int x=pre[i];
vals.pb(query(1,x-1));
for(int j=x+1;j<=x;j++) if((query(1,x-1)&query(x+1,j))!=(query(1,x-1)&query(x+1,j-1))) vals.pb(query(1,x-1)&query(x+1,j));
}
for(int k=1;k<n;k++)
{
ans=max(ans,query(1,k)+query(k+1,n));
for(int i=0;i<pre.size()&&pre[i]<=k;i++) for(int j=suf.size()-1;j>=0&&suf[j]>k;j--)
{
int x=pre[i],y=suf[j];
// cout<<"try: "<<k<<" "<<x<<" "<<y<<endl;
// cout<<(query(1,x-1)&query(x+1,k)&a[y])<<" "<<(query(k+1,y-1)&query(y+1,n)&a[x])<<endl;
ans=max(ans,(query(1,x-1)&query(x+1,k)&a[y])+(query(k+1,y-1)&query(y+1,n)&a[x]));
}
}
// for(int i=1;i<=n;i++) cout<<isp[i]<<" "<<iss[i]<<"\n";
for(int k=n-1,flg=0;k>=1;k--)
{
if(!iss[k+1])
{
flg=1;
for(int i=0;i<vals.size();i++) ma[vals[i]]=max(ma[vals[i]],(vals[i]&a[k+1]));
}
if(flg)
{
for(int i=0;i<pre.size()&&pre[i]<=k;i++)
{
int x=pre[i];
int v=(query(1,x-1)&query(x+1,k));
ans=max(ans,(v&ma[v])+(query(k+1,n)&a[x]));
}
}
}
reverse(a+1,a+1+n);
for(int i=1;i<=n;i++) isp[i]=iss[i]=0;
build();
ma.clear(),pre.clear(),suf.clear(),vals.clear();
pre.pb(1),isp[1]=1;
for(int i=2;i<=n;i++) if(query(1,i)!=query(1,i-1)) pre.pb(i),isp[i]=1;
suf.pb(n),iss[n]=1;
for(int i=n-1;i>=1;i--) if(query(i,n)!=query(i+1,n)) suf.pb(i),iss[i]=1;
reverse(suf.begin(),suf.end());
for(int i=0;i<pre.size();i++)
{
int x=pre[i];
vals.pb(query(1,x-1));
for(int j=x+1;j<=x;j++) if((query(1,x-1)&query(x+1,j))!=(query(1,x-1)&query(x+1,j-1))) vals.pb(query(1,x-1)&query(x+1,j));
}
for(int k=n-1,flg=0;k>=1;k--)
{
if(!iss[k+1])
{
flg=1;
for(int i=0;i<vals.size();i++) ma[vals[i]]=max(ma[vals[i]],(vals[i]&a[k+1]));
}
if(flg)
{
for(int i=0;i<pre.size()&&pre[i]<=k;i++)
{
int x=pre[i];
int v=(query(1,x-1)&query(x+1,k));
ans=max(ans,(v&ma[v])+(query(k+1,n)&a[x]));
}
}
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
【GDCPC 2023】Classic Problem
相较于 \(n\) 的范围，图中只有很少一部分点拥有一条特殊边权的邻边，将这些点称为”特殊点“，将其余点称为”一般点“。
只有 \(2m\) 个特殊点和 \(2m+1\) 个一般点的连续段，我们可以将一个一般点的连续段缩成一个点（正确性证明：Kruskal），即得到了一个点数为 \(O(m)\) 的图，可以接受。
本来我想用 Kruskal 继续做下去的，只要快速找到某两个联通块之间长度为某个数的一条边即可，实际上一个连通块会包含多个连续段，导致两个联通块的结构会特别多，找边会变的异常复杂甚至无法维护。
考虑 Boruvka 算法，对于一般点找到左右两边第一个不在同一连通块内的一般点，这个比较好维护，暴力扫一遍即可，对于特殊点需要暴力枚举特殊边，还需要找到左右两边第一个没有特殊边的点，事实上这个也可以暴力跳，因为总共只会经过 \(O(m)\) 个有特殊边的点。
复杂度 \(O(m \log n)\)，有一些细节。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
struct DSU
{
int fa[400015],L[400015],R[400015];
int find(int x)
{
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
int xx=find(x),yy=find(y);
if(xx!=yy)
{
fa[xx]=yy;
L[yy]=min(L[yy],L[xx]),R[yy]=max(R[yy],R[xx]);
}
}
void init(int n)
{
for(int i=0;i<n;i++) fa[i]=L[i]=R[i]=i;
}
}d1,d2;
int n,m;
int U[100005],V[100005],W[100005];
vector <pii > vec;
vector <int> bad;
int getid(int u)
{
return upper_bound(vec.begin(),vec.end(),mp(u+1,-1))-vec.begin()-1;
}
int calcd_p(int x,int y)
{
return abs(x-y);
}
int calcd(int u,int v)
{
return min(min(calcd_p(vec[u].fi,vec[v].fi),calcd_p(vec[u].fi,vec[v].se)),min(calcd_p(vec[u].se,vec[v].fi),calcd_p(vec[u].se,vec[v].se)));
}
int pre[400015],nxt[400015];
int to[400015],val[400015];
vector <pii > g[400015];
map <pii,int> has;
void solve()
{
cin>>n>>m;
if(!m)
{
cout<<n-1<<"\n";
return;
}
has.clear();
for(int i=1;i<=m;i++) cin>>U[i]>>V[i]>>W[i];
vec.clear(),bad.clear();
for(int i=1;i<=m;i++) bad.pb(U[i]),bad.pb(V[i]);
sort(bad.begin(),bad.end());
bad.resize(unique(bad.begin(),bad.end())-bad.begin());
if(bad[0]>1) vec.pb(mp(1,bad[0]-1));
ll ans=0;
for(int i=0;i<bad.size();i++)
{
vec.pb(mp(bad[i],bad[i]));
if(i+1<bad.size()&&bad[i]+1<=bad[i+1]-1) vec.pb(mp(bad[i]+1,bad[i+1]-1));
if(i+1==bad.size()&&bad[i]+1<=n) vec.pb(mp(bad[i]+1,n));
}
d1.init(vec.size()),d2.init(vec.size());
for(int i=0;i<vec.size();i++) ans+=vec[i].se-vec[i].fi,g[i].clear();
for(int i=1;i<=m;i++)
{
int u=getid(U[i]),v=getid(V[i]);
has[mp(u,v)]=has[mp(v,u)]=1;
// cout<<"ban: "<<u<<" "<<v<<"\n";
g[u].pb(mp(v,W[i])),g[v].pb(mp(u,W[i]));
}
int N=vec.size();
// for(int i=0;i<N;i++) sort(g[i].begin(),g[i].end()),cout<<vec[i].fi<<" "<<vec[i].se<<" "<<g[i].size()<<"\n";
while(1)
{
bool ok=1;
for(int i=0;i<N;i++) if(d1.find(i)!=d1.find(0))
{
ok=0;
break;
}
for(int i=0;i<N;i++) pre[i]=nxt[i]=val[i]=to[i]=-1,val[i]=inf;
if(ok) break;
for(int i=0;i<N;i++)
{
int j=i;
while(1)
{
if(d1.find(j)!=d1.find((j+1)%N))
{
nxt[j]=(j+1)%N;
break;
}
j=(j+1)%N;
if(nxt[j]!=-1) break;
}
for(int l=i;l!=j;l=(l+1)%N) nxt[l]=nxt[j];
// i=j;
// cout<<i<<"\n";
}
for(int i=N-1;i>=0;i--)
{
int j=i;
while(1)
{
if(d1.find(j)!=d1.find((j+N-1)%N))
{
pre[j]=(j+N-1)%N;
break;
}
j=(j+N-1)%N;
if(pre[j]!=-1) break;
}
for(int l=i;l!=j;l=(l+N-1)%N) pre[l]=pre[j];
// i=j;
// cout<<i<<"\n";
}
for(int i=0;i<N;i++) if(!g[i].size())
{
if(calcd(i,nxt[i])<calcd(i,pre[i])) to[i]=nxt[i],val[i]=calcd(i,nxt[i]);
else to[i]=pre[i],val[i]=calcd(i,pre[i]);
}
for(int i=0;i<N;i++) if(g[i].size())
{
int u=(i+N-1)%N;
pre[i]=nxt[i]=-1;
int cnt=0;
while(1)
{
// cout<<cnt<<"\n";
while(d1.find(u)==d1.find(i))
{
int v=d2.L[d2.find(u)];
u=(v+N-1)%N;
}
cnt++;
if(cnt>g[i].size()+1) break;
if(has[mp(i,u)])
{
u=(u+N-1)%N;
continue;
}
else
{
pre[i]=u;
break;
}
}
// puts("...");
cnt=0;
u=(i+1)%N;
while(1)
{
while(d1.find(u)==d1.find(i))
{
int v=d2.R[d2.find(u)];
u=(v+1)%N;
}
cnt++;
if(cnt>g[i].size()+1) break;
if(has[mp(i,u)])
{
u=(u+1)%N;
continue;
}
else
{
nxt[i]=u;
break;
}
}
// cout<<"... "<<i<<" "<<pre[i]<<" "<<nxt[i]<<"\n";
val[i]=inf;
if(pre[i]!=-1&&calcd(pre[i],i)<val[i]) val[i]=calcd(pre[i],i),to[i]=pre[i];
if(nxt[i]!=-1&&calcd(nxt[i],i)<val[i]) val[i]=calcd(nxt[i],i),to[i]=nxt[i];
for(int j=0;j<g[i].size();j++)
{
int v=g[i][j].fi,w=g[i][j].se;
if(w<val[i]&&d1.find(i)!=d1.find(v)) val[i]=w,to[i]=v;
}
}
for(int i=0;i<N;i++) if(val[i]<val[d1.find(i)]) val[d1.find(i)]=val[i],to[d1.find(i)]=to[i];
vector <array<int,3> > ed;
ed.clear();
for(int i=0;i<N;i++) if(i==d1.find(i)) ed.pb({i,to[i],val[i]});
for(int i=0;i<ed.size();i++) if(d1.find(ed[i][0])!=d1.find(ed[i][1])) ans+=1LL*ed[i][2],d1.merge(ed[i][0],ed[i][1]);
d2.init(N);
for(int i=0;i+1<N;i++) if(d1.find(i)==d1.find(i+1)) d2.merge(i,i+1);
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
【CF280E】Sequence Transformation
这题做法是 dp 导出的！令 \(f_i(x)\) 表示，填了 \([1,i]\)，\(y_i\) 填的是 \(x\) 的最小代价，转移：\(f_i(x)=(x-x_i)^2+\min_{y \in [x-b,x-a]} f_{i-1}(y)\)。
\(f_1(x)\) 的图像很简单，就是抛物线 \(y=(x-x_1)^2\)，\(f_2(x)\) 的图像可以看做将 \(f_1(x)\) 的图像平移，从最低点切开，将右边的部分再平移，中间用一个平台相连，然后整体加上 \((x-x_2)^2\)。
\(f_i(x)\) 的图像我们可以看做 \(O(i)\) 段开口向上的抛物线拼接成的下凹函数，证明就是转移的过程，可以利用类似 slope trick 的方法维护转移，暴力的复杂度是 \(O(n^2)\)，用平衡树可以做到 \(O(n \log n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define double long double
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const double inf=1000000000000.0;
struct Quad
{
double l,r,a,b,c;
double gettop()
{
double x=-b/a/2.0;
if(x<l) return l;
if(x>r) return r;
return x;
}
double calc(double x)
{
return a*x*x+b*x+c;
}
double calcmin()
{
return calc(gettop());
}
void shft(double d)
{
l+=d,r+=d;
double tb=b,tc=c;
b=tb-2.0*a*d;
c=tc-tb*d+a*d*d;
}
};
Quad quad(double l,double r,double a,double b,double c)
{
Quad res;
res.l=l,res.r=r,res.a=a,res.b=b,res.c=c;
return res;
}
void splt(Quad &x,double dl,double dr)
{
x.l=max(x.l,dl),x.r=min(x.r,dr);
}
void add(Quad &x,Quad y)
{
x.a+=y.a,x.b+=y.b,x.c+=y.c;
}
int sz[2];
double tp[6005];
Quad dp[2][20005];
int n;
double A,B,m;
double X[6005],Y[6005];
void solve()
{
cin>>n>>m;
cin>>A>>B;
for(int i=1;i<=n;i++) cin>>X[i];
int now=0;
dp[0][0]=quad(1.0,m,1.0,-2.0*X[1],X[1]*X[1]);
sz[0]=1;
//cout<<dp[0][0].gettop()<<"\n";
for(int i=2;i<=n;i++)
{
now^=1;
sz[now]=0;
double x=-1,y=-1;
for(int j=0;j<sz[now^1];j++)
{
double t=dp[now^1][j].calcmin();
if(t<y||y==-1) y=t,x=dp[now^1][j].gettop();
}
// cout<<x<<" "<<y<<" "<<endl;
tp[i]=x;
// dp[now^1][0].l=-inf,dp[now^1][sz[now^1]-1].r=inf;
for(int j=0;j<sz[now^1];j++)
{
Quad tmp=dp[now^1][j];
tmp.shft(A);
if(tmp.l<=x+A)
{
dp[now][sz[now]]=tmp,splt(dp[now][sz[now]],1.0,x+A);
splt(dp[now][sz[now]],1.0,m);
if(dp[now][sz[now]].l<=dp[now][sz[now]].r) sz[now]++;
}
}
dp[now][sz[now]]=quad(x+A,x+B,0.0,0.0,y);
splt(dp[now][sz[now]],1.0,m);
if(dp[now][sz[now]].l<=dp[now][sz[now]].r) sz[now]++;
for(int j=0;j<sz[now^1];j++)
{
Quad tmp=dp[now^1][j];
tmp.shft(B);
if(tmp.r>=x+B)
{
dp[now][sz[now]]=tmp,splt(dp[now][sz[now]],x+B,m);
splt(dp[now][sz[now]],1.0,m);
if(dp[now][sz[now]].l<=dp[now][sz[now]].r) sz[now]++;
}
}
Quad del=quad(1.0,m,1.0,-2.0*X[i],X[i]*X[i]);
for(int j=0;j<sz[now];j++) add(dp[now][j],del);//,cout<<dp[now][j].l<<" "<<dp[now][j].r<<" "<<dp[now][j].a<<" "<<dp[now][j].b<<" "<<dp[now][j].c<<"\n";
// system("pause");
}
double x=-1,y=-1;
for(int j=0;j<sz[now];j++)
{
double t=dp[now][j].calcmin();
if(t<y||y==-1) y=t,x=dp[now][j].gettop();
}
double ans=y;
Y[n]=x;
for(int i=n;i>=2;i--)
{
if(x<=tp[i]+A) x-=A;
else if(x<=tp[i]+B) x=tp[i];
else x-=B;
Y[i-1]=x;
}
for(int i=1;i<=n;i++) printf("%.12Lf ",Y[i]);
cout<<"\n";
printf("%.12Lf\n",ans);
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【CF1229D】Wojtek and Card Tricks
一个很符合直觉的事情，固定 \(l\) 后 \(f(l,r)\) 改变的次数不多，证明实际上不需要任何群论：
令目前可以构造出的集合是 \(S\)，我们只需要证明，加入一个置换 \(R(R \notin S)\)，\(S\) 的大小至少乘以 \(2\)。我们只需要证明：
- 对于任意 \(P,Q \in S,P \neq Q\)，有 \(P \times R \neq Q \times R\)。
- 对于任意 \(P \in S\)，\(P \times R \notin S\)。
第一个可以反证：假设 \(P \times R = Q \times R\)，令 \(P \times R = T\)，而我们只能找到一个置换使其 \(\times R=T\)，与 \(P=Q\) 矛盾。
第二个还是反证：假设 \(P \times R \in S\)，令 \(P \times R = T\)，由于 \(P,T \in S\)，可以得到 \(R \in S\)，这与 \(R \notin S\) 矛盾。
枚举 \(l\)，找到 \(R\) 后暴力 bfs 即可，复杂度 \(O(nk \space k!\log(k!))\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,K;
vector <int> A[200005];
vector <int> shuf(vector <int> P,vector <int> Q)
{
vector <int> R;
R.clear();
for(int i=0;i<Q.size();i++) R.pb(P[Q[i]]);
return R;
}
int ha[1000005];
vector <int> rl[1000005];
int gethash(vector <int> P)
{
int k=0;
for(int i=0;i<P.size();i++) k*=10,k+=P[i];
return ha[k];
}
bool vis[125];
int now[6];
int to[125][125],a[200005];
queue <int> pos[200005];
void solve()
{
cin>>n>>K;
for(int i=1;i<=K;i++) now[i]=i;
int idx=0;
do
{
int k=0;
for(int i=1;i<=K;i++) k*=10,k+=now[i]-1;
ha[k]=idx;
// cout<<k<<" --- "<<idx<<endl;
for(int i=1;i<=K;i++) rl[idx].pb(now[i]-1);
idx++;
}while(next_permutation(now+1,now+1+K));
for(int i=0;i<idx;i++) for(int j=0;j<idx;j++) to[i][j]=gethash(shuf(rl[i],rl[j]));
for(int i=1;i<=n;i++)
{
for(int j=0;j<K;j++)
{
int x;
cin>>x;
x--;
A[i].pb(x);
}
pos[gethash(A[i])].push(i);
a[i]=gethash(A[i]);
}
// for(int j=0;j<idx;j++) cout<<pos[j].size()<<"\n";
ll ans=0;
for(int l=1;l<=n;l++)
{
for(int j=0;j<idx;j++) if(pos[j].size()&&pos[j].front()<l) pos[j].pop();
memset(vis,0,sizeof(vis));
int u=0;
vis[0]=1;
for(int j=0;j<6;j++) u=to[u][a[l]],vis[u]=1;
int lst=l;
vector <int> nw;
nw.clear();
nw.pb(a[l]);
while(1)
{
int nxt=n+1;
for(int j=0;j<idx;j++) if(!vis[j]&&pos[j].size()&&pos[j].front()<nxt) nxt=pos[j].front();
int c=0;
for(int j=0;j<idx;j++) if(vis[j]) c++;
ans+=1LL*(nxt-lst)*c;
// cout<<l<<" "<<lst<<" "<<nxt<<" "<<c<<endl;
// for(int j=0;j<idx;j++) cout<<pos[j].size()<<"\n";
if(nxt==n+1) break;
nw.pb(a[nxt]);
lst=nxt;
queue <int> q;
while(q.size()) q.pop();
for(int j=0;j<idx;j++) if(vis[j]) q.push(j);
while(q.size())
{
int v=q.front();
q.pop();
for(int j=0;j<nw.size();j++) if(!vis[to[v][nw[j]]]) vis[to[v][nw[j]]]=1,q.push(to[v][nw[j]]);
}
}
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}