[일반] 이거 어떻게 구할까

[익명(223.39)]

1e18보다 큰 N이랑 X가 주어지고

[0,X] 범위에서 4개의 정수 a,b,c,d를 고를때 a<b<c<d이고 a+b+c+d=N인 a,b,c,d 순서쌍의 개수

[Bubbler(bubbler)]

[0,X] 제한이 없으면 그냥 4개로 나누는 방법이랑 2개 같은거, 3개 같은거 등등 구해서 포함배제 뿌슝빠슝 하면 되는데 제한있으면 어케구하지 - dc App

[대학원오지마세요(publfl)]

Bostan-Mori

[익명(223.39)]

점화식 k번째항 계수 구하는걸로 알고있는데 어떻게 접근하는지 조금만 알려주실수 있으신가요..

[대학원오지마세요(publfl)]

a+b+c+d = a + a + (b-a) + a + (b-a) + (c-b) + a + (b-a) + (c-b) + (d-c)꼴로 표현 가능하며, 따라서 a, b-a, c-b, d-c를 다시 a,b,c,d라고 정의하면 a>=0, b,c,d>=1, 4a+3b+2c+d = N이라는 꼴이 나와요. 다시 b,c,d를 b+1,c+1,d+1꼴로 정리하면 a,b,c,d>=0, 4a+3b+2c+d = N-6꼴이 되며, 원래 모든 수가 X이하여야 된다는 조건은 a+b+c+d<=X-3이라는 조건이 됩니다. 이제 a+b+c+d = h라고 고정시켜봅시다. 처음에 a=b=c=0, d=h로 둔 후에 d의 숫자를 c,b,a로 하나씩 옮겨가서 전체 덧셈값을 1씩 늘려간다고 생각해봅시다.

[대학원오지마세요(publfl)]

그러면 h개의 수 각각에 +0,+1,+2,+3을 줘서 N-6-h를 만드는 방법을 묻는것이 됩니다. 이 경우의 수는 (1+x+x^2+x^3)^h의 N-6-h번째 계수를 묻는 것과 같으며, 다시말해 ( (1-x^4)/(1-x) ) ^ h의 N-6-h번째 계수를 묻는 문제가 됩니다. 이것을 Bostan-Mori로 계산할 수 있고, 이것을 h를 0에서 X-3까지 늘려가면서 전부 계산한 뒤 더해주면 될것 같네요. 이대로면 당연히 TLE가 나고, 식정리를 더 하면 h를 0에서 X-3까지 바꿔가며 다 더한 값을 정리할 수 있을것 같은데, 거기까지는 생각 안해봤네요

[대학원오지마세요(publfl)]

흠 맞는지 모르지만 대충 끄적여볼게요. ( ( 1-x^4)/(1-x) ) ^h의 N-6-h번째 계수 = x^h ( ( 1-x^4) / (1-x) )^h의 N-6번째 계수 = ( ( x - x^5) / (1-x) ) ^h의 N-6번째 계수. 이것을 모든 h=0...,X-3에 대해서 전부 해주고 더해준다면 결과는 ( ( x-x^5) / (1-x) ) ^ 0 + ( ( x-x^5) / (1-x) ) ^ 1 + ... + ( ( x-x^5) / (1-x) ) ^ X-3 의 N-6번째 계수 = (1 - t^X-2) / (1-t)의 N-6번째 계수(t = (1-x^4)/(1-x)). 음 식정리 잘 하면 Bostan-Mori 한방에 구할 수 있겠네요

[대학원오지마세요(publfl)]

아 오타가 있네요. t = (x - x^5)/(1-x)

[익명(223.39)]

장문의 답변 감사합니다!!

[익명(125.131)]

초항 몇개 구하고 벌캠박으면 안되나

[익명(223.38)]

중복조합이랑 포함배제 잘 써서 하면 될듯

[익명(223.38)]

근데 10^18?? 모듈러 없다고 하면 팩토리얼 어케 구하노

[익명(182.231)]

큰 수의 팩토리얼은 대충 sqrt(x)logx 시간에 되는걸로 아는데 숫자 범위가 너무 커서 이건 안될듯

[익명(59.6)]

그냥 약분하면 안되나