P8152 题解

Jerrlee✅

2022-02-14 19:45:05

Solution

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 记录