F - Numbered Checker Editorial by physics0523
この問題には様々な方針があります。但し実装量に大きな差があるので楽な方針を考えましょう。
サンプル \(1\) の \(6\) つ目の質問に着目します。
グリッドの各行ごとに考えてみましょう。グリッドは以下のようでした。
1 0 3 0
0 6 0 8
9 0 11 0
0 14 0 16
17 0 19 0
まず、各行ごとの和を求めます。各行ごとに非零な要素は公差 \(2\) の等差数列をなすので、等差数列の和の公式を用いて計算できます。
また、グリッドがチェッカー模様を成すことから、各行ごとの最も左の非零な要素は (存在するなら) 取り出された各行の \(1\) 要素目か \(2\) 要素目です。(最も右のものも同様です。)
次に、行ごとにまとめた後のことを検討します。まず奇数行目に着目しましょう。
1 0 3 0
9 0 11 0
17 0 19 0
奇数行目について以下が成り立ちます:
各行ごとの非零な要素の数を \(x\) とすると、行ごとの値の総和は公差 \(2 \times x \times M\) の等差数列になります。( \(x=0\) でも成り立ちます)
理由は、非零な要素がある列について、各列の値が公差 \(2 \times M\) の等差数列を成すからです。
以下のように、偶数行目についても同様です。
0 6 0 8
0 14 0 16
よって、 \(A_i\) 行目と \(A_i+1\) 行目の \(C_i\) 列目から \(D_i\) 列目に関する情報を計算した後、 \(A_i\) 行目から \(B_i\) 行目までの和を取るという方針がとれます。
実装上のポイントとして、等差数列の和を取る操作を何度も行うことになるので、このように何度も行う操作は関数として取り出して書いておくと実装の軽減に繋がります。
実装例(C++):
#include<bits/stdc++.h>
#define mod 998244353
#define inv2 499122177 // inverse of 2
using namespace std;
// A_1 = fir
// A_i = fir + (i-1) * d
// return A_1 + A_2 + ... + A_{num}
long long arithmetic_sum(long long fir,long long d,long long num){
long long las=(fir+(num-1)*d)%mod;
long long res=(fir+las)%mod;
res*=num;res%=mod;
res*=inv2;res%=mod;
return res;
}
using pl=pair<long long,long long>;
long long n,m;
pl row_data(long long x,long long l,long long r){
if((x+l)%2){l++;}
if((x+r)%2){r--;}
if(l>r){return {0,0};}
long long mi=((x-1)*m+l)%mod;
long long num=1+(r-l)/2;
long long sum=arithmetic_sum(mi,2,num);
num*=2;num%=mod;
num*=m;num%=mod;
return {sum,num};
}
int main(){
int q;
cin >> n >> m >> q;
for(int i=0;i<q;i++){
long long a,b,c,d;
cin >> a >> b >> c >> d;
pl r1=row_data(a,c,d);
pl r2=row_data(a+1,c,d);
long long c1=(b-a+1)/2 + (b-a+1)%2;
long long c2=(b-a+1)/2;
long long res=0;
res+=arithmetic_sum(r1.first,r1.second,c1);res%=mod;
res+=arithmetic_sum(r2.first,r2.second,c2);res%=mod;
cout << res << "\n";
}
return 0;
}
posted:
last update: