模拟+算贡献—

比赛的时候没看到模数，用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;

}

巴特西

模拟+算贡献——cf1195D

最新文章

热门文章