Editorial for Bedao Regular Contest 06 - PYRAMID2
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta quan sát thấy được quy luật của kim tự tháp ~(m, n)~ là số ~1~ sẽ được lặp lại ~n + 1~ lần, số ~m~ sẽ lặp lại ~n~ lần, và các số trong khoảng từ ~[2...m - 1]~ sẽ lặp lại ~2n~ lần:
~(n + 1) + \sum\limits_{i=2}^{m - 1} i \times 2n + m \times n~
= ~(n + 1) + (m - 2) \times (m + 1) \times n + m \times n~
= ~1 + n \times (m^2 - m - 2 + m + 1)~
= ~1 + n \times (m^2 - 1)~
Như vậy với công thức trên ta có thể trả lời mỗi truy vấn trong ~O(1)~.
Độ phức tạp: ~O(q)~
Code mẫu
/* Author : DeMen100ns (a.k.a Vo Khac Trieu self-destruct) School : VNU-HCM High school for the Gifted */ #include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1e9 + 7; inline void add(int &x, int y, int mod = MOD) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod;} inline void mul(int &x, int y, int mod = MOD) { x = (x * 1LL * y) % mod;} inline int prod(int x, int y, int mod = MOD) { return mul(x, y, mod), x;} inline int sum(int x, int y, int mod = MOD) { return add(x, y, mod), x;} inline int bpow(int x, int y, int mod = MOD) { int ans = 1; while (y) { if (y & 1) mul(ans, x, mod); mul(x, x, mod); y >>= 1;} return ans;} inline int Inv(int x, int mod = MOD) { return bpow(x, mod - 2, mod);} inline int Div(int x, int y, int mod = MOD) { return prod(x, Inv(y, mod), mod);} const int N = 1e5 + 5; const long long INF = 1e18 + 7; const int MAXA = 1e9; const int B = sqrt(N) + 5; int dp[N], f[N], a[N]; void solve(){ int n, m; cin >> n >> m; cout << sum(prod(n, (sum(prod(m, m), - 1))), 1) << endl; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while(t--){ solve(); } }
Comments