2015
05-23

# Palindrome graph

In addition fond of programing, Jack also loves painting. He likes to draw many interesting graphics on the paper.
One day,Jack found a new interesting graph called Palindrome graph. No matter how many times to flip or rotate 90 degrees, the palindrome graph are always unchanged.
Jack took a paper with n*n grid and K kinds of pigments.Some of the grid has been filled with color and can not be modified.Jack want to know:how many ways can he paint a palindrome graph?

There are several test cases.
For each test case,there are three integer n m k(0<n<=10000,0<=m<=2000,0<k<=1000000), indicate n*n grid and k kinds of pigments.
Then follow m lines,for each line,there are 2 integer i,j.indicated that grid(i,j) (0<=i,j<n) has been filled with color.
You can suppose that jack have at least one way to paint a palindrome graph.

There are several test cases.
For each test case,there are three integer n m k(0<n<=10000,0<=m<=2000,0<k<=1000000), indicate n*n grid and k kinds of pigments.
Then follow m lines,for each line,there are 2 integer i,j.indicated that grid(i,j) (0<=i,j<n) has been filled with color.
You can suppose that jack have at least one way to paint a palindrome graph.

3 0 2
4 2 3
1 1
3 1

8
3

http://blog.csdn.net/acmmmm/article/details/10195947

1、从对称可以得到 方格可以分为对称的8瓣 所以我们用2条对角线和 2条中位线 把方格切成八瓣，每一瓣的方格数有 0 + 1 + 2 + …… + [n+1]/2  (方格数计算是包含分割线上的方格)

2、若不考虑已上过色的格子 方案就是 k^ (每一瓣的方格数)

3、把上过色的方格都投影到第一瓣方格中（注意存在对称同色的方格），则答案是 k^ ( 投影后剩下的方格数)

4、k较大，需要用快速幂计算

#include<stdio.h>
#include<string.h>
#define ll __int64
#define f(x) (x*(x+1))/2
#define MOD 100000007
ll quickpow(ll m,ll n)
{
ll b = 1;
while (n)
{
if (n&(ll)1)
b = (b*m)%MOD;
n >>=(ll)1;
m = (m*m)%MOD;
}
return b;
}
ll k;
int n,m;
bool map[5050][5050];

void PUT(int x){
for(int i=1;i<=x;i++){

for(int j=1;j<=x;j++)
printf("%d ",map[i][j]);
printf("\n");
}
printf("\n");
}

int Is(int x,int y){
int mid;
if(n&1)
{
mid=(1+n)>>1;
if(x>mid)x-=2*(mid-x);
if(y>mid)y-=2*(mid-y);
}
else
{
mid=n>>1;
if(x>mid)x=2*mid+1-x;
if(y>mid)y=2*mid+1-y;
}
if(map[x][y])return 0;
return map[x][y]=map[y][x]=1;
}
int main(){
int u,v;
while(~scanf("%d %d %I64d",&n,&m,&k)){
int num=0,z=n>>1;
for(int i=1;i<=z;i++)
for(int j=1;j<=z;j++)
map[i][j]=0;
while(m--)
{
scanf("%d%d",&u,&v);
num+=Is(1+u,1+v);
}

//		PUT(n);
n=(n+1)/2;
n=f(n)-num;
ll ans=quickpow(k,n);
printf("%I64d\n",ans);
}
return 0;
}
/*
3 0 2
4 2 3
1 1
3 1

5 3 999
0 0
0 1
0 2

*/

1. Pingback: Travis Scott Type beat

2. Pingback: ترمیم مو و کاشت مو

3. Pingback: sex toys for beginner

4. Pingback: massage vibrator

5. Pingback: طراحی سایت آموزشگاه

6. Pingback: Taekwondo middleweight uniform

7. Pingback: pocket rocket

8. Pingback: نصب دوربین های مدار بسته

9. Pingback: 18 inch dildo

10. Pingback: on site supplies

11. Pingback: Magnetic secondary glazing

12. Pingback: خرید اپل آیدی

13. Pingback: کفسابی در تهران

14. Pingback: sex gel

15. Pingback: موسسه حقوقی

16. Pingback: how to

17. Pingback: realistic dong

18. Pingback: best erotic games

19. Pingback: best wand vibrator

21. Pingback: Best Selling Vibrator

22. Pingback: Century ironman

23. Pingback: ماندگاری ترمیم مو

24. Pingback: driving tips

26. Pingback: Mikemaid 7447

28. Pingback: Cock ring

29. Pingback: تجهیزات مداربسته

30. Pingback: Anal toys

31. Pingback: triple stimulator

32. Pingback: massage after sex

33. Pingback: best glass dildo

34. Pingback: Dildo

35. Pingback: Butt plugs

36. Pingback: quotations

37. Pingback: gay anal sex toys

38. Pingback: bunny rabbit vibrator

39. Pingback: pleasure rabbit

40. Pingback: انواع دوربین مدار بسته

41. Pingback: couples toys

42. Pingback: php online store

43. Pingback: repossession

44. Pingback: Easyforex

45. Pingback: Microsoft software

46. Pingback: Orlando

47. Pingback: Trending Hip Hop

49. Pingback: Non-standard bearings

50. Pingback: ノロウイルス

51. Pingback: airfreight

52. Pingback: inspekce jerabu

54. Pingback: pc games for windows 8

55. Pingback: http://www.pouyaweb.co/

56. Pingback: adam and eve sex toys

57. Pingback: emergency room glendale

58. Pingback: ترمیم موی آقایان

59. Pingback: Lacigreen

60. Pingback: anal sex toys for women

62. Pingback: Savvy vibrator

63. Pingback: couple games

64. Pingback: sex toys for women

65. Pingback: پویا بین

66. Pingback: realistic red vibrator

67. Pingback: اپل ایدی خرید

68. Pingback: قیمت اجاره ویلا در لواسان

69. Pingback: anal sex toys

73. Pingback: خرید apple id

74. Pingback: magnetic labels

75. Pingback: تردمیل خانگی

76. Pingback: worktop protection

77. Pingback: site protection

78. Pingback: polythene

79. Pingback: magic massager

80. Pingback: sasha grey

81. Pingback: Sex Toys

82. Pingback: ted

83. Pingback: sex toys

85. Pingback: Sex Toys

86. Pingback: خرید اپل ایدی

87. Pingback: PHP Programmer

88. Pingback: giving her oral

89. Pingback: all american whopper dildo

90. Pingback: bullet vibrator review

92. Pingback: reddit stocks

93. Pingback: samuraiTV

94. Pingback: vpn خرید رایگان

95. Pingback: Bob Training bag

96. Pingback: anal sex toys

97. Pingback: adam and eve sex toy shop

98. Pingback: کفسابی

99. Pingback: lingerie

101. Pingback: Tunderkert

102. Pingback: tratamento de Alcoolismo

106. Pingback: stock analysis

107. Pingback: Indirect

108. Pingback: penis pump review

109. Pingback: Ben Wah Balls

110. Pingback: Masturbator

111. Pingback: cum cream

112. Pingback: G-spot Vibrator

113. Pingback: dildo review

114. Pingback: Amy Scott

115. Pingback: luxury sex toys

116. Pingback: Mini vibrator

117. Pingback: best wand vibrator

118. Pingback: Service

119. Pingback: free app for laptop

122. Pingback: beginner anal plug

123. Pingback: sexy

124. Pingback: sex toys

125. Pingback: sex toys

126. Pingback: Macho Stallion Erection Keeper

127. Pingback: gay

128. Pingback: pipedream extreme

129. Pingback: penis pump reviews

130. Pingback: Penis Ring

131. Pingback: Penis Pump Video

132. Pingback: RavingsbyRae

133. Pingback: g spot and clitoral vibrator

134. Pingback: jbeatz

135. Pingback: vibrator for women

137. Pingback: wand attachments

138. Pingback: magic touch vibrator

139. Pingback: gay anal sex toys

140. Pingback: couples toys

141. Pingback: whopper sex toys

142. Pingback: نصب دوربین مداربسته

143. Pingback: ABS Module Intercooler

144. Pingback: adam & eve delay spray

146. Pingback: Sripatum

147. Pingback: Bond back cleaning in Melbourne

150. Pingback: good head kit for him

151. Pingback: Best Lube

152. Pingback: Super Head Honcho Masturbator

153. Pingback: Bondage Restraint

154. Pingback: Realistic Dildo

155. Pingback: Make Me Cum Clit Sensitizer

156. Pingback: Hand Held Massager

157. Pingback: Best Vibrator

158. Pingback: Butterfly Kiss Toy

159. Pingback: Wand Massager

160. Pingback: silicone g

161. Pingback: g vibrator

162. Pingback: vibrating realistic dildo

163. Pingback: interior design Singapore

165. Pingback: bandiera Italia

166. Pingback: Cheap bond cleaning Melbourne

167. Pingback: adam and eve sex toy shop

168. Pingback: pink vibrator

169. Pingback: sex toys for beginner

170. Pingback: Tarts

171. Pingback: ravingsbyrae

173. Pingback: inflatable butt pug

174. Pingback: butt plug

175. Pingback: gay toys

176. Pingback: gay sex toys

177. Pingback: ants control extermination services

178. Pingback: end of lease clean Melbourne

179. Pingback: Easy recipes for vegetarians

180. Pingback: adam and eve sex toys shop

181. Pingback: how to use penis pump