26161번 - 트리의 팔
FFT 과정에서 실수 오차로 인하여 잘못된 답을 출력하는 코드를 저격합니다(제출 번호 52366162 52367171 52385942).
데이터의 크기가 커서 첨부 파일로 올립니다: boj26161.zip
첨부한 데이터를 간략하게 설명하자면 다음과 같습니다.
정점의 개수가 300000개이고 모든 노드가 루트 노드와 연결되어 있는 트리가 주어질 때
쿼리 W = V = 2에 대한 정답은 299999 * 299999 % 1000000007 = 999399378 입니다.
재청합니다.
지금 데이터로는 중국인의 나머지 정리 없이 적당히 큰 소수 하나로 NTT한 값으로 답을 구해도 정답 통과합니다.즉, convolution의 결과가 되는 수열의 값들이 32비트 정수형 표현 범위 안인 것 같습니다.
위 데이터로 제출번호 52452580도 저격 가능합니다.
댓글을 작성하려면 로그인해야 합니다.
hijkl2e 3년 전 4
FFT 과정에서 실수 오차로 인하여 잘못된 답을 출력하는 코드를 저격합니다(제출 번호 52366162 52367171 52385942).
데이터의 크기가 커서 첨부 파일로 올립니다: boj26161.zip
첨부한 데이터를 간략하게 설명하자면 다음과 같습니다.
정점의 개수가 300000개이고 모든 노드가 루트 노드와 연결되어 있는 트리가 주어질 때
쿼리 W = V = 2에 대한 정답은 299999 * 299999 % 1000000007 = 999399378 입니다.