2012 Multi-University Training Contest 7: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?
Input
There are several test cases.
For each test case,there are three integer n m k(0
Output
For each case,print a integer in a line,indicate the number of ways jack can paint. The result can be very large, so print the result modulo 100 000 007.
Sample Input
3 0 2
4 2 3
1 1
3 1
Sample Output
8
3
Author
FZU
Source
2012 Multi-University Training Contest 7
//제목: n*n의 행렬을 정하고 안에 있는 격자 염색(k가지 색깔)을 임의의 수평 또는 수직으로 뒤집거나 회전하는 90(180270360)을 만족시켜야 한다. 얻은 도형은 모두 같다.즉 그림 중심의 대칭을 요구한다.현재 몇 개의 칸을 염색하면 그것의 대칭점(8가지 상태) 색깔을 모두 고정시킬 수 있다.현재 고정되지 않은 색의 점의 개수num만 구하면 방안수는 k^num입니다.
//색깔이 대칭적인 행렬은 사실 왼쪽의 1/4의 직사각형의 절반 (삼각형) 색깔이 고정되기만 하면 전체 그림은 이 작은 삼각형으로 회전하고 접을 수 있다.그리고 이 작은 삼각형 안의 모든 점은 서로 관련이 없다.그것이 최초의num값이다. 주어진 m개의 염색점에 대해 각 점의 대칭점(접기, 회전)을 스캔해 보면 모두 그 작은 삼각형에 떨어진다. 있다면num--.시간 복잡도 O(m);
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
using namespace std;
#define maxn 2005
#define LL __int64
#define M 100000007
struct node
{
int x,y;
}point[maxn];
int n,m,k;
map<int,bool>my;
bool OK(int x,int y,int tmp)
{
node aa[10];
aa[1].x=x,aa[1].y=y; // 、 8
aa[2].x=x,aa[2].y=tmp-y;
aa[3].x=tmp-x,aa[3].y=y;
aa[4].x=tmp-x,aa[4].y=tmp-y;
aa[5].x=y,aa[5].y=x;
aa[6].x=tmp-y,aa[6].y=x;
aa[7].x=y,aa[7].y=tmp-x;
aa[8].x=tmp-y,aa[8].y=tmp-x;
int i;
bool flag=false;
for(i=1;i<=8;i++)
if(aa[i].y>=aa[i].x&&aa[i].x<=tmp/2&&aa[i].y<=tmp/2) //
if(!my[aa[i].x*10000+aa[i].y]) // ， map
{
flag=true;
my[aa[i].x*10000+aa[i].y]=true;
}
return flag;
}
LL mod_mult(LL a,LL r)
{
LL d=1;
while(r)
{
if(r&1) d=d*a%M;
r>>=1;
a=a*a%M;
}
return d%M;
}
int main()
{
int i,j;
while(~scanf("%d%d%d",&n,&m,&k))
{
int tmp=n;
if(n&1) tmp++;
LL num=(tmp/2)*(tmp/2+1)/2; //
my.clear();
for(i=0;i<m;i++)
{
scanf("%d%d",&point[i].x,&point[i].y);
if(OK(point[i].x,point[i].y,tmp-1))
num--;
}
printf("%I64d
",mod_mult(k,num));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
