有趣的数论问题

qiaoyisi

tm__xk

13824.
字数.

bristlegrass

同楼上 13824

qiaoyisi

给一下具体过程，谢谢！

tm__xk

本来我是直接跑程序秒的.既然要过程..那就随便码个好了..
157随意,造成4个空当.
穷举2468在其中的分布.
I.13
"3"需3和9分隔,故6为"1".方案数为(12*6*2=)144.
II.112
同理6为"1",方案数为(12*12*2*5=)1440.
III.1111
方案数为(24*30=)720.
综上,总方案数为(6*(144+1440+720)=)13824.

tm__xk

我一定是太无聊了..竟然无聊到用容斥原理算这个问题..
为方便观看,用图来表示是否能相邻的关系..
用点表示数,用边表示不能相邻的关系..可以看到..其实就是2468构成K4,369构成K3(二者公用6)(当然还有157孤立).
我们来看看取其中若干条边后,使这些边两端相邻的方案数..
应该看到,取出的若干条边,如果存在圈,或者存在度数>=3的点,就很没有考虑的意义了..
还有,这里总共6个点,没有圈,于是至多取5条边.
下面记A[i]为取i条边时对应的方案数.
################以上是废话.以下是无聊.以下纯目测,所以嫌太简单的别找我要过程.(ls的过程也是目测,同样别找我解释.)
I.A[0]=9!
II.A[1]=8!*2*9
III.A[2]=7!*(2*21+2^2*15)
IV.A[3]=6!*(2*30+2^2*33+2^3*3)
V.A[4]=5!*(2*24+2^2*27)
VI.A[5]=4!*2*12
综上,总方案数为A[0]-A[1]+A[2]-A[3]+A[4]-A[5]=9!-8!*2*9+7!*(2*21+2^2*15)-6!*(2*30+2^2*33+2^3*3)+5!*(2*24+2^2*27)-4!*2*12=13824.

superacid

我是来吐槽楼主懒得打字的

bristlegrass

好吧...我也是跑程序的...
要思路的话就随便写一个吧

把数分成4组:
a.157
b.248
c.39
d.6

6在中间:
d和bc都不能相邻,所以先从a组抽2个数组成一个集合(e):3*2=6;
a组剩下一个数(f);
b组排列数:3*2=6;
把c组插入b组,分情况:
A.同在一端,无符合题意的排列:0;
B.各在一端,则ef只能插在248中间:2*2=4;
C.一个在一端一个在中间,则ef还有一个要插中间:2*2*2*(7-1)*2=96;
D.在同一空当,则ef有两个空当必插:2*2*2=8;
E.在不同空当:2*6*7=84;
综上:6*6*(0+4+96+8+84)=6912.

6在两端(2):
d和bc都不能相邻,所以先从a组抽1个数组成一个集合(g):3;
a组剩下两个数(h);
b组排列数:3*2=6;
把c组插入b组,分情况:
F.同在一端,无符合题意的排列:0;
G.各在一端,则h只能插在b中间:2*2=4;
H.一个在一端一个在中间,则h还有一个要插中间:2*2*2*(7-1)*2=96;
I.在同一空当,则h有两个空当必插:2*2*2=8;
J.在不同空当:2*6*7=84;
综上:2*3*6*(0+4+96+8+84)=6912.

总:6912+6912=13824.

也不知道对不对-.- 顺便说一下我的程序跑了72秒是不是很渣...
ps:改了一下算法,现在36秒...

tm__xk

bristlegrass 发表于 2013-12-31 09:15
好吧...我也是跑程序的...
要思路的话就随便写一个吧

呃..我的程序..大概跑了..半秒?→_→

tm__xk

话说..一般地讲..这就是求图的哈密顿路的数量吖..