문제는 남자 n명 , 여자 m명 (n>=m) 일 때 nCm % mod를 구하는 문제다 nCm = n! / m!(n-m)! 인데 여기서 바로 %mod를 해버리면 답이 안나온다 우리는 페르마의 소정리를 사용해서 문제를 풀어야 한다! 페르마의 소정리 ==> p가 소수이고 a와 p가 서로소 일 때 a^p=a(mod p) 가 성립한다 a*a'=1(mod p) 일때 a'가 역원이라고 하자이 때 페르마의 소정리에 의해 a^(p-1) = 1(mod p) 가 성립한다그럼 a*a^(p-2) =1(mod p)가 되므로 역은 a^(p-2)다!! 그럼 a/b = a/b*b*b' = a*b' = a*b^(p-2) 가된다~!b^(p-2)는 log시간만에 구하면 시간초과에서 피할 수 있다! 소스코드1234567891011121314..
전에 weeklyps 에서 트리의 지름을 공부할 배운 방법을 이용했다!자세한 설명은 weeklyps에 있는 트리의 지름을 보는게 빠를듯.. ㅎㅎㅎ 정점 x를 기준으로 x의 서브트리에 속하는 최장거리, 안속하는 최장거리를 구해서 비교해주면 far 배열을 채울 수 있다..! 서브트리 속하는건 쉬워서 바로 구할 수 있다 트리의 깊이를 구하듯이 구하면 된다 속하지 않는 경우에는 다시 또 경우를 나눠서 구하면 된다...!자세한 설명은 weeklyps 꼭 가보시길..! 저도 3번읽음 ㅎㅎ다들 열공~~! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #includ..
나무를 심는 비용을 다~~ 구해서 곱하는 문제다비용은 지금 심는 나무와 현재 심어져있는 모든 나무까지의 거리의 합이다 이 문제는 펜윅트리를 2개 만들어서 풀 수 있다 하나는 나무가 (0~200000) 중 몇번째 좌표에 몇개가 있는지 아는 용도고두번째는 (나무의 거리 X 수) 를 담아두는 트리다 어떤 좌표 X에 나무를 심는다고 가정하면 우리는 비용을 2가지 작업으로 구할 수 있다. 1) X보다 큰 좌표에 나무가 심어져 있을 때 = (심어진 나무의 거리 합) - (현재 좌표)X(심어진 나무의 수) 2) X보다 작은 좌표에 나무가 심어져 있을 때 = (현재 좌표)X(심어진 나무의 수) - (심어진 나무의 거리 합) 이렇게 하면 비용을 구할 수 있다!트리로 만들어 두면 시간안에 충분히 할 수 있다!근데 문제를 ..
중앙값은 말 그대로 중앙에 있는 값이다K개 중에서 (K+1)/2번째 에 있는 값을 구하면 된다 이 문제는 세그먼트트리로 풀 수 있다.온도가 0~65536 까지니까 넉넉하게 66666까지 잡고온도가 측정될 때 마다 tree에서 온도를 +1 해준다그리고 K개 이상이면 i-k번째를 -1 하고 중앙값을 찾는다! - 세그먼트트리에서 K번째를 찾기 위해서는 나의 왼쪽 자식인 tree[node*2]와 값을 비교해보면 된다만약 K가 같거나 작다면 왼쪽에 있는 것이니까 왼쪽으로가고아니라면 오른쪽으로 가는데 K에서 왼쪽만큼을 빼고 가야한다!그래야 전체적으로 볼때 K번째를 찾을 수 있다. 소스코드123456789101112131415161718192021222324252627282930313233343536373839404..