完美间隔配对排列

mathe

明白了，应该两个序列，其中一个0可以放在边界上，一个不允许。

mathe

提交序列中，发现
A176127
表示了不带零情况的数目

mathe

根据OEIS中链接，可以找到一篇文章，模仿这篇文章利用多项式解决这个问题，可以有下面代码，不过发现效率上比我前面代码提升不多，好处对内存需求非常之低
1. 允许头尾是0的情况

1. #include <iostream>
   
2. 
   
3. typedef __int128_t dtype;
   
4. #ifndef N
   
5. #define N 2
   
6. #endif
   
7. #define R (2*N+1)
   
8. 
   
9. dtype evalf(long v)
   
10. {
    
11.    int i,k;
    
12.    dtype prod=2*__builtin_popcountl(v)-R;
    
13.    for(i=1;i<=N;i++){
    
14.      long t= (v^(v>>(i+1)))&((1L<<(R-(i+1)))-1);
    
15.      prod*=(R-(i+1))-2*__builtin_popcountl(t);
    
16.    }
    
17.    long numneg = R-__builtin_popcountl(v);
    
18.    if(numneg&1)prod=-prod;
    
19.    return prod;
    
20. }
    
21. 
    
22. int main()
    
23. {
    
24.   dtype v=0;
    
25.   long i;
    
26. #pragma omp parallel for reduction(+:v)
    
27.   for(i=0;i<(1L<<R);i++){
    
28.     dtype localv = evalf(i);
    
29.     v+=localv;
    
30.   }
    
31.   v>>=R;
    
32.   std::cout<<(long)(v+1)/2<<std::endl;
    
33.   return 0;
    
34. }
    

复制代码

2. 不允许头尾是0的情况

1. #include <iostream>
   
2. 
   
3. typedef __int128_t dtype;
   
4. #ifndef N
   
5. #define N 2
   
6. #endif
   
7. #define R (2*N+1)
   
8. 
   
9. dtype evalf(long v)
   
10. {
    
11.    int i,k;
    
12.    long v2=v&~((1L<<(R-1))|1L);
    
13.    dtype prod=2*__builtin_popcountl(v2)-(R-2);
    
14.    for(i=1;i<=N;i++){
    
15.      long t= (v^(v>>(i+1)))&((1L<<(R-(i+1)))-1);
    
16.      prod*=(R-(i+1))-2*__builtin_popcountl(t);
    
17.    }
    
18.    long numneg = R-__builtin_popcountl(v);
    
19.    if(numneg&1)prod=-prod;
    
20.    return prod;
    
21. }
    
22. 
    
23. int main()
    
24. {
    
25.   dtype v=0;
    
26.   long i;
    
27. #pragma omp parallel for reduction(+:v)
    
28.   for(i=0;i<(1L<<R);i++){
    
29.     dtype localv = evalf(i);
    
30.     v+=localv;
    
31.   }
    
32.   v>>=R;
    
33.   std::cout<<(long)(v+1)/2<<std::endl;
    
34.   return 0;
    
35. }
    

复制代码

缺乏的还是算力
原理是定义函数\[ F(n)=\left(\sum_{k=0}^{2n}x_k\right)\prod_{s=1}^n \sum_{k=0}^{2n-s-1}x_kx_{k+s+1}\\G(n)=\left(\sum_{k=1}^{2n-1}x_k\right)\prod_{s=1}^n \sum_{k=0}^{2n-s-1}x_kx_{k+s+1}\]
那么多项式中\(\D\prod_{k=0}^{2n}x_k\)的系数就代表了答案。也就是表达式中各乘积项分别代表0，1，2，..., n出现的位置。
由于多项式是齐次的，每项次数都是2n+1,所以除了上面这一项，其余项都会缺乏某个变量，于是函数\(\D F(n)\prod_{k=0}^{2n}x_k\)对$x_k$取遍-1和1的组合进行累加，那么所有其他项全部消除，而只留下\(\D \prod_{k=0}^{2n}x_k^2\)项，它被重复累加了$2^{2n+1}$次，结果除以这个常数即可

mathe

mathe 发表于 2025-3-6 10:15
很奇怪，我计算的部分结果和大家相同，但是有些不同
  1 1
  2 1

n=21时为443385597340544,这时两个序列相等

王守恩

一眨眼 9 年！藉众多网友接力, 这串数已经有20个数!  谢谢各位网友！

题目：将 0,1,1,2,2,…,n,n 排成一列，
要求两个 k 中间有 k 个数（k=1,2,…,n)，
譬如。
1有1种排法： ("101")
2有1种排法 :  ("12102")
3有1种排法：("1312032")
4有3种排法：("131423024" "141302432" "240231413")
5有11种排法,

我们约定：第1个数(不能是0)要比最后1个数小。

01  1,
02  1,
03  1,
04  3,
05  11,
06  38,   
07  130,   
08  638,    谢谢 aimisiyou！谢谢 adlpg070！
09  4158,    谢谢 aimisiyou！谢谢 adlpg070！
10  23384,   谢谢 aimisiyou！谢谢 adlpg070！
11  124520,   谢谢 aimisiyou！谢谢 adlpg070！
12  847484,   谢谢 aimisiyou！谢谢 adlpg070！
13  6987380,   谢谢网友时间的音符(Excel论坛)！
14  53746000,   谢谢网友yjh_27(Excel论坛)！
15  400346544,    谢谢网友uk702！
16  3529108816,    谢谢网友l4m2！
17  35963592624,    谢谢网友l4m2！
18  351432650816,    谢谢网友l4m2！
19  3346590201888,   谢谢网友l4m2！
20  36341624453568,   谢谢网友l4m2！
......
谢谢各位网友！

mathe

n=22结果为5245806847699840

northwolves

mathe版主算力太高

A381759

A381760

王守恩

一个好玩的游戏——原题是这样的。

1,1,2,2,3,3——2,3,1,2,1,3——满足2个1中间有1个数, 2个2中间有2个数, 2个3中间有3个数。

1,1,2,2,3,3,4,4——2,3,4,2,1,3,1,4——满足2个1中间有1个数, 2个2中间有2个数, 2个3中间有3个数, 2个4中间有4个数。

原题三十年前很流行, 几乎每个小朋友都在做。遗憾的是, 不是每对数都有答案。本人在此基础上加了1个0, 能使每对数都有答案, 可以连续做题目了。

同事们搓麻将,打扑克, 小朋友也是挺烦人的。我说我来出道题, 用0,1,1——0,1,1,2,2把题意解释清楚, 就让小朋友自己动手去折腾, 只要找到1个答案就可以！做对了再发2张牌, 骗小朋友蛮好的。

我的初衷是每对数找1个答案就可以！！尽可能往前走！！！享受每次找到答案的喜悦, 更鼓励自己去寻找下一个答案的冲动。也许来个小朋友第二天还在兴奋的告诉我：我把9做出来了！！

对于每个数都有解, 我好像不怀疑, 但不曾想某个数有多少解, 更不曾想有怎么多解！谢谢各位网友！

做题目最好的方法是动手, 希望看到道题的网友, 享受每次找到答案时的喜悦, 更在意信任自己一定能找到答案的信念, 因为探索比结果更诱人。