长沙集训Ⅱ——Day9

荣耀火影 · 2019-08-28 07:46:24 · 个人记录

T1

异或统计

（本题代码由于常数较大，最后三个点会被卡。）

#include<cstdio>
#include<cstring>
using namespace std;

inline long long read()
{
    long long res=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
    return res;
}
inline void write(long long x)
{
    int s[20],top=0;
    while(x) s[++top]=x%10,x/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}

typedef long long ll;
const ll N=1e5+10,p=998244353;
ll n,s[40],a[N],f[N],g[N],sum[40][2],ans;

inline bool bit(ll x,ll y) { return (x>>y)&1; }
inline void solve(ll x)
{
    ll s0=1;
    for(ll k=0;k<=30;k++)
    {
        memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); 
        memset(sum,0,sizeof(sum));

        for(ll i=1;i<=n;i++)
        {
            for(ll j=0;j<=30;j++) (f[i]+=s[j]*sum[j][bit(a[i],j)^1]%p)%=p;
            if(bit(a[i],k)==x) 
                for(int j=0;j<=30;j++) (sum[j][bit(a[i],j)]+=1)%=p;
        }

        memset(sum,0,sizeof(sum));

        for(ll i=n;i>=1;i--)
        {
            for(ll j=0;j<=30;j++) (g[i]+=s[j]*sum[j][bit(a[i],j)^1]%p)%=p;
            if(bit(a[i],k)!=x) 
                for(int j=0;j<=30;j++) (sum[j][bit(a[i],j)]+=1)%=p;
        }

        for(ll i=1;i<=n;i++) (ans+=s0*f[i]%p*g[i]%p)%=p;
        (s0<<=1)%=p;
    }
    return;
}

int main()
{
    n=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    s[0]=1;
    for(ll i=1;i<=30;i++) s[i]=(s[i-1]<<1)%p;
    solve(1); solve(0);
    write(ans);
    return 0;
}

T2

集合统计

#include<cstdio>
using namespace std;

inline long long read()
{
    long long res=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
    return res;
}
inline void write(long long x)
{
    long long s[20],top=0;
    while(x) s[++top]=x%10,x/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}

const long long p=1e9+7;
long long n,k,m,f[5010][5010],ans;

inline long long pow(long long x,long long y)
{
    long long res=1;
    while(y)
    {
        if(y&1) res=res*x%p;
        x=x*x%p;
        y>>=1;
    }
    return res;
}

int main()
{
    n=read(); k=read(); m=read();
    f[0][0]=1; f[1][1]=1;
    for(long long i=1;i<=n;i++)
    for(long long j=1;j<=k;j++)
        if(f[i][j])
        {
            if(i<n&&j<k) (f[i+1][j+1]+=f[i][j])%=p;
            if(i+j<n) (f[i+j][j]+=f[i][j])%=p;
        }
    for(long long x=1;x<=n;x++)
    for(long long y=1;y<=k&&x*y<=n;y++)
    {
        long long tmp;
        tmp=f[n-x*y][k-y]%p;
        if(x*(y+1)<=n&&y+1<=k) tmp=(p+tmp-f[n-x*(y+1)][k-(y+1)])%p;
        (ans+=y*pow(x,m)%p*tmp%p)%=p;
    }
    write(ans);
    return 0;
}

T3

异或统计2

#include<cstdio>
using namespace std;

typedef long long ll;
const ll p=998244353;
inline ll read()
{
    ll res=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
    return res;
}
inline void write(ll x)
{
    int s[20],top=0;
    while(x) s[++top]=x%10,x/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}

ll n,k,ans;

inline ll pow(ll x,ll y)
{
    ll res=1;
    while(y)
    {
        if(y&1) (res*=x)%=p;
        (x*=x)%=p;
        y>>=1;
    }
    return res;
}

int main()
{
    n=read(); k=read();
    if(n&1)
    {
        for(ll b=30;b>=0;b--)
        {
            ll a=(1<<b);
            if(k&a)
            {
                ll lst=(k&((1<<b)-1))+1;
                (ans+=pow(2,p-b-2)*((pow((lst+a)%p,n)-pow((lst-a+p)%p,n)+p)%p)%p)%=p;
                break;
            }
        }
    }
    else
    {
        ans++;
        for(ll b=30;b>=0;b--)
        {
            ll a=(1<<b);
            if(k&a)
            {
                ll lst=(k&((1<<b)-1))+1;
                (ans+=pow(2,p-b-2)*((pow((lst+a)%p,n)+pow((lst-a+p)%p,n))%p-2*pow(lst,n)%p+p)%p)%=p;
            }
        }
    }
    ans=(p+pow(k+1,n)-ans)%p;
    write(ans);
    return 0;
}