首页 > ACM题库 > HDU-杭电 > HDU 4365-Palindrome graph-模拟-[解题报告]HOJ
2015
05-23

HDU 4365-Palindrome graph-模拟-[解题报告]HOJ

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

题意:求用k种颜料将n*n大的方格涂满的方法有多少种,这里已经有m个格子上过色了

涂满后的方格要满足:中心对称,翻转对称,旋转对称

 

思路:

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

*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

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


  1. Pingback: Travis Scott Type beat

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

  3. Pingback: http://scalercflight.org/members/holck53brun/activity/1003823/

  4. Pingback: sex toys for beginner

  5. Pingback: massage vibrator

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

  7. Pingback: Taekwondo middleweight uniform

  8. Pingback: pocket rocket

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

  10. Pingback: 18 inch dildo

  11. Pingback: on site supplies

  12. Pingback: Magnetic secondary glazing

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

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

  15. Pingback: sex gel

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

  17. Pingback: how to

  18. Pingback: realistic dong

  19. Pingback: best erotic games

  20. Pingback: best wand vibrator

  21. Pingback: buy kvass

  22. Pingback: Best Selling Vibrator

  23. Pingback: Century ironman

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

  25. Pingback: driving tips

  26. Pingback: bangal ka jadu

  27. Pingback: Mikemaid 7447

  28. Pingback: bangal ka jadu

  29. Pingback: Cock ring

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

  31. Pingback: Anal toys

  32. Pingback: triple stimulator

  33. Pingback: massage after sex

  34. Pingback: best glass dildo

  35. Pingback: Dildo

  36. Pingback: Butt plugs

  37. Pingback: quotations

  38. Pingback: gay anal sex toys

  39. Pingback: bunny rabbit vibrator

  40. Pingback: pleasure rabbit

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

  42. Pingback: Super middleweight Black karate uniforms

  43. Pingback: couples toys

  44. Pingback: how cholesterol levels predict your health

  45. Pingback: php online store

  46. Pingback: repossession

  47. Pingback: Easyforex

  48. Pingback: Microsoft software

  49. Pingback: Orlando

  50. Pingback: Trending Hip Hop

  51. Pingback: Download Free Young Thug Mixtapes

  52. Pingback: Non-standard bearings

  53. Pingback: ノロウイルス

  54. Pingback: airfreight

  55. Pingback: inspekce jerabu

  56. Pingback: Download Free MP3

  57. Pingback: pc games for windows 8

  58. Pingback: tigerclaw red 6 oz poly/cotton karate uniform

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

  60. Pingback: adam and eve sex toys

  61. Pingback: emergency room glendale

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

  63. Pingback: Lacigreen

  64. Pingback: anal sex toys for women

  65. Pingback: adult sex toy

  66. Pingback: Savvy vibrator

  67. Pingback: couple games

  68. Pingback: sex toys for women

  69. Pingback: پویا بین

  70. Pingback: realistic red vibrator

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

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

  73. Pingback: anal sex toys

  74. Pingback: adam and eve

  75. Pingback: adamandeve.com

  76. Pingback: kala jadu

  77. Pingback: خرید apple id

  78. Pingback: magnetic labels

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

  80. Pingback: worktop protection

  81. Pingback: site protection

  82. Pingback: polythene

  83. Pingback: magic massager

  84. Pingback: sasha grey

  85. Pingback: Sex Toys

  86. Pingback: ted

  87. Pingback: sex toys

  88. Pingback: adult

  89. Pingback: Sex Toys

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

  91. Pingback: PHP Programmer

  92. Pingback: giving her oral

  93. Pingback: all american whopper dildo

  94. Pingback: bullet vibrator review

  95. Pingback: Adamandeve.com

  96. Pingback: reddit stocks

  97. Pingback: samuraiTV

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

  99. Pingback: Bob Training bag

  100. Pingback: anal sex toys

  101. Pingback: adam and eve sex toy shop

  102. Pingback: کفسابی

  103. Pingback: lingerie

  104. Pingback: adam and eve

  105. Pingback: Tunderkert

  106. Pingback: tratamento de Alcoolismo

  107. Pingback: home page

  108. Pingback: head honcho toy

  109. Pingback: adam and eve

  110. Pingback: stock analysis

  111. Pingback: Indirect

  112. Pingback: penis pump review

  113. Pingback: Ben Wah Balls

  114. Pingback: Masturbator

  115. Pingback: cum cream

  116. Pingback: G-spot Vibrator

  117. Pingback: adam and eve sex toysmr. just right vibrator

  118. Pingback: dildo review

  119. Pingback: Amy Scott

  120. Pingback: luxury sex toys

  121. Pingback: Mini vibrator

  122. Pingback: best wand vibrator

  123. Pingback: pc games free download for windows 10

  124. Pingback: Service

  125. Pingback: free app for laptop

  126. Pingback: games for laptop download

  127. Pingback: free download for windows pc

  128. Pingback: beginner anal plug

  129. Pingback: sexy

  130. Pingback: sex toys

  131. Pingback: sex toys

  132. Pingback: Macho Stallion Erection Keeper

  133. Pingback: gay

  134. Pingback: pipedream extreme

  135. Pingback: vietnam womens patch sewing blouse manufacturer

  136. Pingback: penis pump reviews

  137. Pingback: Penis Ring

  138. Pingback: Penis Pump Video

  139. Pingback: RavingsbyRae

  140. Pingback: g spot and clitoral vibrator

  141. Pingback: jbeatz

  142. Pingback: vibrator for women

  143. Pingback: adult sex toy

  144. Pingback: wand attachments

  145. Pingback: magic touch vibrator

  146. Pingback: gay anal sex toys

  147. Pingback: couples toys

  148. Pingback: whopper sex toys

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

  150. Pingback: ABS Module Intercooler

  151. Pingback: adam & eve delay spray

  152. Pingback: app for pc download

  153. Pingback: Sripatum

  154. Pingback: Bond back cleaning in Melbourne

  155. Pingback: adam and eve

  156. Pingback: adam and eve

  157. Pingback: good head kit for him

  158. Pingback: Best Lube

  159. Pingback: Super Head Honcho Masturbator

  160. Pingback: Bondage Restraint

  161. Pingback: Realistic Dildo

  162. Pingback: Make Me Cum Clit Sensitizer

  163. Pingback: Hand Held Massager

  164. Pingback: Best Vibrator

  165. Pingback: Butterfly Kiss Toy

  166. Pingback: Wand Massager

  167. Pingback: silicone g

  168. Pingback: g vibrator

  169. Pingback: vibrating realistic dildo

  170. Pingback: interior design Singapore

  171. Pingback: kala jadu

  172. Pingback: bandiera Italia

  173. Pingback: Cheap bond cleaning Melbourne

  174. Pingback: adam and eve sex toy shop

  175. Pingback: pink vibrator

  176. Pingback: sex toys for beginner

  177. Pingback: Tarts

  178. Pingback: ravingsbyrae

  179. Pingback: Google

  180. Pingback: inflatable butt pug

  181. Pingback: butt plug

  182. Pingback: gay toys

  183. Pingback: gay sex toys

  184. Pingback: ants control extermination services

  185. Pingback: end of lease clean Melbourne

  186. Pingback: Easy recipes for vegetarians

  187. Pingback: adam and eve sex toys shop

  188. Pingback: how to use penis pump

  189. Pingback: Google