N. 각 차원을 따로 생각해서 두 구간이 겹치지 않는 경우 바로 -1, 끝점만 겹치면 차원이 하나 줄어듬, 그 이외는 유지
O. 가장 간단한 네제곱 DP를 생각해보신 다음에, Maximum Subarray문제를 푸는 방식과 유사한 방식으로 시간복잡도를 줄일 수 있습니다.
P. (P_n)^k=P_{nk}이므로 식을 잘 하시면 A,B가 구해집니다. 그런데 문제는 식에 F_{nk}/F_{k}가 들어있다는 것입니다. 피보나치 수열의 성질에 의해 이 수는 언제나 정수이므로, 답은 언제나 존재합니다. 그래서 1,000,000,007로 나눈 나머지로 모듈러 연산의 역원을 구하면 되는데, 이때 F_{k}를 나눈 나머지가 0이 될 수 있으므로 1,000,000,007^2으로 나눈 나머지를 가지고 있으시면 됩니다.
kriii
9/28
대회가 끝났습니다!
최종 순위
참가해주신 여러분들께 모두 감사드립니다!
그냥 간단하게 풀이를 적어봤습니다.
N. 각 차원을 따로 생각해서 두 구간이 겹치지 않는 경우 바로 -1, 끝점만 겹치면 차원이 하나 줄어듬, 그 이외는 유지
O. 가장 간단한 네제곱 DP를 생각해보신 다음에, Maximum Subarray문제를 푸는 방식과 유사한 방식으로 시간복잡도를 줄일 수 있습니다.
P. (P_n)^k=P_{nk}이므로 식을 잘 하시면 A,B가 구해집니다. 그런데 문제는 식에 F_{nk}/F_{k}가 들어있다는 것입니다. 피보나치 수열의 성질에 의해 이 수는 언제나 정수이므로, 답은 언제나 존재합니다. 그래서 1,000,000,007로 나눈 나머지로 모듈러 연산의 역원을 구하면 되는데, 이때 F_{k}를 나눈 나머지가 0이 될 수 있으므로 1,000,000,007^2으로 나눈 나머지를 가지고 있으시면 됩니다.
Q. 사원수 a+bi+cj+dk의 곱셈의 역원은 \frac{a-bi-cj-dk}{a^2+b^2+c^2+d^2}입니다.
R. 이 문제의 오마쥬이고 이 문제 정도를 참고하셔서 풀면 됩니다.
S. 판 크기 가로 세로가 둘다 짝수이면서 음수 갯수가 홀수개가 아닌 이상 모두 양수로 만들 수 있습니다. 아니면 한개만 음수로 남길 수 있습니다. 판을 조작하는 것은 어떻게든 해보세요!
T. 고민해보세요
U. 어떤 순서로 하든 결과는 같습니다.
V. 잘 입력 받아서 문제에서 하라는 대로 하시면 됩니다. 입력 받는 것이 어려울 수도 있습니다(..).
W. N이 홀수이면 (N-1)/2, 짝수이면 N-1
X. D[i] = 최대공약수가 i의 배수인 개수, X[i] = 최대공약수가 i인 개수라고 하면 X[i] = D[i] - X[i*2] - X[i*3] - ...입니다. 이제 초기 D를 잘 계산하시면 됩니다. 이부분이 문제에서 가장 어려운 부분입니다.
Y. 간선이 모두 x<y이므로 i를 증가시켜 가면서 값을 갱신하시면 자동적으로 답이 구해집니다.
Z. 이 문자는 알파벳을 다르게 쓴 것인데 게임 fez에서 나오는 문자입니다. 다음 링크를 참조하세요 : A B C
9/22
대회 날짜는 2014년 9월 28일(일) 13:00 - 18:00 (KST)이며
전날 연습 세션이 2014년 9월 27일(토) 19:00 - 22:00 (KST)에 있을 예정입니다.
연습 세션은 별다른 신청이 없어도 가능하지만, 본 대회는 대회 전까지 신청을 하지 않으면 참가가 불가능한 점을 유의해주세요.
9/15
여러분을 위한 꿈과 희망이 가득한 대회! 올해도 매우 쉬운 문제들로 무장한 제2회 kriiICPC가 올해도 여러분을 찾아왔습니다!
올해도 geniusainta.com에서 대회를 열기 때문에 따로 가입을 해주셔야 합니다.
자세한 사항은 이곳으로
혹은 이곳으로
많은 관심 부탁드립니다.
9년 전