각각의 $n$에 대하여 대칭 축을 기준으로 왼쪽에 $k$쌍의 괄호가 존재하는 경우의 수를 $h(n,k)$로 정의하자. 그럼 다음이 성립한다. $$h(n,k)=h(n-1,k-1)+h(n-1,k)$$ \[h(n,k)=0\ \ k>=1){ if(k&1) s=s*n%mod; n=n*n%mod; } return s; } int main(){ ll i,n,ans=0,K,card=1,end; scanf("%lld %lld",&n,&K); end=n/2; if(n%2==0) end-=1; ans=K*fpow(K+1,2*end)%mod; for(i=1;i

'냠냠' 이라는 문제이다! 냠냠 $n\times m$ 격자에서 원점으로부터 각 점들로 직선을 긋는데 서로 다른 직선의 개수를 구하는 문제로 바꿔 볼 수 있다. 그럼 겹치는 직선이 뭔지만 알면 문제를 풀 수 있겠다. 기울기가 $b/a$이고 기약분수라고 한다면 $2b/2a,\ 3b/3a...$등 이 겹치는 직선이므로 1개만 세야한다. 이때 관찰할 수 있는 사실은 $b/a$가 기약분수가 아니면 반드시 겹치는 직선이 된다는 사실이다. 그럼 $b/a$가 기약분수가 되는 $a,b$쌍의 개수를 세면 된다. 이것은 다음과 같이 나타난다. $$\sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i,j)=1]$$ 이때 Mobius inversion을 적용하면 \[\sum_{d=1}^{\min(n,m)} \mu..

집합 $s$는 크기가 $n$이고 어떤 자연수 $m$의 약수를 모두 포함하고 있다. 그 집합의 원소들에 대해 다음 행렬을 만들었을 때 행렬식을 구하는 문제이다. $$D_{n}=\begin{vmatrix} \gcd(x_{1},x_{1}) & \gcd(x_{1},x_{2}) & ... & \gcd(x_{1},x_{n})\\ \gcd(x_{2},x_{1}) & \gcd(x_{2},x_{2}) & ... & \gcd(x_{2},x_{n})\\ ... & ... & ... & ...\\ \gcd(x_{n},x_{1}) & \gcd(x_{n},x_{2}) & ... & \gcd(x_{n},x_{n})\\ \end{vmatrix}$$ 행렬식을 계산할 때 가장 단순하게 생각할 수 있는 것은 대각 행렬의 꼴을 만든 뒤에 ..

일반 물리가 재미없어서 수업시간에 푼 문제;; 아~ 시험공부 하기 싫다~~ 문제 해법으로 바로 넘어가자. $g, h$가 주어졌을 때 $gk=h^{n}+\alpha$($\alphak: k*=h if p: k*=h a=(2*k)//a-1 a*=g if a==g: g=0 return (h*a+g,a) t=int(input()) for i in range(t): g,h=map(int,input().split()) ans1=f(g,h,0) ans2=f(g,h,1) no1=0 no2=0 if ans1[0]>10**18: no1+=1 if ans2[0]>10**18: no2+=1 if gcd(ans1[0],ans1[1])!=g or r(ans1[0],ans1[1])!=h: no1+=1 if gcd(ans2[0],an..

이 문제는 $x^{n}-1$을 소인수분해 하는 것이 목적이다. 문제 지문에 나와있다시피 $x^{n}-1$은 다음과 같이 소인수분해 된다. $$x^{n}-1=\prod_{d|n} \Phi_{d}$$ 양 변에 log를 취하자. $$\log(x^{n}-1)=\sum_{d|n} \log(\Phi_{d})$$ 뫼비우스 역공식을 이용하면 $$\log(\Phi_{n})=\sum_{d|n} \log(x^{d}-1) \mu(n/d)$$ $$\Phi_{n}=\prod_{d|n} (x^{d}-1)^{\mu(n/d)}$$ 위 식을 이용해 $x^{n}-1$을 구성하는 각각의 $\Phi$들을 구하면 답을 구할 수 있다. $\mu(n/d)$의 값이 1 또는 -1인 것만 계산하면 된다. 물론 $\mu$를 전처리 하는 것은 필수이다...

처음 참가해본 대회인데 3문제나 풀어서 기쁘다. 문제들을 보자마자 느낀 것은 정말 새롭고 신기하다는 것 ㅋㅋㅋㅋㅋ 1번 문제는 그냥 Text로 복사 붙여넣기 하면 끝난다. 2번은 애초에 아는 언어가 C++20 밖에 없어서 부분 점수만 받고 끝났다. 3, 4번은 무서워서 안했다 ㅋㅋㅋ 5번을 풀 때 txt파일에 있는 단어 중에서 5개의 글자가 서로 다른 것들을 추리고 제출하고, 채점 결과를 초대로 추리고 돌리고... 하면 쉽게 풀린다. 6번이 가장 힘들었던 문제... 4시 정도에 했는데 8분 정도 노가다를 했다. 😫😫 7번도 패스 8번은 직접 육군훈련소에 가서 찾아봤는데 비밀번호가 걸려서 읽을 수가 없었다. 그래서 그냥 막 찍다가 '하이'로 부분 점수를 얻었다. 9번은 9-1번 문제에서 포기했다. 아무리 ..