【题解】ABC259Ex Yet Another Path Counting

Sol

考虑两种暴力。

• 直接枚举同类点，组合数计算两点之间的路径数。单次操作时间复杂度 \(O(B^2)\)。其中 \(B\) 表示这类点的个数。
• 暴力 dp，记 \(dp_{i,j}\) 表示到 \((i,j)\) 的方案数，若走到同类点那么加上方案数，单次操作复杂度 \(O(n^2)\)。

然后考虑根号分治，当 \(B \leq n\) 时，做第一种操作，单次复杂度 \(O(n^2)\)，不会超过 \(n\) 次，总复杂度 \(O(n^3)\)。当 \(B>n\) 时，最多做 \(n\) 次，单次复杂度 \(O(n^2)\)，总复杂度 \(O(n^3)\)。
综上，总复杂度 \(O(n^3)\)。

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
#define int long long
using namespace std;
inline char gc()
{
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (isdigit(ch))
	{
		num=num*10+(int)(ch-'0');
		ch=getchar();
	}
	return pos*num;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
void writesp(int x)
{
	write(x);
	putchar(' ');
}
void writeln(int x)
{
	write(x);
	putchar('\n');
}
const int N=1e3+10,mod=998244353;
int n,C[N][N],ans,f[N][N],Map[N][N];
vector<pair<int,int> > G[N*N];
void work1(vector<pair<int,int> > g)
{
	for (int i=0;i<(int)g.size();i++)
		for (int j=i;j<(int)g.size();j++)
		{
			int x=g[i].first-g[j].first,y=g[i].second-g[j].second;
			if (x<0) x=-x,y=-y;
			else if (!x&&y<0) y=-y;
			if (y<0) continue;	
			ans=(ans+C[x+y][x])%mod;
		}
}
void work2(vector<pair<int,int> > g)
{
	memset(Map,0,sizeof(Map));
	for (auto x:g)
		Map[x.first][x.second]=1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
			if (Map[i][j]) (f[i][j]+=1)%=mod,ans=(ans+f[i][j])%mod;
		}
}
signed main()
{
	n=read();
	for (int i=0;i<=2*n;i++)
	{
		C[i][0]=1;
		for (int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			int x=read();
			G[x].emplace_back(i,j);
		}
	for (int i=1;i<=n*n;i++)
	{
		if (G[i].empty()) continue;
		if (G[i].size()<=n) work1(G[i]);
		else work2(G[i]);
	}
	writeln(ans);
}