1
1 차 다항식의 근음 (Q (x))을 x0 = -b/a라고합시다. 변수 a와 b의 범위가 크기 때문에 x0은 변수 x0에 저장하기 위해 커질 수 있습니다. 코드 줄이 어떻게 작동하는지 hackerank problemMOD 조작을 사용하여 큰 숫자를 고유 숫자로 매핑
누군가가 설명해 주시겠습니까 및 수학 :
때문에, 그것은 모드
int x0 = mul(mod - b, rev(a));
문제 링크와 함께 몇 가지 동작을 사용하여 일부 고유 번호로 변환된다 이 수술 뒤에? rev
의 모듈러 역이 거의 이론을 통해 계산 될 수 있도록
전체 코드 -
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);
const int mod = 1e9 + 7;
int udd(int &a, int b) {
a += b;
if (a >= mod)
a -= mod;
return a;
}
int add(int a, int b) {
return udd(a, b);
}
int mul(ll a, ll b) {
return a * b % mod;
}
//============didnt understand this step
int bin(int a, int d) {
int b = 1;
while (d) {
if (d & 1)
b = mul(b, a);
d >>= 1;
a = mul(a, a);
}
return b;
}
int rev(int a) {
assert(a != 0);
return bin(a, mod - 2);
}
const int maxn = 100100;
int px[maxn];
int c[maxn];
struct Fenwick {
int a[maxn];
int t[maxn];
void set(int pos, int val) {
int delta = add(val, mod - a[pos]);
a[pos] = val;
delta = mul(delta, px[pos]);
for (int i = pos; i < maxn; i |= i + 1) {
udd(t[i], delta);
}
}
int get(int r) {
int res = 0;
for (int i = r - 1; i >= 0; i = (i & (i + 1)) - 1)
udd(res, t[i]);
return res;
}
int get(int l, int r) {
return add(get(r), mod - get(l));
}
} fw;
int main() {
#ifdef LOCAL
assert(freopen("test.in", "r", stdin));
#endif
int n, a, b, q;
cin >> n >> a >> b >> q;
//========what does this line do?
int x0 = mul(mod - b, rev(a));
px[0] = 1;
for (int i = 1; i < n; ++i)
px[i] = mul(px[i - 1], x0);
forn (i, n) {
cin >> c[i];
fw.set(i, c[i]);
}
forn (i, q) {
int t, a, b;
cin >> t >> a >> b;
if (t == 1) {
fw.set(a, b);
} else {
++b;
int s = fw.get(a, b);
if (x0 == 0)
s = fw.a[a];
cout << (s == 0 ? "Yes" : "No") << '\n';
}
}
}