### PNVZarif's blog

By PNVZarif, history, 10 days ago,

• +7

 » 10 days ago, # |   +1 Let $a_1, a_2, ..., a_C$ be the separations between consecutive partners. We need to solve for $\;a_1+a_2+...+a_c=N-C\;$ where $a_i\geq R\; \forall i$. This is the same as $\;a'_1+a'_2+...+a'_c=N-C-R*C\;$ where $a'_i\geq 0\; \forall i\quad$ (Substituting $a'_i=a_i-R$)Now, notice that we can arrange a particular tuple $(a_1,a_2,...a_C)$, exactly $N$ times around the table and each will be treated as a distinct way as long as this tuple is a unique circular permutation. (Eg. (1,1,3) and (1,3,1) or (2,3,4,5) and (3,4,5,2) are not).One special case being that if all $a_i$'s are equal (can only happen when $C|N$) then we cannot arrange $N$ times around the table but only $N/C$ times as after that we will get a repetition.Finally, in every scenario Pixie can be seated in $N-C$ independent ways, each counted as distinct. We can just multiply the final total with $N-C$ at the very last to incorporate that.Therefore an algorithm would be: Find the number of (unique circular permutation) tuples $(a_1,a_2,...a_C)$ where at least two $a_i$'s differ. Let this be $cnt_1$. Find the number of tuples $(a_1,a_2,...a_C)$ where all $a_i$'s are same. Let this be $cnt_2$. (it will either be $0$ or $1$) Output $ans=(cnt_1*N+cnt_2*\frac{N}{C})*(N-R)\%p$ Note that, ${m+C-1 \choose m}$ is the total number of tuples (where $m=N-C-R*C$). Out of these at most one is of type two (if C divides N) and remaining are exactly all tuples with at least two distinct values, but these are not circularly invarient yet. In fact we have exactly $C$ copies of each such tuple.Thus, $cnt_2=(N\%C==0)$ and $cnt_1=\frac{{n+C-1 \choose n}-cnt_2}{C}\;$. This makes the final answer simplier — $\;ans=\frac{{m+C-1 \choose m}*N*(N-R)}{C}\%p$Example:Test Case 1$a_1+a_2+a_3=9-3=6,\;\; a_1,a_2\geq2\;\;\;\qquad$ or $\qquad\;\;\;a'_1+a'_2+a'_3=0,\;\; a'_1,a'_2\geq0$$(a_1,a_2,a_3)=(2,2,2)$$cnt_1=0$. no such ways.$cnt_2=1$ comprises of $(2,2,2)$ case repeated $9/3=3$ times. $\therefore 1*3=3$ ways.Total $(0+3)*(N-C)=3*6=18$ ways.Test Case 2$a_1+a_2=10-2=8,\;\; a_1,a_2\geq1\;\;\;\qquad$ or $\qquad\;\;\;a'_1+a'_2=6,\;\; a'_1,a'_2\geq0$$(a_1,a_2)=(1,7),(2,6),(3,5),(4,4),(5,3),(6,2),(7,1)$$cnt_1=3$ comprises of $(1,7),(2,6),(3,5)$, each repeated $10$ times. $\therefore 3*10=30$ ways.$cnt_2=1$ comprises of $(4,4)$ case repeated $10/2=5$ times. $\therefore 1*5=5$ ways.Total $(30+5)*(N-C)=35*8=280$ ways.