既见君子

同济医学生的起落落落落人生记录

hdu 5632 Rikka with array

  这道题是前天BC73 div2的第三题,当时看到这道题的时候有一种一眼相中的感觉,特别喜欢这道题,特别想做,虽然不会做,但是比赛结束之后还是找到友善的wyj给我讲了这道题,真是数位dp好题。

 题意:

给一个长度<=10^300的序列,a[i]=i分解成二进制的1的个数,求a中的逆序对个数。

 题解:

 设f[i]表示[0,2^i-1]的答案,那么会发现一个非常巧妙的东西,f[i+1]其实就是一段f[i]和f[i]里面每个数的第i位都变为了1这样组合起来的答案,所以当我们把他们组合起来的时候他们内部的逆序对数是算出来了的,只用算一个在左边一个在右边的那些逆序对,就记一下两边1的个数为i的数有多少个就可以更新啦。

 最后统计答案的时候先转成二进制然后从高位到低位,数位dp,区间的合并是差不多的,只是1的个数变了而已。

 (唔其实yj有写更加详细的题解但是粘过来觉得不好所以就班门弄斧啦)

code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int mod=998244353;
const int maxn=1000+5;
int f[maxn],cnt[maxn][maxn],sum[maxn][maxn];
int bit[maxn];
struct bignum{
        int w[400];
        bignum operator -(const bignum &b){
                bignum c;
                memset(c.w,0,sizeof(c.w));
                c.w[0]=max(b.w[0],w[0]);
                for(int i=1;i<=c.w[0];++i){
                        if(w[i]<b.w[i]){
                                w[i]+=10;
                                w[i+1]-=1;
                        }
                        c.w[i]=w[i]-b.w[i];
                }
                while(!c.w[c.w[0]]&&c.w[0]>1) c.w[0]--;
                return c;
        }
        bool operator <=(const bignum &b){
                if(w[0]<b.w[0]) return true;
                if(w[0]>b.w[0]) return false;
                for(int i=w[0];i>=1;--i){
                        if(w[i]<b.w[i]) return true;
                        if(w[i]>b.w[i]) return false;
                }
                return true;
        }
        bignum operator +(const bignum &b){
                bignum c;
                memset(c.w,0,sizeof(c.w));
                c.w[0]=max(b.w[0],w[0])+1;
                for(int i=1;i<=c.w[0]-1;++i){
                        c.w[i]+=w[i]+b.w[i];
                        c.w[i+1]+=c.w[i]/10;
                        c.w[i]%=10;
                }
                while(!c.w[c.w[0]]&&c.w[0]>1) c.w[0]--;
                return c;
        }
        void print(){
                for(int i=w[0];i>=1;--i) printf("%d",w[i]);
                printf("\n");
        }
} Mi[maxn],st;
int now[maxn];
char s[maxn];
void prepare(){
        Mi[0].w[0]=1;
        Mi[0].w[1]=1;
        for(int i=1;i<=1000;++i)
                Mi[i]=Mi[i-1]+Mi[i-1];
        cnt[0][0]=1;
        sum[0][0]=1;
        for(int i=1;i<=1000;++i) sum[0][i]=1;
        for(int i=1;i<=1000;++i){
                cnt[i][0]=sum[i][0]=cnt[i-1][0];
                for(int j=1;j<=1000;++j) cnt[i][j]=(cnt[i-1][j]+cnt[i-1][j-1])%mod,sum[i][j]=(sum[i][j-1]+cnt[i][j])%mod;
                int ans=(2*f[i-1])%mod;
                for(int j=2;j<=1000;++j) ans+=((long long)cnt[i-1][j]*sum[i-1][j-2])%mod,ans%=mod;
                f[i]=ans;
         }
}
void convert(){
        memset(bit,0,sizeof(bit));
        for(int i=1000;i>=0;--i)
                if(Mi[i]<=st){
                        bit[i]=1;
                        st=st-Mi[i];
                }
}
int work(){
        int ans=0;
        memset(now,0,sizeof(now));
        int last=0;
        for(int i=1000;i>=0;--i)
                if(bit[i]){
                        ans+=f[i],ans%=mod;
                        for(int j=last+1;j<=1000;++j) ans+=((long long)now[j]*sum[i][j-last-1])%mod,ans%=mod;
                        for(int j=0;j+last<=1000;++j) now[j+last]+=cnt[i][j],now[j+last]%=mod;
                        last+=1;
                }
        return ans;
}
int main(){
        freopen("array.in","r",stdin);
        freopen("array.out","w",stdout);
        int T;
        scanf("%d",&T);
        prepare();
        bignum e;
        memset(e.w,0,sizeof(e.w));
        e.w[0]=e.w[1]=1;
        while(T--){
                scanf("%s",s);
                memset(st.w,0,sizeof(st.w));
                st.w[0]=strlen(s);
                for(int i=1;i<=st.w[0];++i)
                        st.w[i]=s[st.w[0]-i]-'0';
                st=st+e;
                convert();
                printf("%d\n",work());
        }
        return 0;
}

评论
热度(2)
©既见君子
Powered by LOFTER