CodeForces 1195D Submarine in the Rybinsk Sea （算贡献）
传送门
思路：
n的大小为1e5，n^2枚举不现实，考虑每个数的贡献。
先看easy版本的，即所有的数长度都相同。那么每个数可以有n次在前面，n次在后面。
比如说12，33：
12和12组合得到1122，12和33得到1323：在这两个里12的贡献都是1020（只看前面的部分）
12和12组合得到1122，33和12组合得到3132：在这两个里12的贡献都是102（只看后面的部分）
也就是说12对答案的贡献为n*（102+1020）(n=2)。
这样枚举每一个数计算就可以。
再看hard版本，所有的数长度都不同。但是每个数对于不同长度的贡献都是确定的，可以枚举所有的长度（1-10），求一个贡献的总和。然后就不是很会实现。
代码：
easy
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define x first #define y second const int maxn=1e5+10; const ll mod=998244353; ll a[25]; ll cul(ll x){ ll res=0,cnt=0,t=x,tot=0; while(t){ cnt++;t/=10; } t=x; for(int i=0;i<cnt;i++){ a[tot++]=t%10; a[tot++]=t%10; t/=10; } for(int i=2*cnt-1;i>=0;i--){ res=(res*10+a[i])%mod; } return res; } int main(){ ll res=0; int n;cin>>n; for(int i=1;i<=n;i++){ ll x;cin>>x; res=(res+cul(x)*n%mod)%mod; } cout<<res<<endl; return 0; }
hard
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+100; const ll mod=998244353; ll p[35],len[15]; ll a[maxn],b[35]; ll get_len(ll x){ return (ll)(log10(x)+1); } int main(){ p[0]=1; for(int i=1;i<=32;i++) p[i]=p[i-1]*10%mod; int n;cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; len[get_len(a[i])]++; //cout<<get_len(a[i])<<endl; } ll res=0; for(int i=1;i<=n;i++){ int cnt=0;ll t=a[i]; while(t){//把当前每一位数都分离出来 b[++cnt]=t%10;t/=10; } for(int j=1;j<=10;j++){//枚举所有的长度 ll sum=0; for(int k=1;k<=cnt;k++){ sum=(sum+b[k]*p[k-1+min(j,k)]%mod)%mod;//该数在前面的贡献 sum=(sum+b[k]*p[k-1+min(j,k-1)]%mod)%mod;//该数在后面的贡献 } res=(res+sum*len[j])%mod;//对长度为j的数贡献都相同，乘积即可 } } cout<<res<<endl; return 0; }
