Problem statement: You are given an integer $$$n$$$. There are n sticks of length $$$1, 2, 3, ..., n$$$. You find to find out how many incongruent triangles can be formed by using three of the given sticks. Output the result modulo $$$10^{12} + 9$$$.
Constraint: $$$4 < n < 10^{12}$$$, where $$$n$$$ is a positive integer.
My idea: I analyzed some base cases. After that, I transformed the problem into an equation with a nested loop. After resolving the nested loop, I determined the number of triangles, denoted as $$$x$$$, to be,
I can't optimize it for the ceiling function. It is working on $$$O(n)$$$. But the constraint of the problem is: $$$4 < n < 10^{12}$$$. Therefore, we can't iterate over n. However, Can it be simplified? (Can we express this equation without using the summation sign?)
Thanks in advance for your assistance.
Doing it with $$$O(1)$$$ !!! It seems impossible to me.
$$$i(i+1)/2$$$ is an integer, as one of either $$$i$$$ or $$$(i+1)$$$ must be even, so the ceiling function essentially disappears and you can use the usual formulas for $$$\sum i$$$ and $$$\sum i^2$$$.
For the remaining ones, notice that the pattern of $$$\lceil (i+1) / 2 \rceil$$$ is $$$1, 2, 2, 3, 3, 4, 4, \dots$$$. You can infer some formulas from here based on whether $$$n$$$ is odd or even.
Thank you very much! I have found the formula.