Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

P8152 题解

posted on 2022-02-14 19:45:05 | under 题解 |

UPD:修复了取模的一个 bug。

题意

给定一个足够大的正方形,每次将其右下角的小正方形(没有就是它自己)分成 $n \times n$ 份,求一共有几个正方形(正方形内不包含其余正方形)。

思路

以每次分割 $2 \times 2$ 的正方形为例,每次会增加 $3$ 也就是 $2 \times 2-1$ 个正方形,如此进行 $k$ 次,再加上 $1$(补上一开始就有的一个正方形),就是答案。

所以公式就是 $ans=(n \times n-1) \times k+1$。

记得模上 $998244353$!

注:本篇题解所用公式运算中不会也不可能出现负数,所以 long long 足够,无需 __int128

代码

C 语言可以 $30$ ms 跑出答案:

#include<stdio.h>
int main(){
    long long n,k;
    scanf("%lld%lld",&n,&k);
    long long a=((((n*n-1)%998244353)*k)%998244353)+1;
    printf("%lld",a);
}

AC 记录