比赛的时候没看到模数,用java大数在写,最后看到的时候已经慌了。。

把贡献算清楚就可以

下面是贡献的推导

  有五位数 abcde * 10个

  有两位数 fg * 3 个

  那么这两种数组成的情况就是 abcdfeg 或 abcfdge,现在只考虑五位数在前,两位数在后的情况,

  五位数的情况是abcd_e_,每个五位数出现了3次,那直接把10个五位数在每位上求和,然后这个五位数的贡献*3,

  两位数的情况是____f_g,每个两位数出现了10次,那么也直接把3个两位数在每位上求和,然后这个两位数的贡献*10

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define ll long long
#define mod 998244353
ll n,a[maxn],A[];
ll cnt[],x[][];
void calc(ll a){
ll len=,tmp=a,pos=;
while(tmp){
tmp/=;len++;
}
cnt[len]++; tmp=a;
while(tmp){
pos++;
x[len][pos]+=tmp%;
tmp/=;
}
} ll f(int i,int j){
ll res1=,res2=;
if(i>j){
for(int k=;k<=j;k++){
res2=(res2+x[j][k]*A[k*-]%mod)%mod;
res1=(res1+x[i][k]*A[k*]%mod)%mod;
}
for(int k=j+;k<=i;k++)
res1=(res1+x[i][k]*A[j+k]%mod)%mod;
}
else if(i==j){
for(int k=;k<=i;k++){
res2=(res2+x[j][k]*A[k*-]%mod)%mod;
res1=(res1+x[i][k]*A[k*]%mod)%mod;
}
}
else if(i<j){
for(int k=;k<=i;k++){
res2=(res2+x[j][k]*A[k*-]%mod)%mod;
res1=(res1+x[i][k]*A[k*]%mod)%mod;
}
for(int k=i+;k<=j;k++)
res2=(res2+x[j][k]*A[k+i]%mod)%mod;
}
return (res1*cnt[j]+res2*cnt[i]%mod)%mod;
} int main(){
cin>>n;
A[]=;
for(int i=;i<=;i++)A[i]=A[i-]*%mod;
for(int i=;i<=n;i++){
cin>>a[i];
calc(a[i]);
}
ll ans=;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(cnt[i] && cnt[j])
ans=(ans+f(i,j))%mod;
cout<<ans<<endl;
}
05-27 19:02