「PMOI-5」破译の论

Lithium_Chestnut · 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;
}