P8152 「PMOI-5」破译の论 题解

· · 题解

观察题目发现，每一次分割，小矩形总个数会乘 2 再减 1；第一次分割后矩形的总个数为 n^2 。

由此我们可以得到，第 k 次分割后，矩形个数为 n^2\times k -k+1。

又因为结果需要取模，所以每运算一次就取一次模。

放代码：

#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int p=998244353;
int main(){
  ull n,k; cin>>n>>k;
  ull x=1ull*(n*n%p)*(k%p)%p;
  cout<<(x%p-k%p+1)%mod;
  return 0;
}