组合计数小技巧
一个关于组合计数的小技巧:这个问题是这样的,给定\(n\)个数\(a_1\sim a_n\),要求出这\(n\)个数中所有组合的乘积之和
例如\(n=3\)时,即为:
\(a_1+a_2+a_3+a_1a_2+a_2a_3+a_1a_3+a_1a_2a_3\)
这个问题的解决是这样的
设\(f(i)\)表示前\(i\)项的和,则有
\[f(i)=a_i+f(i-1)+a_if(i-1),f(1)=a_1 \]证明显然,拆开即得,从组合意义的角度来说,也即算上\(a_i\)单独一项,再算上之前的所有不含\(a_i\)的项,再将之前不含\(a_i\)的项乘上\(a_i\)
标签:技巧,组合,个数,1a,计数,2a From: https://www.cnblogs.com/oierpyt/p/16950413.html