自动搬运

查看原文

来自洛谷，原作者为

	Lithium_Chestnut 这个家伙很家伙，什么都没有什么。

搬运于2025-08-24 22:36:26，当前版本为作者最后更新于2021-12-26 17:23:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每次分割将右下角的矩形分割为 $n \times n$ 个矩形，显然每次分割就是将原有的 $a$ 个矩形分割为 $a-1+n \times n$ 个矩形。

那么 $k$ 次分割就是 $a-k+n \times n \times k$。

因为原有矩形为 $1$，所以答案就是 $1-k+n \times n \times k$，按降幂顺序排列整合一下就是 $n^2k-k+1$。

由于计算过大，记得开 __int128，并且配上快读快输，还有取模 $998244353$。

代码如下：

#include<bits/stdc++.h>
#define ll __int128
using namespace std;
ll n,k;
const int mod=998244353;
ll read()
{
	int x=0,w=0;
	char ch=0;
	while(!isdigit(ch))
	{
		w|=ch=='-';
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return w?-x:x;
}
void write(ll x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
int main()
{
	n=read(),k=read();
	write((n*n*k-k+1)%mod);
	return 0;
}