Đề bài yêu cầu bạn tính:
$$
\sum_{i=a}^{c}\sum_{j=b}^{d} k^{(i-1)\,m + (j-1)}.
$$
Áp dụng tính chất luỹ thừa, ta tách $k^{(i-1)m + (j-1)} = k^{(i-1)m}\times k^{j-1}$
Sau đó, ta được:
$$
\sum_{i=a}^{c}\sum_{j=b}^{d} k^{(i-1)m + (j-1)}
= \Big(\sum_{i=a}^{c} k^{(i-1)m}\Big)\times \Big(\sum_{j=b}^{d} k^{j-1}\Big).
$$
Vì tổng trong ngoặc trái chỉ phụ thuộc vào $i$ và tổng phải chỉ phụ thuộc vào $j$
$\longrightarrow$ Ta sẽ tính tích hai tổng cho kết quả cuối cùng. Gọi:
* $R = \sum_{i=a}^{c} k^{(i-1)m}$,
* $C = \sum_{j=b}^{d} k^{j-1}$.
Kết quả là $R \times C \pmod{MOD}$.
Ta sẽ biến đổi lại biểu thức $R$ và $C$ như sau:
$$
R = \sum_{i=a}^{c} k^{(i-1)m}
= k^{(a-1)m} \times \big(1 + (k^m) + (k^m)^2 + \dots + (k^m)^{(c-a)}\big).
$$
$$
C = \sum_{j=b}^{d} k^{j-1}
= k^{b-1} \times \big(1 + k + k^2 + \dots + k^{(d-b)}\big).
$$
Từ $2$ biểu thức bên trên, ta nhận thấy chỉ cần tính được tổng $S(n) = 1 + a + a^2 + \dots + a^{n}$ là ta có thể hoàn thành bài toán
Nếu $MOD$ là số nguyên tố ta thường dùng công thức
$$
\sum_{t=0}^{n} a^t = \frac{a^n-1}{a-1}
$$
và lấy nghịch đảo $a-1$ modulo. Tuy nhiên ở bài toán này $MOD$ là ```111539768``` không phải là $1$ số nguyên tố nên không thể dùng được nghịch đảo modulo.
Thay vào đó, ta tính tổng bằng **chia để trị**:
**Lưu ý:** Do $S(n)$ lấy số mũ từ $0$ đến $n$ nên sẽ có $n+1$ phần tử
Ta xét hai ví dụ sau:
$$
S(5) = a^0 + a^1 + a^2 + a^3 + a^4 + a^5
$$
$$
S(6) = a^0 + a^1 + a^2 + a^3 + a^4 + a^5 + a^6
$$
Biến đổi lại $S(5)$ ta được
$S(5) = (a^0 + a^1 + a^2) + a^3 \times (a^0 + a^1 + a^2) = (a^0 + a^1 + a^2)\times(a^3 + 1) = S(2)\times(a^3 + 1)$
Khi đó với $S(6) = S(5) + a^6$
Từ đó cho ta ý tưởng như sau:
* Với $1$ dãy có số phần tử là chẵn $(2m)$ ta tách 2 nửa mỗi nửa có $m$ phần tử; phần sau là phần trước nhân thêm $r^{m}$. Vậy ta có công thức cho $n$ lẻ.
* Với $1$ dãy có số phần tử là lẻ $(2m+1)$, ta có $S(2m)=S(2m-1)+r^{2m}$, và lại áp dụng công thức cho $S(2m-1)$ (chia nửa) để viết theo $S(m-1)$. Vậy ta có công thức cho $n$ chẵn.
Code tham khảo:
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 5;
const int mod = 111539768;
int mul(int a, int b){
__int128 ans = 1;
(ans *= a) %= mod;
(ans *= b) %= mod;
return (int)ans;
}
int add(int a, int b){
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return a;
}
int fpow(int a, int n){
int ans = 1;
while(n){
if(n & 1) (ans *= a) %= mod;
(a *= a) %= mod;
n >>= 1;
}
return ans;
}
int calc(int a, int n){
if(n == 0) return 1;
if(n % 2){
int k = (n + 1) / 2;
int sum = calc(a, k - 1);
return mul(sum, 1 + fpow(a, k));
}
return add(calc(a, n - 1), fpow(a, n));
}
signed main(){
int n, m, k, a, b, c, d;
cin >> n >> m >> k >> a >> b >> c >> d;
int mr = fpow(k,(a - 1) * m);
int row = calc(fpow(k, m), c - a);
int sR = mul(mr, row);
int mc = fpow(k, b - 1);
int col = calc(k, d - b );
int sC = mul(mc, col);
cout << mul(sR, sC) << "\n";
}
```
Vinhzn08
Created at
3 likes