NC19772. 生命游戏
描述
输入描述
五个整数，N, x1, y1, x2, y2, 表示需要计算的时长为 N，两个细胞的坐标分别为 (x1, y1), (x2, y2).
输出描述
一个整数，表示 1 ~ N 时刻所有细胞个数之和。
示例1
输入:
3 0 0 2 2
输出:
14
说明:
第1个时刻的细胞有：(0, 0), (1, 1)C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2019-10-11 23:40:44
#include <ctime>
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <queue>
#include <bitset>
#include <string>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;
namespace cell_xor_split{//一个细胞在屏幕上分裂向四周扩散，偶数个消失，奇数个保留，原位置不保留
typedef __int128 ll;
ll _one_cell_after_n_step(int n){//一个细胞在n秒后剩下个数
ll ans = 1;
while (n) {
ans *= 4;
n -= n & -n;
}
return ans;
}
inline short did(short x) {
return x < 0 ? (x - 1) / 2: (x == 0 ? 0 : x / 2);
}
ll _1D_hit_after_n_step(int x, int n) {//求单个维度下n步的冲突
ll f[2][5] = {0};//0, 1为借位 2， 1， 2为不借位， 3， 4 为进位1， 2
f[0][2] = 1;
bool bz = 0, bz1 = 1;
for (int bit = 1; bit < (1 << 30); bit <<= 1, swap(bz, bz1)) {
memset(f[bz1], 0, sizeof(f[bz1] ));
int v = ((n & bit) > 0) + 1;
for (int i = -2; i <= 2; i ++){
if (((i + 2) & 1) != ((x & bit) > 0)) continue;
f[bz1][did(i) + 2] += f[bz][i + 2] * v;
}
if (v == 2) {
for (int i = -2; i <= 2; i ++)
for (int j = -2; j <= 2; j += 4){
if (((i + j + 4) & 1) != ((x & bit) > 0)) continue;
f[bz1][did(i + j) + 2] += f[bz][i + 2];
}
}
}
return f[bz][0 + 2];
}
ll _two_cell_hit_after_n_step(int x1, int y1, int x2, int y2, int n) {//两个细胞n秒撞在一起的部分
x2 = abs(x2 - x1), y2 = abs(y2 - y1);
int x = (x2 + y2) , y = (abs(x2 - y2)) ;//旋转45°，相当于切比雪夫变换
return _1D_hit_after_n_step(x, n) * _1D_hit_after_n_step(y, n);
}
ll _two_cell_after_n_step(int x1, int y1, int x2, int y2, int n) {//两个细胞相互作用后的结果
return (_one_cell_after_n_step(n) - _two_cell_hit_after_n_step(x1, y1, x2, y2, n)) * 2;
}
ll _one_cell_after_0_n_step(int n){//一个细胞在n秒后剩下个数
ll f[2][2] = {0};
bool bz = 0, bz1 = 1;
f[0][1] = 1;
for (int i = 30; i >= 0 ;swap(bz, bz1), i --) {
memset(f[bz1], 0, sizeof(f[bz1]));
for (int j = 0; j < 2; j++) {
int r = 1;
if (j) r = ((n >> i) & 1);
for (int k = 0; k <= r; k++)
f[bz1][(k == r) && j] += (f[bz][j] << (k << 1));
}
}
return f[bz][1] + f[bz][0];
}
int ind(vector<int> d) {
int x = 0;
for (auto u:d)
x = x * 5 + u + 2;
return x;
}
void work(ll*fbz, ll*fbz1, bool n_bit, int bit, vector<int>&d, int id, int wbz, int wbz1, ll v) {
if (id == d.size()) {
fbz1[wbz1] += fbz[wbz] * v;
return;
}
int x = d[id];
for (int i = -2; i <= 2; i ++) {
if (((i + 2) & 1) != ((x & bit) > 0)) continue;
work(fbz, fbz1, n_bit, bit, d, id + 1, wbz * 5 + i + 2, wbz1 * 5 + did(i) + 2, (v << n_bit));
}
if (n_bit) {
for (int i = -2; i <= 2; i++)
for (int j = -2; j <= 2; j += 4) {
if (((i + j + 4) & 1) != ((x & bit) > 0)) continue;
work(fbz, fbz1, n_bit, bit, d, id + 1, wbz * 5 + i + 2, wbz1 * 5 + did(i + j) + 2, v);
// f[bz1][sig1][did(i + j) + 2] += f[bz][sig][i + 2];
}
}
/*for (int ix = -2; ix <= 2; ix++) {
if (((ix + 2) & 1) != ((x & bit) > 0)) continue;
for (int iy = -2; iy <=)
f[bz1][sig1][did(ix) + 2] += f[bz][sig][ix + 2] * v;
}
if (v == 2) {
}*/
}
ll _mD_hit_after_0_n_step(vector<int>&d, int n) {//求多个维度下0~n步的冲突
ll f[2][2][100] = {0};//0, 1为借位 2， 1， 2为不借位， 3， 4 为进位1， 2
vector<int>v(d.size(), 0);
f[0][0][ind(v)] = 1;
bool bz = 0, bz1 = 1;
for (int bit = 1; bit < (1 << 30); bit <<= 1, swap(bz, bz1)) {
memset(f[bz1], 0, sizeof(f[bz1]));
for (int sig = 0; sig < 2; sig ++) {
for (int n_bit = 0; n_bit < 2; n_bit ++) {
bool sig1 = max(sig + n_bit - ((n & bit) > 0), 0);
int v = n_bit + 1;
work(f[bz][sig], f[bz1][sig1], n_bit, bit, d, 0, 0, 0, 1);
}
}
}
return f[bz][0][ind(v)];
}
ll _two_cell_hit_after_0_n_step(int x1, int y1, int x2, int y2, int n) {//两个细胞0~n秒撞在一起的部分
x2 = abs(x2 - x1), y2 = abs(y2 - y1);
vector<int>d;
d.push_back(x2 + y2), d.push_back(abs(x2 - y2));
return _mD_hit_after_0_n_step(d, n);
}
ll _two_cell_after_0_n_step(int x1, int y1, int x2, int y2, int n) {//两个细胞相互作用后的结果
return (_one_cell_after_0_n_step(n) - _two_cell_hit_after_0_n_step(x1, y1, x2, y2, n)) * 2;
}
}
using namespace cell_xor_split;
void output(ll x){
vector<int> d;
while (x) d.push_back(x % 10), x /= 10;
reverse(d.begin(), d.end());
for (auto u:d)
printf("%d",u);
}
int main() {
int n, x1, y1, x2, y2;
cin>>n>>x1>>y1>>x2>>y2;
output(cell_xor_split::_two_cell_after_0_n_step(x1, y1, x2, y2, n - 1));
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 484K, 提交时间: 2018-10-05 21:22:32
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define Id(a,b) ((a)*2+(b))
using namespace std;
typedef __int128 LL;
typedef double db;
LL solve1(LL n){
LL ret=0;
LL pre=1;
fd(i,30,0){
ret=ret*5;
if ((n&(1<<i))>0){
ret=ret+pre;
pre=pre*4;
}
}
return ret;
}
LL f[40][7][7];//-3..3
LL solve2(LL n,LL x,LL y){
fd(i,30,0){
fo(vx,0,6){
fo(vy,0,6){
fo(ax,-2,2)
fo(ay,-2,2)
if ((ax+ay)%2==0&&abs(ax)+abs(ay)<=2){
LL v=max(abs(ax),abs(ay));
v=1<<(2-v);
if (ax==0&&ay==0)v=v+1;
int vx_=(vx-3)*2+ax+3-((x&(1<<i))>0),vy_=(vy-3)*2+ay+3-((y&(1<<i))>0);
if (vx_>=0&&vx_<7&&vy_>=0&&vy_<7){
f[i][vx_][vy_]+=f[i+1][vx][vy]*v;
}
}
}
}
if ((n&(1<<i))>0){
LL val[7][7];
fo(vx,0,6)fo(vy,0,6)val[vx][vy]=0;
val[3][3]=1;
fd(w,30,i){
LL tmp[7][7];
fo(vx,0,6)fo(vy,0,6){tmp[vx][vy]=val[vx][vy];val[vx][vy]=0;}
if (w==i||((n&(1<<w))==0)){
fo(vx,0,6)
fo(vy,0,6){
int vx_=(vx-3)*2+3-((x&(1<<w))>0),vy_=(vy-3)*2+3-((y&(1<<w))>0);
if (vx_>=0&&vx_<7&&vy_>=0&&vy_<7)val[vx_][vy_]+=tmp[vx][vy];
}
}
else
fo(vx,0,6){
fo(vy,0,6){
fo(ax,-2,2)
fo(ay,-2,2)
if ((ax+ay)%2==0&&abs(ax)+abs(ay)<=2){
int v=max(abs(ax),abs(ay));
v=1<<(2-v);
int vx_=(vx-3)*2+ax+3-((x&(1<<w))>0),vy_=(vy-3)*2+ay+3-((y&(1<<w))>0);
if (vx_>=0&&vx_<7&&vy_>=0&&vy_<7){
val[vx_][vy_]+=tmp[vx][vy]*v;
}
}
}
}
}
fo(a,0,6)fo(b,0,6)f[i][a][b]+=val[a][b];
}
}
LL ret=f[0][3][3];
return ret;
}
int digiw,digi[1000];
void putans(LL v){
if (v==0){putchar('0');putchar('\n');return;}
for(;v;v=v/10)digi[++digiw]=v%10;
for(;digiw;digiw--)putchar('0'+digi[digiw]);
putchar('\n');
}
int main(){
int n,x1,y1,x2,y2;
cin>>n>>x1>>y1>>x2>>y2;
LL x=abs(x1-x2),y=abs(y1-y2);
LL ans=solve1(n)-solve2(n,x,y);
ans=ans*2;
putans(ans);
return 0;
}