bzoj 4918: 回文数对

发布时间:2017-7-9 7:02:52编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"bzoj 4918: 回文数对 ",主要涉及到bzoj 4918: 回文数对 方面的内容,对于bzoj 4918: 回文数对 感兴趣的同学可以参考一下。

#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;ll n,m,T,f[51][16];ll min(ll a,ll b){return a<b?a:b;}ll work(ll n,ll a,ll b){    ll MMH=0;    memset(f,0,sizeof(f));    f[0][3]=1;    for (ll i=1;i<=(n>>1);i++)    for (ll qa=0;qa<2;qa++)    for (ll qb=0;qb<2;qb++)    for (ll ha=0;ha<2;ha++)    for (ll hb=0;hb<2;hb++)    if ((qa^qb)==(ha^hb)&&(i!=1||qa!=qb)){        ll QA=(a>>n-i)&1,QB=(b>>n-i)&1;        ll HA=(a>>i-1)&1,HB=(b>>i-1)&1;                for (ll k=0;k<16;k++){            ll K=k;            if (QA<qa&&!(k&8)) continue;            if (QB<qb&&!(k&4)) continue;                        if (QA>qa) K|=8;            if (QB>qb) K|=4;                        if (HA>ha) K|=2;else if (HA<ha) K&=13;            if (HB>hb) K|=1;else if (HB<hb) K&=14;            f[i][K]+=f[i-1][k];        }    }        if (n&1){        ll i=n+1>>1;        for (ll _a=0;_a<2;_a++)        for (ll _b=0;_b<2;_b++)        if (n!=1||_a!=_b){            ll A=(a>>i-1)&1,B=(b>>i-1)&1;                        for (ll k=0;k<16;k++){                ll K=k;                if (A<_a&&!(k&8)) continue;                if (B<_b&&!(k&4)) continue;                                if (A>_a) K|=8;                if (B>_b) K|=4;                f[i][K]+=f[i-1][k];            }        }    }    ll i=n+1>>1;    for (ll k=0;k<16;k++)    if (((k&8)||(k&2))&&((k&4)||(k&1))) MMH+=f[i][k];    return MMH;}ll Mavis(ll a,ll b){    if (b<0) return 0;    ll i,j,k,mmh=0;    for (i=40,j=0,k=0;i;i--){        j<<=1;k<<=1;j|=(a>>i)&1;k|=(b>>i)&1;        if (j==k) mmh+=j*work(i,(1ll<<i)-1,(1ll<<i)-1)+work(i,a&((1ll<<i)-1),b&((1ll<<i)-1));else mmh+=k*work(i,(1ll<<i)-1,(1ll<<i)-1)+work(i,(1ll<<i)-1,b&((1ll<<i)-1));    }    return mmh+b+1;}int main(){    scanf("%lld",&T);    while(T--){        scanf("%lld%lld",&n,&m);        printf("%lld\n",Mavis(m,m)-2*Mavis(m,n-1)+Mavis(n-1,n-1));    }}
View Code


上一篇:android 自动化测试案例之 MonkeyScript
下一篇:使用excel进行数据挖掘(2)----分析关键影响因素

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款