UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213148#584. t31811260623100ms0kbC++1110.1kb2024-11-09 21:27:472024-11-09 23:21:06

answer

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
int n, m, op, l, r, x, a[100001];
struct tree
{
    int sum1, sum2, sum3, sum4, sum5, sum6, sum7, sum8, sum9, sum10, mul, add;
} tree[400001];
void work(int x, int len, int a, int b)
{
    tree[x].mul = tree[x].mul * b % MOD;
    tree[x].add = tree[x].add * b % MOD;
    tree[x].add = ((tree[x].add + a) % MOD + MOD) % MOD;
    if (b != 1)
    {
        tree[x].sum1 = tree[x].sum1 * b % MOD;
        tree[x].sum2 = (tree[x].sum2 * b % MOD) * b % MOD;
        tree[x].sum3 = ((tree[x].sum3 * b % MOD) * b % MOD) * b % MOD;
        tree[x].sum4 = (((tree[x].sum4 * b % MOD) * b % MOD) * b % MOD) * b % MOD;
        tree[x].sum5 = ((((tree[x].sum5 * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD;
        tree[x].sum6 = (((((tree[x].sum6 * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD;
        tree[x].sum7 = ((((((tree[x].sum7 * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD;
        tree[x].sum8 = (((((((tree[x].sum8 * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD;
        tree[x].sum9 = ((((((((tree[x].sum9 * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD;
        tree[x].sum10 = (((((((((tree[x].sum10 * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD) * b % MOD;
    }
    if (a != 0)
    {
        int a2 = a * a % MOD, a3 = a2 * a % MOD, a4 = a3 * a % MOD, a5 = a4 * a % MOD, a6 = a5 * a % MOD, a7 = a6 * a % MOD, a8 = a7 * a % MOD, a9 = a8 * a % MOD, a10 = a9 * a % MOD;
        tree[x].sum10 = ((tree[x].sum10 + len * a10 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 10ll * tree[x].sum9 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 45ll * tree[x].sum8 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 120ll * tree[x].sum7 % MOD * a3 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 210ll * tree[x].sum6 % MOD * a4 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 252ll * tree[x].sum5 % MOD * a5 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 210ll * tree[x].sum4 % MOD * a6 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 120ll * tree[x].sum3 % MOD * a7 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 45ll * tree[x].sum2 % MOD * a8 % MOD) + MOD) % MOD;
        tree[x].sum10 = ((tree[x].sum10 + 10ll * tree[x].sum1 % MOD * a9 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + len * a9 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 9ll * tree[x].sum8 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 36ll * tree[x].sum7 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 84ll * tree[x].sum6 % MOD * a3 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 126ll * tree[x].sum5 % MOD * a4 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 126ll * tree[x].sum4 % MOD * a5 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 84ll * tree[x].sum3 % MOD * a6 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 36ll * tree[x].sum2 % MOD * a7 % MOD) + MOD) % MOD;
        tree[x].sum9 = ((tree[x].sum9 + 9ll * tree[x].sum1 % MOD * a8 % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + len * a8 % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + 8ll * tree[x].sum7 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + 28ll * tree[x].sum6 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + 56ll * tree[x].sum5 % MOD * a3 % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + 70ll * tree[x].sum4 % MOD * a4 % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + 56ll * tree[x].sum3 % MOD * a5 % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + 28ll * tree[x].sum2 % MOD * a6 % MOD) + MOD) % MOD;
        tree[x].sum8 = ((tree[x].sum8 + 8ll * tree[x].sum1 % MOD * a7 % MOD) + MOD) % MOD;
        tree[x].sum7 = ((tree[x].sum7 + len * a7 % MOD) + MOD) % MOD;
        tree[x].sum7 = ((tree[x].sum7 + 7ll * tree[x].sum6 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum7 = ((tree[x].sum7 + 21ll * tree[x].sum5 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum7 = ((tree[x].sum7 + 35ll * tree[x].sum4 % MOD * a3 % MOD) + MOD) % MOD;
        tree[x].sum7 = ((tree[x].sum7 + 35ll * tree[x].sum3 % MOD * a4 % MOD) + MOD) % MOD;
        tree[x].sum7 = ((tree[x].sum7 + 21ll * tree[x].sum2 % MOD * a5 % MOD) + MOD) % MOD;
        tree[x].sum7 = ((tree[x].sum7 + 7ll * tree[x].sum1 % MOD * a6 % MOD) + MOD) % MOD;
        tree[x].sum6 = ((tree[x].sum6 + len * a6 % MOD) + MOD) % MOD;
        tree[x].sum6 = ((tree[x].sum6 + 6ll * tree[x].sum5 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum6 = ((tree[x].sum6 + 15ll * tree[x].sum4 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum6 = ((tree[x].sum6 + 20ll * tree[x].sum3 % MOD * a3 % MOD) + MOD) % MOD;
        tree[x].sum6 = ((tree[x].sum6 + 15ll * tree[x].sum2 % MOD * a4 % MOD) + MOD) % MOD;
        tree[x].sum6 = ((tree[x].sum6 + 6ll * tree[x].sum1 % MOD * a5 % MOD) + MOD) % MOD;
        tree[x].sum5 = ((tree[x].sum5 + len * a5 % MOD) + MOD) % MOD;
        tree[x].sum5 = ((tree[x].sum5 + 5ll * tree[x].sum4 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum5 = ((tree[x].sum5 + 10ll * tree[x].sum3 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum5 = ((tree[x].sum5 + 10ll * tree[x].sum2 % MOD * a3 % MOD) + MOD) % MOD;
        tree[x].sum5 = ((tree[x].sum5 + 5ll * tree[x].sum1 % MOD * a4 % MOD) + MOD) % MOD;
        tree[x].sum4 = ((tree[x].sum4 + len * a4 % MOD) + MOD) % MOD;
        tree[x].sum4 = ((tree[x].sum4 + 4ll * tree[x].sum3 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum4 = ((tree[x].sum4 + 6ll * tree[x].sum2 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum4 = ((tree[x].sum4 + 4ll * tree[x].sum1 % MOD * a3 % MOD) + MOD) % MOD;
        tree[x].sum3 = ((tree[x].sum3 + len * a3 % MOD) + MOD) % MOD;
        tree[x].sum3 = ((tree[x].sum3 + 3ll * tree[x].sum2 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum3 = ((tree[x].sum3 + 3ll * tree[x].sum1 % MOD * a2 % MOD) + MOD) % MOD;
        tree[x].sum2 = ((tree[x].sum2 + 2ll * tree[x].sum1 % MOD * a % MOD) + MOD) % MOD;
        tree[x].sum2 = ((tree[x].sum2 + len * a2 % MOD) + MOD) % MOD;
        tree[x].sum1 = ((tree[x].sum1 + len * a % MOD) + MOD) % MOD;
    }
}
void pushup(int x)
{
    tree[x].sum1 = (tree[x << 1].sum1 + tree[x << 1 | 1].sum1) % MOD;
    tree[x].sum2 = (tree[x << 1].sum2 + tree[x << 1 | 1].sum2) % MOD;
    tree[x].sum3 = (tree[x << 1].sum3 + tree[x << 1 | 1].sum3) % MOD;
    tree[x].sum4 = (tree[x << 1].sum4 + tree[x << 1 | 1].sum4) % MOD;
    tree[x].sum5 = (tree[x << 1].sum5 + tree[x << 1 | 1].sum5) % MOD;
    tree[x].sum6 = (tree[x << 1].sum6 + tree[x << 1 | 1].sum6) % MOD;
    tree[x].sum7 = (tree[x << 1].sum7 + tree[x << 1 | 1].sum7) % MOD;
    tree[x].sum8 = (tree[x << 1].sum8 + tree[x << 1 | 1].sum8) % MOD;
    tree[x].sum9 = (tree[x << 1].sum9 + tree[x << 1 | 1].sum9) % MOD;
    tree[x].sum10 = (tree[x << 1].sum10 + tree[x << 1 | 1].sum10) % MOD;
}
void build(int x, int l, int r)
{
    tree[x].add = 0;
    tree[x].mul = 1;
    if (l == r)
    {
        tree[x].sum1 = a[l];
        tree[x].sum2 = (tree[x].sum1 * tree[x].sum1) % MOD;
        tree[x].sum3 = (tree[x].sum1 * tree[x].sum2) % MOD;
        tree[x].sum4 = (tree[x].sum1 * tree[x].sum3) % MOD;
        tree[x].sum5 = (tree[x].sum1 * tree[x].sum4) % MOD;
        tree[x].sum6 = (tree[x].sum1 * tree[x].sum5) % MOD;
        tree[x].sum7 = (tree[x].sum1 * tree[x].sum6) % MOD;
        tree[x].sum8 = (tree[x].sum1 * tree[x].sum7) % MOD;
        tree[x].sum9 = (tree[x].sum1 * tree[x].sum8) % MOD;
        tree[x].sum10 = (tree[x].sum1 * tree[x].sum9) % MOD;
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(x);
}
void pushdown(int x, int l, int r)
{
    int mid = (l + r) >> 1;
    work(x << 1, mid - l + 1, tree[x].add, tree[x].mul);
    work(x << 1 | 1, r - mid, tree[x].add, tree[x].mul);
    tree[x].add = 0;
    tree[x].mul = 1;
}
void change(int x, int l, int r, int ll, int rr, int a, int b)
{
    if (ll <= l && r <= rr)
    {
        work(x, r - l + 1, a, b);
        return;
    }
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    if (ll <= mid)
        change(x << 1, l, mid, ll, rr, a, b);
    if (mid < rr)
        change(x << 1 | 1, mid + 1, r, ll, rr, a, b);
    pushup(x);
}
int query(int x, int l, int r, int ll, int rr, int k)
{
    if (ll <= l && r <= rr)
    {
        if (k == 1)
            return tree[x].sum1;
        if (k == 2)
            return tree[x].sum2;
        if (k == 3)
            return tree[x].sum3;
        if (k == 4)
            return tree[x].sum4;
        if (k == 5)
            return tree[x].sum5;
        if (k == 6)
            return tree[x].sum6;
        if (k == 7)
            return tree[x].sum7;
        if (k == 8)
            return tree[x].sum8;
        if (k == 9)
            return tree[x].sum9;
        if (k == 10)
            return tree[x].sum10;
    }
    pushdown(x, l, r);
    int mid = (l + r) >> 1, ans = 0;
    if (ll <= mid)
        ans += query(x << 1, l, mid, ll, rr, k);
    ans %= MOD;
    if (mid < rr)
        ans += query(x << 1 | 1, mid + 1, r, ll, rr, k);
    ans %= MOD;
    pushup(x);
    return ans % MOD;
}
signed main()
{
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld", &op);
        if (op == 1)
        {
            scanf("%lld %lld %lld", &l, &r, &x);
            change(1, 1, n, l, r, x, 1);
        }
        else if (op == 2)
        {
            scanf("%lld %lld %lld", &l, &r, &x);
            change(1, 1, n, l, r, x, 0);
        }
        else
        {
            scanf("%lld %lld %lld", &l, &r, &x);
            printf("%lld\n", query(1, 1, n, l, r, x));
        }
    }
    return 0;
}
源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 0
Runtime Error

input:

458 823
14431 9895 11970 15308 2575 20181 709 27999 12992 18884 11061 16281 5044 28990 25092 28337 3...

output:

result:

Test #2:

score: 0
Runtime Error

input:

481 526
8409 14498 18636 10027 24362 32458 17986 17730 11956 19192 2193 1034 29317 19284 16210 26242...

output:

result:

Test #3:

score: 0
Runtime Error

input:

100000 100000
15247 4194 9619 4532 22058 2667 21549 16652 25327 12018 13395 11426 7243 11714 22904 2...

output:

result:

Test #4:

score: 0
Runtime Error

input:

100000 100000
6264 26207 28424 24165 4852 20798 5803 18679 24588 12238 25786 28622 19900 101 25922 2...

output:

result:

Test #5:

score: 0
Runtime Error

input:

100000 100000
15043 9299 7163 25384 24996 3803 24356 12466 22073 12987 8931 14997 3951 32704 23076 8...

output:

result:

Test #6:

score: 0
Runtime Error

input:

100000 100000
14736 16956 19864 23894 29403 5507 12182 6188 17192 14440 18618 3970 15396 15037 23334...

output:

result:

Test #7:

score: 0
Runtime Error

input:

50000 50000
17799 29763 25337 21321 1391 31852 27418 28753 18524 14044 15976 18893 12274 22834 11348...

output:

result:

Test #8:

score: 0
Runtime Error

input:

50000 50000
10654 14956 14287 25326 8102 30579 11682 23553 272 22672 14460 30241 13026 12738 4912 72...

output:

result:

Test #9:

score: 0
Runtime Error

input:

90000 90000
29538 28214 24706 30393 27759 9002 13458 10243 15713 14881 10630 5593 7942 24578 29370 1...

output:

result:

Test #10:

score: 0
Runtime Error

input:

100000 100000
23515 49 31372 25112 16779 21279 30735 32743 14678 15189 1763 23114 32215 14873 20487 ...

output:

result:

中文 English

Server time: 2025-03-18 00:39:56 | 开源项目