置换

来日方长 · 2018-10-23 16:10:40 · 个人记录

题目描述

negii 沉迷于研究计算机的构造，他发现简单的二进制竟然能完成如此复杂的计算，当他知道二进制的所有位运算的操作之后，他突发奇想，他想找一种方法能实现二进制位的翻转。具体地，就是我们要将7（0111）翻转成14（1110），11（1011）翻转成13（1101）。

现在我们给定二进制位数k 以及n 个满足二进制位数不超过k 的数，我们需要输出对应翻转后的数的十进制表示由于读入量较大，所以n 个数由本机随机生成，具体生成方式如下

int my_rand()
{
    Seed=(214013LL*Seed+2531011)&((1<<k)-1);
    return Seed;
}

我们会给出初始的Seed，我们会调用n 次函数，得到需要翻转的n 个数我们还会采取特殊的输出方式，我们将所有答案hash，并输出最后的值即可。

int ans=0;
void my_hash(int x)
{
    ans=((long long)ans*233+x)%99824353;
}

我们每得到一个数，进行翻转后，我们就会调用一次这个函数，其中传入参数x 为翻转后的数，我们最后输出ans 的值即可。

输入描述

共3 个数，分为n，k，Seed

输出描述

一行，一个整数，表示最后hash 值。

数据范围

对于前50% k<=17

对于前70% k<=20

对于前90% k<=23

对于 100% n<=2^k ,k<=25

题解

我看数据范围，发现直接O(k2^k)的暴力貌似过不去。然而这个数据范围是假的。

正解貌似是倍增预处理之后跑，然而常数太大跑得没暴力快。当然，这道题纯暴力不卡常是过不去的。

我们用类似快速幂的方法，把要反转的数的二进制数从前往后扫，直接乘上2^{k-i+1}。这样复杂度貌似是O(k2^k)，然而随机数据是跑不满的，而且这样常数很小，再加上一些优化就能跑得比正解快了。

AC代码：

#include<iostream>
#include<cstdio>
#define LL long long
#define reint register int
int sd,n,k,ans,hh;
int my_rand(){return sd=(214013LL*sd+2531011)&((1<<k)-1);}
void my_hash(int x){ans=((LL)ans*233+x)%99824353;}
void print(int x){if(x>9)print(x/10);putchar(x%10+'0');}
void read(int &in){
    in=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))in=in*10+(ch^48),ch=getchar();
    return;
}
int rev(int x){
    int rt=0,zz=hh;
    while(x){
        if(x&1)rt+=zz;
        zz>>=1,x>>=1;
    }return rt;
}
int main(){
    read(n),read(k),read(sd);hh=1<<(k-1);
    for(reint i=1;i<=n;i++)my_hash(rev(my_rand()));
    print(ans),putchar('\n');
    return 0;
}