replace

wjh15101051's space

卧薪尝胆，厚积薄发。

replace

Date: Tue Oct 16 14:27:29 CST 2018

In Category: NoCategory

Description：

给 $n$ 个 $k$ 位二进制数，求他们翻转后的值。

$1\leqslant n\leqslant 2^k,1\leqslant k\leqslant 25$

Solution：

预处理 $2^{14}$ 的翻转的值，询问时分两半查一下。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXV 14

int Rev[1 << MAXV];

inline int rev(int k)

{

	register int res = 0;

	for(register int i = 1;i <= 14;++i)

	{

		res = res << 1;

		if(k & (1 << (i - 1)))

		{

			res |= 1;

		}

	}

	return res;

}

inline void init()

{

	for(register int i = 0;i < (1 << MAXV);++i)

	{

		Rev[i] = rev(i);

	}

	return;

}

int n,k,s;

inline int my_rand()

{

	s = (214013ll * s + 2531011) & ((1 << k) - 1);

	return s;

}

int ans = 0;

inline void my_hash(int x)

{

	ans = ((long long)ans * 233 + x) % 99824353;

	return;

}

int main()

{

	freopen("replace.in","r",stdin);

	freopen("replace.out","w",stdout);

	init();

	cin >> n >> k >> s;

	for(register int i = 1;i <= n;++i)

	{

		register int x = my_rand();

		register int res = (Rev[x & ((1 << 14) - 1)] << 14) | Rev[x >> 14];

		res = res >> (28 - k);

		my_hash(res);

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}

In tag: 玄学

wjh15101051