PROBLEM LINK:Author: Zhuolin Yang DIFFICULTY:HARD PREREQUISITES:Fast Fourier Transform, Divide and Conquer, Lucas Theorem PROBLEM:Let $f(n,k)$ be the sum of products of all size$k$ subsets of $[n]=\{1,2,\dots,n\}$. Formally $$f(n,k)=\sum_{S\subseteq[n],S=k}\prod_{x\in S}x.$$ Given $n\le 10^{501}$ and prime $p\le 10^5$, how many ways are there to select a $k$ from $0$ to $n$ such that $f(n,k)$ is not divisible by $p$? QUICK EXPLANATION:
EXPLANATION:subtask 1In this subtask, $n\le 5000$. Let $f[i][j]$ be the product of size$j$ subsets of $\{1,2,\dots,i\}$. Then we can obtain the following dp equation: $$f[i][j]=f[i1][j]+i\cdot f[i1][j1].$$ This is because, if we choose $i$ into our subset, the product should be $i\cdot f[i1][j1]$; otherwise it should be $f[i1][j]$. We can compute $f[\cdot][\cdot]$ in $O(n^2)$ time and then compute the answer. subtask 2In this subtask, $n\le 200000$. We need an observation: $f(n,k)$ is the coefficient of $x^{nk}$ in the polynomial $$\prod_{i=1}^n(x+i)=(x+1)(x+2)\dots(x+n).$$ Why is that? Suppose we want to compute the coefficient of $x^{nk}$ of above polynomial. Think about how you multiply polynomials, and you'll realize that it's just the sum of products over all choices of $k$ subsets of $\{1,2,\dots,n\}$, which is the definition of $f(n,k)$. Now the task becomes to compute the product of $n$ polynomials of the form $(x+i)$. This can be done by divide and conquer, along with FFT. Let $A(x)$ be the product of the first half of $(x+i)$'s, and $B(x)$ be the product of rest $(x+i)$'s. We compute $A(x)$ and $B(x)$ recursively, and then compute $A(x)\cdot B(x)$ by FFT. The time complexity is $T(n)=2T(n/2)+O(n\log n)$, so $T(n)=O(n\log^2 n)$. This idea is illustrated by the following pseudocode, where $MUL(S)$ computes $\prod_{s\in S}(x+s)$.
After that, we just count the number of coefficients which can't be divided by $p$. subtask 3Following what we did before, let $P(x)=(x+1)(x+2)\dots (x+n)=a_0+a_1x+a_2x^2+\dots+a_nx^n$, we know that the answer is the number of $a_i$'s which can't be divided by $p$. Let $c=\lfloor n/p\rfloor$ and $b=n\bmod p$. Under modulo $p$, we have: $$P(x)=[(x+1)(x+2)\dots (x+p)]^c(x+1)(x+2)\dots (x+b).$$ You can observe that(see the second last paragraph of Finite field) $$(x+1)(x+2)\dots (x+p)\equiv (x^px)\pmod p,$$ Therefore $$P(x)=(x^px)^c\cdot (x+1)(x+2)\dots(x+b).$$ Since we only want to count the number of nonzero coefficients(after modulo $p$), it's no difference if we replace $(x^px)$ by $(x^{p1}1)$. We let $f(x)=(x^{p1}1)^c$, and $g(x)=(x+1)(x+2)\dots(x+b)$. For convenience, if $b=p1$ we let $f(x)=(x^{p1}1)^{c+1}$ and $g(x)=1$. Let $\Delta(f)$ be the number of nonzero coefficients of $f$, then $\Delta(f\cdot g)=\Delta(f)\Delta(g)$, since $g$ has degree $< p1$ and $f$ has nonzero coefficients only on $x^{i(p1)}$ terms. Solving $\Delta(f)$Let's suppose $f(x)=(x^{p1}1)^k$ for some integer $k$. Then $$f(x)=\sum_{i=0}^kx^{i(p1)}(1)^{ki}\binom{k}{i}.$$ We write $k,i$ in base $p$, say $k=k_1k_2\dots k_l$ and $i=i_1i_2\dots i_l$. By Lucas's Theorem, $\binom{k}{i}\not\equiv 0\pmod p$ if and only if $\forall 1\le j\le l$, $i_j\le k_j$. Therefore $\Delta(f)=(k_1+1)(k_2+1)\dots(k_l+1)$ since the $j$th bit of $i$ has $(k_j+1)$ options. Solving $\Delta(g)$$\Delta(g)$ can be computed by the divideandconquer with FFT in subtask 2. Time complexityWe need $O(len^2)$ time to convert $n$ into base $p$, where $len=O(\log n)$ is the length of $n$. We need a divideandconquer and FFT, whose time complexity is $O(p\log^2 p)$. Thus the total time complexity is $O(len^2+p\log^2 p)$. ALTERNATIVE SOLUTION:Please feel free to share your approaches :) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 27 Jan, 14:03

To illustrate what is talked about in gorre_morre's post here is two images showing an image plot of Here And here We're interested in the number of black pixels in some row. So just by finding the answer for the base triangle we can use the structure of the Sierpinski fractal to compute the answer for an arbitrary row. Specifically this involves interpreting the row index as a number in base answered 13 Feb, 22:38
@algmyr about time complexity of this if N was equal P/2 now what is time complexity of this?!
(13 Feb, 23:09)
@userhacker The case $n=p/2$ is not actually the worst case, it's more like $n=p/\sqrt{2}$ (so about 70000 for the largest allowed prime). And as for time complexity: Finding the correct row is quadratic in $n\,\textrm{mod}\,p$. Finding the number of triangles for a given row is more or less $O(\log(n))$, at least small enough to be insignificant. If you are clever about searching from the top or bottom depending on what row you want, you ended up passing the test cases, although you can easily devise cases that kills such a solution, like $n=p/\sqrt{n}$.
(13 Feb, 23:24)
@gorre_morre said time complexity so according that i choose N=49999 and p=99991 then we have O(min(49999,49992)^2)=O(49992^2)=O(2499200064) and we have 4 test case?
(13 Feb, 23:36)
i think you getting close to main solution. in main solution we find a general pattern for every N according to p,p^2,p^4,p^8,p^16 ,.... <10^501. just this have one exception for that we need calculate F(value of exeption,p) with FFT. this is fastest way. your way is near it. link text
(13 Feb, 23:58)
That time complexity is correct asymptotically, but the actual number of operations is a bit different since we work on a triangle. The point where working from above is more expensive is a bit lower down than half the triangle, essentially the horizontal line that cuts the triangle in two pieces with the same area. This way is nowhere near the one expected one complexity wise. It's just pure luck that this approach ends up working with the test cases, $n\,\textrm{mod}\,p$ never ended up close to the worst case for this algo.
(14 Feb, 00:32)
check this test case for TLE: 4 49999 99991 , 49999 99971 , 49999 99989 , 51999 99991 goodby man.good luck.
(14 Feb, 01:08)
On my laptop just the first case takes like 6 seconds (pypy) which wouldn't by itself be a TLE, since pypy for some reason has the same time multiplier as python, 5x. I think your test could potentially actually work if run on the server. However 50k is not the worst case, as stated. From what I measured on single cases, in (p,time) pairs: (50000,6.3), (60000,9.1), (70000,36.7), (80000,14.3), (90000,7.6)
(14 Feb, 01:51)
showing 5 of 7
show all

Nice problem! One nitpick in the description: it's not always true that deg(g)<p−1, as n can be 1 mod p. This case can be handled by adding 1 to n, as this just introduces an extra factor of x (mod p) to the polynomial product, which doesn't affect the number of nonzero coefficients. (I think your solution actually does this.) You can reduce the time taken to work out Δ(g) to O(p.log(p)) operations if you want to, by using a single FFT of order p1 in the multiplicative group mod p. That's because this FFT converts the coefficients of a polynomial (of degree less than p1) to the set of values it takes. So the inverse FFT, also an FFT, reconstructs the coefficients of g from the set of values the polynomial takes: g(1), ..., g(p1). These values can be worked out in O(p) time because g(r)=(r+b)/r*g(r1). The required FFT isn't a powerof2 size, but it can converted to three powerof2 FFTs using a variant of Bluestein's algorithm that doesn't need (2N)^th roots of unity. This is how one of my solutions worked. It made things maybe two or three times faster compared with a divideandconquer approach. (The gain wasn't huge because the overheads are such that p around 100,000 still counts as 'small'!) It takes 0.26 seconds using Python+numpy. answered 13 Feb, 01:27

@userhacker no 1 sec is also too long .. it should be 0.000....inf..1 nano seconds answered 14 Feb, 00:01

Using OEIS, I noticed the given example was a sequence produced by Stirling Numbers of the First Kind. I then looked for formulas for Stirling numbers. I used FFT for numbers less than 100K. answered 14 Feb, 08:13

time limit for this problem must be 1 or 2 sec(hard problem). because i see some approach that not considered for this problem. answered 13 Feb, 03:04
