题目概述

ACL Beginner Contest E

解题报告

不知道各位数学课上有没有求过这个数列的通项公式……

$$ 9,99,999,9999,\cdots $$

其实就是 $10^n-1$ ，如果求 $k,kk,kkk,kkkk,\cdots$ 的话就是 ${k\over 9}(10^n-1)$ 。

（没想到通项公式也没事，数字只有9个，可以直接 $O(9n)$ 预处理）

直接线段树标记下传就行了。

解题报告

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<2,MOD=998244353,INV9=443664157;

int n,te,pw[maxn+5];
int l[maxt+5],r[maxt+5],val[maxt+5],tag[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<1)+(tot<<3)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Pushup(int p) {val[p]=((LL)val[p<<1]*pw[(r[p]-l[p]+1)>>1]%MOD+val[p<<1|1])%MOD;}
void Build(int L,int R,int p=1){
    l[p]=L;r[p]=R;if (L==R) {val[p]=1;return;} int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
void Addtag(int p,int K) {val[p]=(LL)(pw[r[p]-l[p]+1]-1)*INV9%MOD*K%MOD;tag[p]=K;}
void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
void Insert(int L,int R,int K,int p=1){
    if (L==l[p] && r[p]==R) return Addtag(p,K);
    Pushdown(p);int mid=l[p]+(r[p]-l[p]>>1);
    if (R<=mid) Insert(L,R,K,p<<1); else if (L>mid) Insert(L,R,K,p<<1|1);
    else Insert(L,mid,K,p<<1),Insert(mid+1,R,K,p<<1|1);
    Pushup(p);
}
int main(){
    freopen("E.in","r",stdin);freopen("E.out","w",stdout);
    readi(n);pw[0]=1;for (int i=1;i<=n;i++) pw[i]=(LL)pw[i-1]*10%MOD;Build(1,n);
    for (readi(te);te;te--){
        int L,R,K;readi(L);readi(R);readi(K);
        Insert(L,R,K);printf("%d\n",val[1]);
    }
    return 0;
}