一个排列组合问题

qiaoyisi

tm__xk

基本粒子 发表于 2015-5-22 19:37
第1题和我的解法差不多，只是我把结果打错了，三种情况之和确实是43075640

我猜也是..这么弄反俩数字的不出意外都是手误..

基本粒子

tm__xk 发表于 2015-5-21 09:23
反正都是简单的暴力活儿就能搞定的..

1L..

第1题和我的解法差不多，只是我把结果打错了，三种情况之和确实是43075640

双子流星

谁然数学刚交过排列组合问题，但这也太难了，看半天没看懂。

tm__xk

qiaoyisi 发表于 2015-5-21 16:16
这个解法非常厉害!不过太简略，估计我看也得看半天才能理解。

这么写本来就不是拿来看的..

这种问题就是暴力活而已..又不是有明显的可以归纳的结构..仅仅略带点对称性而已..计算过程也没简单什么..
(我的意思是..比方说长长的2xN用骨牌覆盖的方案数那样的fibonacci..递推的计算已经算是..呃..复杂度比穷举简单的..
而这种..就算是稍微利用下对称性..顶多也就优化个常数而已..)
总之就是我觉得真没啥好说的..所以就不多作解释了..
反正方法无非是穷举..别算错就行了..唯一有得选择的只是穷举的顺序罢了..我觉得不值得对这种问题的这种顺序选择作解释..

ps.你觉得"解法非常厉害"?为什么会这么觉得(除了故意只写式子不作解释让人不明觉厉外)?
我觉得吧..如果有意识的去稍微利用下对称性可以算得上"厉害"的话..那什么都不优化只是最笨的暴力的如果能算得下去算到最后算出正确结果的话也算得上是同样程度的"厉害"了....
ps2.9L对6L的那个计算过程..跟你在8L说的是完全一样的..吧..

qiaoyisi

tm__xk 发表于 2015-5-21 09:23
反正都是简单的暴力活儿就能搞定的..

1L..

这个解法非常厉害!不过太简略，估计我看也得看半天才能理解。

tm__xk

反正都是简单的暴力活儿就能搞定的..

1L..
5*(4*(4*4+4*3*3)^3+3*4*3*(4*4+4*3*3)*(3*4+4*3+3*3*3)^2+4*3*2*(3*4+4*3+3*3*3)^3)=43075640
刚好和5L反了两位呢..

6L..
A=4*3^2
B=4^2+3*3^2
C=4*3+3*3^2
D=2*4*3+2*3^2
5*4^3*(A^3+4*B^3)+3*5*4*(4*3^2)*(A*C^2+B*C^2+3*B*D^2)+5*4*3*3^3*(3*C^2*D+2*D^3)=1418274920

解释什么的就算了..个人认为这种东西没什么解释的必要..

qiaoyisi

我们首先不管区域N、O、P，并按区域K、L、M的不同情况进行分类：
1.K、L、M同色：
1.1  区域A与区域K、L、M同色，则区域B有4种颜色可取，区域E、G在此基础上，均有3种颜色可取。区域C、F、J和区域D、H、I染色同区域B、E、G，故此类有5×（4×3×3）^3种；
1.2  区域A与区域K、L、MA不同色，则区域A有4种颜色可取，区域B显然与区域A不同色，若区域B与区域K、L同色，则区域B、E、G共有4×4种；若区域B与区域K、L不同色，则区域B、E、G共有3×3×3种。区域C、F、J和区域D、H、I染色同区域B、E、G，故此类有5×4×（4×4+3×3×3）^3种；
故1类共有5×（4×3×3）^3+5×4×（4×4+3×3×3）^3=1823420（种）。
2.K、L、M其中两个同色（与哪两个同色有关，故此类最后应×3，先考虑K、L同色情况）：
2.1  区域A与区域K、L同色，则区域B有4种颜色可取，区域E、G在此基础上，均有3种颜色可取。区域C显然与区域A不同色，若区域C与区域M同色，则区域F有4种颜色可取，区域J有4种颜色可取；若区域C与区域M不同色，则区域F有3种颜色可取，区域J有3种颜色可取。区域D、H、I染色同区域C、F、J，故此类有5×4×（4×3×3）×（4×3+3×3×3）^2种；
2.2  区域A与区域K、L不同色，与区域M同色，若区域B与区域K、L同色，则区域E、G在此基础上，均有4种颜色可取；若区域B与区域K、L不同色，则区域B有3种颜色可取，区域E、G在此基础上，均有3种颜色可取。区域C显然与区域A不同色，若区域C与区域K同色，则区域F有4种颜色可取，区域J有3种颜色可取；若区域C与区域K不同色，则区域C有3种颜色可取，则区域F有3种颜色可取，区域J有3种颜色可取。区域D、H、I染色同区域C、F、J，故此类有5×4×（4×4+3×3×3）×（4×3+3×3×3）^2种；
2.3  区域A与区域K、L不同色，与区域M也不同色，则区域A有3种颜色可取，若区域B与区域K、L同色，则区域E、G在此基础上，均有4种颜色可取；若区域B与区域K、L不同色，则区域B有3种颜色可取，则区域E、G在此基础上，均有3种颜色可取；区域C显然与区域A不同色，若区域C与区域K同色，则区域F有4种颜色可取，区域J有3种颜色可取；若区域C与区域M同色，则区域J有4种颜色可取，区域F有3种颜色可取；若区域C与区域K、M不同色，则区域C有2种颜色可取，则区域F、J在此基础上，均有3种颜色可取。区域D、H、I染色同区域C、F、J，故此类有5×4×3×（4×4+3×3×3）×（4×3+4×3+2×3×3）^2种；
故2类共有[5×4×（4×3×3）×（4×3+3×3×3）^2+5×4×（4×4+3×3×3）×（4×3+3×3×3）^2+5×4×3×（4×4+3×3×3）×（4×3+4×3+2×3×3）^2]×3=20862900（种）。
3.K、L、M颜色互不相同：
3.1  区域A与区域K、L、M中的其中一个颜色相同，故最后应×3。不妨设区域A与区域K颜色相同，若区域B与区域L同色，则区域G有4种颜色可取，则区域E有3种颜色可取；若区域B与区域L不同色，则区域B有3种颜色可取，则区域G、E在此基础上，均有3种颜色可取；若区域C与区域M颜色相同，则区域J有4种颜色可取，则区域F有3种颜色可取；若区域C与区域M不同色，则区域C有3种颜色可取，则区域F、J在此基础上，均有3种颜色可取；区域D显然与区域A不同色，若区域D与区域L同色，则区域H有4种颜色可取，则区域I有3种颜色可取；若区域D与区域M同色，则区域I有4种颜色可取，则区域H有3种颜色可取；若区域D与区域L、M均不同色，则区域D有2种颜色可取，则区域H有3种颜色可取，则区域I有3种颜色可取。故此类有5×4×3×（4×3+3×3×3）^2×（4×3×2+2×3×3）×3种；
3.2   区域A与区域K、L、M颜色均不相同，则区域A有2种颜色可取。此时区域A、K、L，区域A、K、M，区域A、L、M颜色均各不相同，故只需考虑一组。区域B显然与区域A不同色，若区域B与区域K同色，则区域E有4种颜色可取，则区域G有3种颜色可取；若区域B与区域L同色，则区域G有4种颜色可取，则区域E有3种颜色可取；若区域B与区域K、L均不同色，则区域B有2种颜色可取，则区域E有3种颜色可取，则区域G有3种颜色可取。故此类有5×4×3×2×（4×3×2+2×3×3）^3种；
故3类共有5×4×3×（4×3+3×3×3）^2×（4×3×2+2×3×3）×3+5×4×3×2×（4×3×2+2×3×3）^3=20389320种。
接下来考虑区域N、O、P，1类条件下，区域N、O、P均有4种颜色可取；2类条件下，区域K、L、M同色一侧有4种颜色可取，异色一侧各有3种颜色可取；3类条件下，区域N、O、P各有3种颜色可取。故最终得到，共有4^3×1823420+4×3×3×20862900+3×3×3×20389320=1418274920种不同的染色方案。

基本粒子

qiaoyisi 发表于 2015-5-17 23:39
分析的对的，方法差不多。请看此问题的强化：

说说你的方法吧，有点难算。

qiaoyisi

分析的对的，方法差不多。请看此问题的强化：