Dashboard - The 14-th BIT Campus Programming Contest - Codeforces

题解；

题目要求求出所有多项式的和，可得出每一个出现的符号位是’+‘或’-‘的概率相同，而’+''-'后面的算式都相同，可得出只需计算所有可能的多项式中第一个数字的和；用第一个标识符将第一个数字和后面的多项式分隔开，又因为符合可能是‘+’‘-’两种可能，则最后答案即为 s[ i-1 ]*num[ n-i ]*2

s[ k ]：记录k位能表示的所有数字的和 (1+n)*n/2

num[ k ]：k 位多项式有多少个；k位多项式的开头一定是数字，第二位可能是符号

递推公式 num[ i ]=10*num[ i-1 ]+10*2*num[ i-2 ]

*记得写快速幂

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll>pi;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
const int N=5e5+5;inline ll read(){  //__int128 可以换成 int longlong 基于自己的需求即可ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int T,n;
ll s[N],num[N];
inline ll quickp(ll base,ll pow=mod-2){ll res=1;while(pow){if(pow&1)res=res*base%mod;pow>>=1;base=base*base%mod;}return res;
} int main(){T=read();num[1]=10;num[2]=100;s[1]=45;s[2]=4950;for(int i=3;i<N;i++){ll tmp=quickp(10,i); s[i]=(tmp*(tmp-1)/2)%mod;num[i]=(num[i-1]*10%mod+num[i-2]*20%mod)%mod; }while(T--){n=read();ll res=s[n];for(int i=2;i<n;i++){res=(res+s[i-1]*num[n-i]%mod*2)%mod; }printf("%lld\n",res); }return 0;
}