Atcoder abc338

發表於 更新於 分類於 ， Disqus： 文章字數： 589 所需閱讀時間 ≈ 2 分鐘
G(矩阵乘法)

https://atcoder.jp/contests/abc338

G - evall

给定字符串S,由123456789+*组成

最开始和最后的字符是数字，没有相邻的非数字

对于$(i\le j)$, 如果s[i],s[j]都是数字，则eval(i,j)为这一段字符串的表达式结果

否则 为0

求 $\displaystyle \sum_{i=1}^{|S|}\sum_{i=j}^{|S|} eval(i,j)\mod 998244353$

$|S| \le 10^6$

2s

1024mb

我的思路

这里虽然没有括号，但是有乘法的优先运算

如果固定前面

1
2
3
1234123*234*345+3245*145+324*45*345
[............]
fix          i->

那我们得到的是 [base + prodbase * (cur=34)]

每次遇到数字就是cur*=10,cur+=int(s[i])

而进入新的乘法则是prodbase*=cur, cur = 0

而进入新的加法则是base+=prodbase*cur,prodbase=1,cur=0

这个方法的问题在于 如果想用矩阵表示，那么在做prodbase * cur的时候 无法做这个乘法

再增加prodres东西

1
2
3
4
5
6
1234123*234*345+3245*145+324*45*345
                                 i
[base                  ]          
                         xxxxxx      prodbase 
                                xx   cur
                         xxxxxxxxx   prodres

ans = base + prodres

prodres = prodbase * cur, 而新的转移 发现cur不需要了

那么 遇到数字时,

1
2
3
4
5
6
			sumall     base prodres    prodbase    1
sumall        1 
base          1         1     
prodres      10                 10
prodbase   int(char)         int(char)     1  
1                                                  1

那么 遇到+时,

1
2
3
4
5
6
			sumall    base prodres    prodbase     1
sumall        1 
base                   1          
prodres                1                
prodbase            
1                                         1        1

那么 遇到*时,

1
2
3
4
5
6
			sumall    base prodres    prodbase    1
sumall        1 
base                   1          
prodres                                   1               
prodbase            				       
1                                                 1

所以，后缀矩阵乘法就秒了

前置的是[0,0,0,1,1]

代码

https://atcoder.jp/contests/abc338/submissions/50121997

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=5;
using matrix=array<array<mint,N>,N>;
matrix add(){
  return matrix{{
    {{1,0,0,0,0}},
    {{0,1,0,0,0}},
    {{0,1,0,0,0}},
    {{0,0,0,0,0}},
    {{0,0,0,1,1}},
  }};
}
matrix mul(){
  return matrix{{
    {{1,0,0,0,0}},
    {{0,1,0,0,0}},
    {{0,0,0,1,0}},
    {{0,0,0,0,0}},
    {{0,0,0,0,1}},
  }};
}
matrix num(int i){
  return matrix{{
    {{1 ,0, 0,0,0}},
    {{1 ,1, 0,0,0}},
    {{10,0,10,0,0}},
    {{i ,0, i,1,0}},
    {{0 ,0, 0,0,1}},
  }};
}
matrix operator*(const matrix&A,const matrix&B){
  matrix C;
  rep(i,0,N)rep(j,0,N) {
    C[i][j]=0;
    rep(k,0,N) C[i][j]+=A[i][k]*B[k][j];
  }
  return C;
}

char s[1000010];
int main(){
  scanf("%s",s);
  int n=strlen(s);
  matrix A;
  rep(i,0,N) A[i][i]=1;
  mint ans=0;
  auto res=[&](const matrix&M){return M[3][0]+M[4][0];}; // ([0,0,0,1,1] * M)[0][0]
  per(i,0,n) {
    matrix B;
    if(s[i]=='+') B=add();
    else if(s[i]=='*') B=mul();
    else B= num(s[i]-'0');
    A=B*A;
    if(s[i] != '+' and s[i] != '*') ans += res(A);
  }
  printf("%d\n",ans.val());
  return 0;
}

总结

G: 没啥难度，想起来写起来都很顺