2015
04-16

# Yummy Triangular Pizza

Pizzahat has released a new pizza with triangular shaped pieces. This pizza is composed of some equal-sized equilateral triangle. Moreover, all the triangles are connected. Also, if two triangles are directly connected, they must share a common edge.
How many different shapes of this kind of N-pieces pizza are there? Two patterns are considered as same if they can completely overlap after rotation and shifting (note that flipping is not included).

There are multiple test cases. The first line of input contains a single integer denoting the number of test cases.
For each test case, there is only one line with only one integer N denoting the number of pieces that can be used. (1 <= N <= 16)

There are multiple test cases. The first line of input contains a single integer denoting the number of test cases.
For each test case, there is only one line with only one integer N denoting the number of pieces that can be used. (1 <= N <= 16)

3
2
4
10

Case #1: 1
Case #2: 4
Case #3: 866

Hint
Case2：



#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <iostream>

#define lson l, m, rt << 1
#define rson m+1, r, rt<<1|1
using namespace std;

const int maxn = 100010;
int tree[maxn << 2];
int CLF[maxn<<2];
void PushUp(int rt){
tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);
}
void PushDown(int rt){
if(!CLF[rt]) return;
tree[rt<<1] = tree[rt<<1|1] = tree[rt];
CLF[rt] = 0;
CLF[rt<<1|1] = CLF[rt<<1] = 1;
}

void Build(int l, int r, int rt){
CLF[rt] = 0;
if(l == r){
int tmp;
scanf("%d", &tmp);
tree[rt] = tmp;
return;
}
int m = (l + r)>>1;
Build(lson);
Build(rson);
PushUp(rt);
}

void Change1(int l, int r, int rt, int L, int R, int x){
if(L <= l && r <= R){
tree[rt] = x;
CLF[rt] = 1;
return ;
}
int m = (l + r) >> 1;
PushDown(rt);
if(L <= m)
Change1(lson, L, R, x);
if(m < R)
Change1(rson, L, R, x);
PushUp(rt);
}
int gcd(int a, int b){
while(b){
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
void Change2(int l, int r, int rt, int L, int R, int x){
if(L <= l && r <= R && CLF[rt] && tree[rt] > x){
tree[rt] = gcd(tree[rt], x);
return;
}
if(l == r){
tree[rt] = gcd(tree[rt], x);
return ;
}
PushDown(rt);
int m = (l + r) >> 1;
if(L <= m && tree[rt<<1] > x)
Change2(lson, L, R, x);
if(m < R && tree[rt<<1|1] > x)
Change2(rson, L, R, x);
PushUp(rt);
}
void Query(int l, int r, int rt){
if(CLF[rt]){
for(int i = r - l + 1; i; i--){
printf("%d ", tree[rt]);
}
return;
}
if(l == r){
printf("%d ", tree[rt]);
return;
}
int m = (l + r) >> 1;
Query(lson);
Query(rson);
}
int main()
{
int n, t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
Build(1, n, 1);
int q;
scanf("%d", &q);
while(q--){
int c, l, r, num;
scanf("%d%d%d%d", &c, &l, &r, &num);
if(c == 1){
Change1(1, n, 1, l, r, num);
}
if(c == 2)
Change2(1, n, 1, l, r, num);
}
Query(1, n, 1);
printf("\n");
}
return 0;
}

import java.util.*;
public class  Main
{
final int maxn = 100010;
Scanner cin = new Scanner(System.in);
int[] tree = new int[maxn << 2];
int[] flag = new int[maxn << 2];
void PushUp(int rt){
tree[rt] = Math.max(tree[rt << 1], tree[rt<<1|1]);
}
void PushDown(int rt){
if(0 == flag[rt])
return;
tree[rt<<1] = tree[rt<<1|1] = tree[rt];
flag[rt<<1] = flag[rt<<1|1] = 1;
flag[rt] = 0;
}
void Build(int l, int r, int rt){
flag[rt] = 0;
tree[rt] = 0;
if(l == r){
tree[rt] = cin.nextInt();
flag[rt] = 1;
return;
}
int m = (l + r) >> 1;
Build(l, m, rt << 1);
Build(m + 1, r, rt<<1|1);
PushUp(rt);
}
void Change1(int l, int r, int rt, int L, int R, int x){
if(L <= l && r <= R){
tree[rt] = x;
flag[rt] = 1;
return;
}
PushDown(rt);
int m = (l + r)>>1;
if(L <= m)
Change1(l, m, rt << 1, L, R, x);
if(m < R)
Change1(m + 1, r, rt << 1|1, L, R, x);
PushUp(rt);
}
int gcd(int a, int b){
while(b != 0){
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
void Change2(int l, int r, int rt, int L, int R, int x){
if(L <= l && r <= R && flag[rt] == 1){
if(tree[rt] > x)
tree[rt] = gcd(tree[rt], x);
return;
}
PushDown(rt);
int m = (l + r) >> 1;
if(L <= m && tree[rt<<1] > x)
Change2(l, m, rt << 1, L, R, x);
if(m < R && tree[rt << 1|1] >  x)
Change2(m + 1, r, rt << 1|1, L, R, x);
PushUp(rt);
}
int fl = 0;
void Query(int l, int r, int rt){
if(1 == flag[rt]){
for(int i = r – l; i >= 0; i–)
{
System.out.print(tree[rt]);
System.out.print(‘ ‘);
}
return;
}
int m = (l + r) >> 1;
Query(l, m, rt<<1);
Query(m + 1, r, rt << 1|1);
return ;
}
void go()
{
int t = 0;
t = cin.nextInt();
while(t != 0){
t–;
fl = 0;
int n = cin.nextInt();
Build(1, n, 1);
int q = cin.nextInt();
int c, l, r, x;
for(int i = 0; i < q; i++){
c = cin.nextInt();
l = cin.nextInt();
r = cin.nextInt();
x = cin.nextInt();
if(c == 1)
Change1(1, n, 1, l, r, x);
if(c == 2)
Change2(1, n, 1, l, r, x);
}
Query(1, n, 1);
System.out.println("");
}
cin.close();
return;
}
public static void main(String[] args){
Main ma = new Main();
ma.go();
}