2015
04-14

# The irRegularGame of Life

The irRegularGame of Life(http://www.bilibili.tv/video/av94917/) is an interesting game, it’s based on the same cell rules as Conway’s original, with the addition of limitations on initial conditions, and goals for completing levels.

The Conway’s original game of life rules is a "2-Dimensional cellular automaton". It was invented by British mathematician John Conway in 1970.It is not a game in the video game sense, but consists of a 2-D grid of cells. The game of life shouldn’t to be confused with Milton Bradley’s Board game of the same name.
Cells in the grid follow a few simple mathematical rules that determine whether they will live, die or multiply in the next generation.
Specifically, each cell interacts with its 8 horizontal, vertical, and diagonal neighbours, according to these 4 simple rules below:
1. Any live cell with fewer than 2 live neighbours dies through loneliness.
2. Any live cell with more than 3 live neighbours dies through overcrowding.
3. Any live cell with 2 or 3 live neighbours lives to the next generation.
4. Any dead cell with exactly 3 live neighbours comes to live.

Despite having such simple rules, the patterns that evolve are remarkable and can vary greatly from only small differences in initial conditions.
The game of life has fascinated mathematicians, computer scientists and nerdy types for decades.

This picture shows the rule of The irRegularGame of Life.

Sakuya thought this game is too simple, so he added some rules.
1.We have K (1<=K<=10) independent boxes in every level, and each box contains 4*4 grids.
2.The goal to pass a level is the sum of live cells in all boxes are exactly N (0<=N<=20) after T (0<=T<=200000) generations.
3.For those boxes, we can add at most M (0<=M<=20) cells.

Sakuya want know how many ways to pass one level?

As an example, initially we have one box as below.

The goal is to have exactly 5 live cells after 10 generations, and we can add at most one cell into the box.
There are 9 different ways to pass this level.

First an integer L (L <= 50), indicates there are L different levels.
For every level, the first line contains 4 integers, they are K, M, T and N which mentioned above.
Then, there are K 4*4 01-matrices follow, indicating the initial state of each box, 0 stands for an empty cell and 1 stands for an alive cell.

First an integer L (L <= 50), indicates there are L different levels.
For every level, the first line contains 4 integers, they are K, M, T and N which mentioned above.
Then, there are K 4*4 01-matrices follow, indicating the initial state of each box, 0 stands for an empty cell and 1 stands for an alive cell.

2

1 1 10 5
0 0 0 0
0 1 0 0
1 0 1 0
0 1 0 0

2 3 0 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Case #1: 9
Case #2: 4960
Hint
ATTENTION: It is to ALL the box that at most M cells are available to be add into, not to EACH box.
In the second sample, we can add 3 cells into two empty boxes and the goal is the sum of live cells in all boxes are exactly 3 after 0 generation, so we have C(32,3) = 4960 different ways.


k状态让i个死细胞活

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000009
#define pb push_back
vector <int> p[15];
int st[15];
int f[1<<16][20];
int to[15][20][20];
long long dp[15][25][25];
int num[1<<16];
int dx[]= {0,0,-1,1,1,1,-1,-1};
int dy[]= {-1,1,0,0,1,-1,1,-1};
int check(int x,int y)
{
if(x>=0
&& x<4
&& y>=0
&& y<4)return
1;
return 0;
}
int nxt(int t)
{
int ret=0;
rep(i,17)
{
int x=i/4;
int y=i%4;
int cnt=0;
for(int j=0; j<8; j++)
{
int nx =
x+dx[j];
int ny =
y+dy[j];
if(check(nx,ny))
{
int pos = nx*4+ny;
if((1<<pos)&t)
cnt++;
}
}
if((1<<i)&t)
{
if(cnt==2||cnt==3)
ret^=(1<<i);
}
else
{
if(cnt==3)
ret^=(1<<i);
}
}
return ret;
}
void init()
{
int n =
1<<16;
memset(num,0,sizeof(num));
rep(i,n)rep(j,17)
if(i&(1<<j))
num[i]++;
rep(i,n)f[i][0]=nxt(i);
for(int i=1;
i<=18; i++)
for(int j=0; j<n; j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int getnxt(int s,int t)
{
for(int i=18;
i>=0; i–)
if((1<<i)<=t)
{
t-=(1<<i);
s=f[s][i];
}
return s;
}
int main()
{
int L,K,M,T,N,t;
init();
scanf(“%d”,&L);
rep(cas,L)
{
scanf(“%d%d%d%d”,&K,&M,&T,&N);
rep(i,K)p[i].clear();
memset(st,0,sizeof(st));
rep(k,K)rep(i,4)rep(j,4)
{
scanf(“%d”,&t);
if(t)st[k]^=(1<<(i*4+j));
}
int n=1<<16;
memset(to,0,sizeof(to));
rep(k,K) // 10*2^16
rep(i,n)
if((st[k]&i) == st[k])
{
int j=i^st[k];
int cnt1=num[j];
int _nxt=getnxt(i,T);
int cnt2=num[_nxt];
to[k][cnt1][cnt2]++;
}
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int k=0; k<K; k++)
{
for(int
i=0; i<=M; i++)
{
for(int j=0;
j<=N; j++)
{
if(dp[k][i][j]==0)continue;
for(int p=0; p<=16; p++)
{
for(int
q=0; q<=16; q++)
{
if(to[k][p][q]==0)continue;
if(i+p<=M
&& j+q<=N)
dp[k+1][i+p][j+q]=(dp[k+1][i+p][j+q]+dp[k][i][j]*to[k][p][q])%mod;
}
}
}
}
}
long long ret=0;
for(int i=0; i<=M; i++)
ret=(ret+dp[K][i][N])%mod;
printf(“Case #%d: %I64d\n”,cas+1,ret);
}
}

1. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。