龙老师获得了一个不寻常的计算器，因为这个道具的品质是金色传说。它除了在按 666666 时可以发出声音以外，还可以输入一个算式并计算出它的结果。金色传说计算器的显示屏上只有 nn 个可以显示的位置，而且只有 0?90?9 十个数字键和两个运算符键+、-共 1212 个按键可以按，连=都没有，所以必须输入一个 nn 位的合法算式，它才会自动计算出该算式的结果。
我们定义合法的算式为一个长度恰好为 nn 的字符串，其中字符串只包含数字 0?90?9 和运算符+、-，同时不允许算式第一个或最后一个位置出现运算符，也不允许同时有两个运算符相邻。算式的计算结果是对该字符串模拟十进制加减法运算得到的结果，只包含数字的算式其计算结果等于它本身。如果金色传说计算器的输入不是一个合法的算式，那么它就不能得到任何计算结果。例如，在 n=6n=6 时，1+2+3、+12345、23+45+和123+-4都不是合法的算式，而123456和0+0+00都是合法的算式。注意，前导零是允许在算式中出现的。
龙老师一个个地数出了计算器的显示位置数 nn。他想知道，如果把所有的合法的算式全都都输入一次，金色传说计算器输出的所有计算结果之和是多少？计算结果的总和可能很大，请输出它对 998244353998244353 取模之后的答案。
第一行输入一个正整数 T (1≤T≤100)T (1≤T≤100)，表示数据组数。
接下来 TT 组数据，每组数据输入一个正整数 n (1≤n≤5×105)n (1≤n≤5×105)，表示金色传说计算器的显示位。
对于每组数据，请输出一个非负整数，表示所有计算结果之和取模 998244353998244353 之后的答案，注意换行。
5 1 2 3 4 5
45 4950 500400 50103000 19816235
当 n=1n=1 时，共有 0,1,?,90,1,?,9 共 1010 个合法算式，它们的结果之和是 4545。
当 n=2n=2 时，共有 00,?,9900,?,99 共 100100 个合法算式，它们的结果之和是 49504950。
当 n=3n=3 时，000,?,999000,?,999 是合法的算式，当然与形如A+B和A-B的算式也都是合法算式，它们的结果之和是 500400500400。
solve:
首先任意假定一个式子12+23-3，那么一定有对应的式子12-23+3。那么他们的和就是12*2,也就是只和最前面的数有关，所以求总的和就是计算出
ans=最前面的数的所有情况的和*他们出现的次数。所以式子可以写成：k位数+子式子（符号也可以是负号，所有有2种情况）。我们只需要考虑前面的
k位数，后面的子式子就可以忽略了。
记sum[k]为k位数能构成的所有数的和，比如k=3，就是000~999的和。记num[m]为后面子式子位数为m时，能构成多少条式子，（就是最前面的数出现多少次）。
sum[k]很容易求，sum[k]=10^k*(10^k-1)/2，用一下等差数列求和。
下面观察num[m+1]与num[m] 的关系：
假设已知num[m]，第一位一定要是数字，所以变成m+1，只能在前面加一个数字（0~9）,就有10种情况，part1=num[m]*10；
原来位数为m时第一位记为a，可以看出a原来只能是数字，变成m+1后的时候，a变成式子的第二位，就可以变成+ or -。
这时m+1位就变成：第一位数字(0~9) ‘+,-‘ (m-1)位的式子。所以可以得到part2=num[m-1]*20;
所以得到num[m+1]=part1+part2=num[m]*10+num[m-1]*20。
代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<sstream> #include<vector> #include<stack> #include<deque> #include<cmath> #include<map> #define sd(x) scanf("%d",&x) #define ms(x) memset(x,0,sizeof x) #define fr(i,n) for(int i=1;i<=n;i++) using namespace std; typedef long long ll; const int maxn=5e5+50; const int mod=998244353; ll num[maxn],sum[maxn],p10; int main() { num[0]=1,num[1]=10,num[2]=100; p10=1; for(int i=1;i<=5e5;i++) { p10=p10*10%mod; sum[i]=p10*1LL*(p10-1)/2%mod; } for(int i=3;i<=5e5;i++) { num[i]=(10*num[i-1]%mod+20*num[i-2]%mod)%mod; } int T; cin>>T; while(T--) { int n; scanf("%d",&n); ll ans=0; for(int i=1;i<=n-2;i++) { ans+=2*sum[i]*num[n-i-1]%mod; //ans%=mod; 因为加了这句而T2 } ans=(ans+sum[n])%mod; cout<<ans<<endl; } return 0; }
原文：https://www.cnblogs.com/studyshare777/p/12885996.html