[急]有趣的数问题 能否用正则表达式解决？

Question

正则表达式java

Answer 1

正则表达式是做模式匹配的，不是用来实现楼主的算法的。
模式匹配就是从一个字符串里找到指定规则的字符串。楼主的算法，是要求出n位数字中所有的有趣数。除非楼主想要用笨办法，逐个迭代出所有的情况，然后用正则进行模式匹配。
老实说，正则用在这个场景，效率是最低的，而且低得令人发指。如果排列组合学得好的话，应该能从数学的角度列出 通项公式，然后，直接用BigDecimal求出结果，不是更干脆一些？

Answer 2

推导出递推公式：
Fn+1=2Fn+(n-2)*(2^(n-1)-1)

Answer 3

怎么推出来的？我的思路：
一共n位，假设有a位是0,1，b位是2,3，
这样a+b=n，2<=a<=n-2
然后第一位不能是0，所以也不能是1，这样n位里取a位有c(n-1,a)种
然后这a位是：
0111....1
0011....1
...
00.......01
一共a-1种
相应的剩下b位就有b-1种
所以就是
sum=0
for i=2, i<=n-2, i++
  sum+=c(n-1, i)*(i-1)*(n-i-1)
print sum
然后c(n,k)的计算方法要用dp，直接算的话不好取余。
c[n][k]=c[n-1][k]+c[n-1][k-1]
预处理所有的c[1000][1000]，
然后c(n,k)就可以直接读了，复杂度100w+n*testcase。