题目链接：

J - 金色传说

 Gym - 102174J 

题目大意：

合法的表达式个数。

具体思路：

因为有加减，所以当我们枚举到某一位的时候，如果当前这一位是加号或者减号，那么后面的就可以抵消掉了，所以这是一个很大的优化，但是注意这种情况前面的会重复加，所以需要计算出重复的次数。

len[i]代表当长度为i的合法情况总数。

sum[i]代表长度为i并且为纯数字的情况总数。

所以len[n] = sigma((1<=i<=n-2))(sum[n-i-1]*2*len[i]);

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define inf 0x3f3f3f3f
 4 # define ll long long
 5 const int maxn = 2e6+100;
 6 const int N = 5e5+10;
 7 const int mod = 998244353;
 8 ll sum[maxn],len[maxn];
 9 ll qsm(ll t1,ll t2)
10 {
11     ll res=1ll;
12     while(t2)
13     {
14         if(t2&1)
15             res=res*t1%mod;
16         t2>>=1;
17         t1=t1*t1%mod;
18     }
19     return res;
20 }
21 void init()
22 {
23     sum[1]=45ll;
24     sum[2]=4950ll;
25     len[1]=10ll;
26     len[2]=100ll;
27     for(int i=3; i<N; i++)
28     {
29         ll tmp=qsm(10ll,i);
30         sum[i]=(tmp*(tmp-1ll)/2%mod);
31         len[i]=(10ll*2ll*len[i-2]%mod+10ll*len[i-1]%mod)%mod;
32     }
33 }
34 int main()
35 {
36     init();
37     int T;
38     scanf("%d",&T);
39     while(T--)
40     {
41         int n;
42         scanf("%d",&n);
43         ll ans=sum[n];
44         for(int i=1; i<=n-2; i++)
45         {
46             ans=(ans+sum[n-i-1]*2ll*len[i])%mod;
47         }
48         printf("%lld\n",ans%mod);
49     }
50     return 0;
51 }