시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 512 MB | 879 | 323 | 289 | 40.533% |
wo_okje의 Codeforces 레이팅은 언제나 민트에 머물러 있다. 블루를 가기 위해 대회에 참가한 욱제는 A번 문제와 B번 문제를 합해 3분 만에 풀어내는 데 성공하고야 말았다! 신나게 C번 문제로 넘어간 욱제는 다음 문제를 마주치고 말았다.
당신에게 그래프가 주어진다. 이 그래프는 자연수 N(1 ≤ N ≤ 191,229)으로 표현되며, 다음과 같은 정점과 간선을 가진다.
서로 다른 두 간선이 끝점을 공유하지 않도록 정확히 N개의 간선을 고르는 방법의 수를 구하여라. 단, 수가 너무 커질 수 있으니 109+7로 나눈 나머지를 출력하여라.
라는 내용의 문제를 1시간째 고민했지만 문제를 풀지 못해 블루를 가지 못할 것 같다는 생각이 든 wo_okje는 당신에게 몰래 도움을 요청했다. wo_okje를 위해 이 문제를 풀어주자!
입력의 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 191,229)
이후 T개의 줄에 걸쳐 각각의 그래프를 나타내는 자연수 N이 주어진다. (1 ≤ N ≤ 191,229)
문제에 대한 답을 한 줄에 하나씩 총 T개의 줄에 걸쳐 출력하여라.
2 1 2
1 2
Contest > BOJ User Contest > Good Bye, BOJ > Good Bye, BOJ 2019! C번