Polynomial Division 数学题

https://www.hackerrank.com/contests/101hack45/challenges/polynomial-division

询问一个多项式能否整除一个一次函数。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 <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int MOD = 1e9 + ;

const int maxn = 1e5 + ;

LL powx[maxn];

LL quick_pow(LL a, LL b, int MOD) {

    LL ans = ;

    LL base = a;

    while (b > ) {

        if (b & ) {

            ans *= base;

            if (ans >= MOD) ans %= MOD;

        }

        b >>= ;

        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 = ;

    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[] = ;

    powx[] = -b * quick_pow(a, MOD - , MOD) % MOD;

    for (int i = ; i <= n; ++i) {

        powx[i] = powx[i - ] * powx[] % MOD;

    }

    for (int i = ; i <= n; ++i) {

        LL x;

        scanf("%lld", &x);

        arr[i] = x;

        upDate(i, x * powx[i - ] % MOD);

    }

    if (b == ) {

        while (q--) {

            int flag;

            scanf("%d", &flag);

            if (flag == ) {

                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] == ) {

                    printf("Yes\n");

                } else printf("No\n");

            }

        }

        return;

    }

    while (q--) {

        int flag;

        scanf("%d", &flag);

        if (flag == ) {

            int pos;

            LL val;

            scanf("%d%lld", &pos, &val);

            pos++;

            LL now = (get_sum(pos) + MOD - get_sum(pos - )) % MOD;

            upDate(pos, -now);

            upDate(pos, val * powx[pos - ] % MOD);

        } else {

            int L, R;

            scanf("%d%d", &L, &R);

            L++;

            R++;

            LL now = (get_sum(R) - get_sum(L - ) + MOD) % MOD;

            if (now == ) {

                printf("Yes\n");

            } else printf("No\n");

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

Polynomial Division 数学题

最新文章

热门文章