本文共 2376 字，大约阅读时间需要 7 分钟。
询问一个多项式能否整除一个一次函数。a * x + b
注意到如果能整除，就比如是x^2 + 2 * x + 1能整除2 * x + 2
那么它必定能整除2 * x + 2的根，也就是和根肯定有交点。
因为你能整除，也就是(x^2 + 2 * x + 1) = k * (2 * x + 2)
那么k * (2 * x + 2)还是条直线。唯独使得2 * x + 2 = 0那个点是不会变的。
然后就是bit维护了。相当于询问[L, R]中，这一段的和，
注意特判一下b = 0，有点不同。
#include #include #include #include #include #include #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include #include #include #include #include #include const int MOD = 1e9 + 7;const int maxn = 1e5 + 20;LL powx[maxn];LL quick_pow(LL a, LL b, int MOD) { LL ans = 1; LL base = a; while (b > 0) { if (b & 1) { ans *= base; if (ans >= MOD) ans %= MOD; } b >>= 1; base *= base; if (base >= MOD) base %= MOD; } return ans;}LL c[maxn];int n, a, b, q;int lowbit(int x) { return x & (-x);}void upDate(int pos, LL val) { while (pos <= n) { c[pos] += val; pos += lowbit(pos); if (c[pos] >= MOD) c[pos] %= MOD; }}LL get_sum(int pos) { LL ans = 0; while (pos) { ans += c[pos]; pos -= lowbit(pos); if (ans >= MOD) ans %= MOD; } return ans;}LL arr[maxn];void work() {// cout << quick_pow(2, 4, MOD) << endl; scanf("%d%d%d%d", &n, &a, &b, &q); powx[0] = 1; powx[1] = -b * quick_pow(a, MOD - 2, MOD) % MOD; for (int i = 2; i <= n; ++i) { powx[i] = powx[i - 1] * powx[1] % MOD; } for (int i = 1; i <= n; ++i) { LL x; scanf("%lld", &x); arr[i] = x; upDate(i, x * powx[i - 1] % MOD); } if (b == 0) { while (q--) { int flag; scanf("%d", &flag); if (flag == 1) { int pos, val; scanf("%d%d", &pos, &val); ++pos; arr[pos] = val; } else { int L, R; scanf("%d%d", &L, &R); L++; R++; if (arr[L] == 0) { printf("Yes\n"); } else printf("No\n"); } } return; } while (q--) { int flag; scanf("%d", &flag); if (flag == 1) { int pos; LL val; scanf("%d%lld", &pos, &val); pos++; LL now = (get_sum(pos) + MOD - get_sum(pos - 1)) % MOD; upDate(pos, -now); upDate(pos, val * powx[pos - 1] % MOD); } else { int L, R; scanf("%d%d", &L, &R); L++; R++; LL now = (get_sum(R) - get_sum(L - 1) + MOD) % MOD; if (now == 0) { printf("Yes\n"); } else printf("No\n"); } }}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif work(); return 0;}
转载于:https://www.cnblogs.com/liuweimingcprogram/p/6348987.html
