题解 P6553 【Strings of Monody】

· · 题解

这道题的题意很简单这里就不赘述了

首先看数据范围,n<=10^6, m<=10^3,肯定不能暴力求解了，但是对于这道题，1,4,5的所在位置对答案没有影响，所以我们可以分别记录1,4,5的数量，每次修改时维护这个数量就可以了,但是每次询问乘积时如果直接求的话会TLE,所以我们可以预处理出4,5的次幂来，每次询问直接调用就好了

注意模数是99824353，不要想当然 (Ctrl+C是个好东西)

下面是代码详解

#include<bits/stdc++.h>
#define MAXN 1000000
using namespace std;
typedef long long ll;
int m, tot[6], a[MAXN+5];
ll pow4[MAXN+5], pow5[MAXN+5];
const ll mod = 99824353;
int main()
{
    pow4[0] = pow5[0] = 1;//预处理4,5的次幂
    for(int i = 1; i <= MAXN; i++)
        pow4[i] = (pow4[i-1]*4) % mod, pow5[i] = (pow5[i-1]*5) % mod;
    char ch;
    int cnt = 0;
    while(ch = getchar(), ch != '\n')
    {//逗号表达式返回最后一个语句的值,这个while就是每次读入一个字符存到ch里,如果ch是换行就结束循环
        cnt++;
        a[cnt] = ch-'0';
        tot[a[cnt]]++;//数据只有1,4,5，可以直接用数组下标对应
    }
    scanf("%d", &m);
    while(m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);getchar();//注意这里要先用一个getchar()读掉r后面的空格,不然会RE
        for(int i = l; i <= r; i++)
        {
            int x = getchar()-'0';
            tot[a[i]]--;//原a[i]对应的数的数量减一
            tot[x]++;//新a[i]对应的数的数量加一
            a[i] = x;//一定要把a[i]换掉,不然重复更新的时候会出错
        }
        ll sum = (tot[1] + 4*tot[4] + 5*tot[5]) % mod;
        ll p = (pow4[tot[4]] * pow5[tot[5]]) % mod;//已经预处理过4,5的次幂了,直接调用就可以 (没有1的原因都懂)
        printf("%d %lld %lld\n", tot[1], sum, p);//注意longlong要用%lld,不然会见祖宗的
    }
    return 0;
}