/*
这题是个很好的找规律练习题。。这里说的找规律当然不是人工暴力的去算。。而是先写个DP去找。。
首先我们要明确3根塔和4根塔本质的不同：3根塔时。。由于最下面那个盘子是最大的。。所以可以对上面的盘子进行递推。。4根塔时。。不管怎样挪移。。
最小的盘子所在的那根柱子是无法使用的。。也就是说我们只能使用3根。。所以状态转移很明显了：
f[i]=min(f[j]*2+g)。。其中f[i]表示4根塔的最小移动步数。。g[i]表示3根塔的最小移动步数。。
但是O(n^2)级别显然无妨应付本题数据。。所以去打个n<=10的表吧。。就可以看出规律了。。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int Ca=10000;
int dp[50001];
int n;

int main()
{
    cin>>n;
    dp[1]=1;
    int d=2,r=2,t=2;
    for(int i=2;i<=n;i++)
    {
        dp[i]=(dp[i-1]+d)%Ca;
        if(r>1)
            r--;
        else
        {
            d=(d<<1)%Ca;
            t++;
            r=t;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}
     

我来做点贡献

详解：4根柱子的情况.

按照惯例，从一个盘子做起.

n=1: 1次.

n=2: 3次.

n=3: 借助第4根柱子，5次搞定，比3根柱子省了2次.

以后都需要充分利用第4根柱子以减少次数.

n=4: 把1,2,3摊开，把1搭到2上面腾出一个空柱子移4，然后把3搭上去，再用3次把1,2搭上去，共计9次.

n=5: 把1,2,3摊开，再把1,2收到3的上面，腾出了两个空柱子，把4,5用3步移好，再次腾出了两个空柱子，把1,2摊开，然后1,2,3一并收到4上面，共计13次.

n=6: 把1,2,3摊开，再把1,2收到3的上面，腾出了两个空柱子，相当于用3根柱子移动4,5,6（7步完成），再次腾出了两个空柱子，把1,2摊开，然后1,2,3一并收到4上面，共计17次.

n=7:

屏蔽5,6,7，用n=4的方法把1,2,3,4移到另一根柱子上(9次)

此时腾出了两个空柱子，相当于用3根柱子移动5,6,7 (7次)

屏蔽5,6,7，用n=4的方法把1,2,3,4移好(9次)

共计25次.

n=8:

屏蔽6,7,8，用n=5的方法把1,2,3,4,5移到另一根柱子上(13次)

此时腾出了两个空柱子，相当于用3根柱子移动6,7,8 (7次)

屏蔽6,7,8，用n=5的方法把1,2,3,4,5移好(13次)

共计33次.

n=9:

屏蔽6,7,8,9，用n=5的方法把1,2,3,4,5移到另一根柱子上(13次)

此时腾出了两个空柱子，相当于用3根柱子移动6,7,8,9 (15次)

屏蔽6,7,8,9，用n=5的方法把1,2,3,4,5移好(13次)

共计41次.

n=10:

屏蔽7,8,9,10，用n=6的方法把1,2,3,4,5,6移到另一根柱子上(17次)

此时腾出了两个空柱子，相当于用3根柱子移动7,8,9,10 (15次)

屏蔽7,8,9,10，用n=6的方法把1,2,3,4,5,6移好(17次)

共计49次.

关于n个盘子如何确定分界线的问题：

首先1到(n-1)个盘子的问题需要全部解决，把所需步数记录下来，记为

f(1),f(2),……,f(n-1).

若把n个盘子分成前k个和后(n-k)个，则所需步数是

N = f(k) + 2^(n-k) - 1 + f(k)

其中，k=1,2,3,……,(n-1)

取最小的N值作为f(n)的值，对应的k值作为n个盘子的最佳分界线.

利用上述方法，我们不难得到前面一些n值的最佳步数和最佳分界线，我们把结果记录到一张表上.

由于n=0不失一般性，一并收入表中.

其中步数 f(n) = f(k) + 2^(n-k)-1 + f(k).

盘子数n 最佳分界k和(n-k) 步数f(n)增量d

 00, 00+ 0+ 0= 0-

 10, 10+ 1+ 0= 11

 21, 11+ 1+ 1= 32

 31, 21+ 3+ 1= 52

 42, 23+ 3+ 3= 94

 53, 25+ 3+ 5=134

 63, 35+ 7+ 5=174

 74, 39+ 7+ 9=258

 85, 3 13+ 7+13=338

 96, 3 17+ 7+17=418

106, 4 17+15+17=498

117, 4 25+15+25=65 16

128, 4 33+15+33=81 16

139, 4 41+15+41=97 16

14 10, 4 49+15+49=11316

15 10, 5 49+31+49=12916

16 11, 5 65+31+65=16132

17 12, 5 81+31+81=19332

18 13, 5 97+31+97=22532

19 14, 5113+31+113=257 32

20 15, 5129+31+129=289 32

21 15, 6129+63+129=321 32

22 16, 6161+63+161=385 64

…………… ………

/
个人认为此题有个新解：根据英文wiki的资料，4-Hanoi tower满足递推公式：
T[n,4]=T[k,4]2+T[n-k,3],其中T[i,j]表示初始时有i个盘,j个塔时所用的最少步数
且k满足k=n-round(sqrt(2n+1))+1,round()表示四舍五入的函数
故从1开始递增，连续运用以上递推式即可得出答案
/
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define REP(x,y,z) for (long i=x;i<=y;i+=z)
using namespace std;
long N,a[50005],b[50005];
int main(){
scanf("%ld",&N); b[1]=2;
for (long i=2;i<=N;i++) b[i]=(b[i-1]*2)%10000;
for (long i=1;i<=N;i++){
long k=i-(long)round(sqrt(2*i+1))+1;
a[i]=(a[k]*2+b[i-k]-1)%10000;
}
printf("%ld\n",a[N]);
}

啊就三个点

找规律，首先可以写出DP：f[i]=min(2*(f[j]+h[i-1-j])+1)，这个含义就是先以4柱方式移走j个盘子（需要步数f[j]），这样以后剩下3根柱子，那么有h[i-1-j]步数移走剩下i-1-j，也就是普通的3柱方案数，只剩一个盘子，移走它，+1，然后再把之前移走的移回来，于是乘2.
但是这个DP是O(n^2)的，我们不能直接用。
我们可以用它来打表，
1 2 3 4 5 6 7 8 9 10
1 3 5 9 13 17 25 33 41 49
把相邻两数作差可以发现数列是
1 2 2 4 4 4 8 8 8 8 16 16 16 16 16 ......
值为2^i的数字出现(i+1)次
于是可以写出公式O(n)计算

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;


int n,m;
ll bin[50001];
ll ans;
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    bin[0]=1;
    FOR(i,n) bin[i]=bin[i-1]*2%10000;
    FOR(i,n) if (i*(i-1)<2*n&&2*n<=(i+1)*i) {
        m=i;
        break;
    }
    FOR(i,m-1) {
        ans+=i*bin[i-1]%10000;
        ans%=10000;
    }
    ans+=(n-m*(m-1)/2)*bin[m-1]%10000;
    ans%=10000;
    cout<<ans<<endl;
    return 0;
}

随便推一推就好了~
```c++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int Ca=10000;
int dp[50001];
int n;

int main()
{
cin>>n;
dp[1]=1;
int d=2,r=2,t=2;
for(int i=2;i<=n;i++)
{
dp[i]=(dp[i-1]+d)%Ca;
if(r>1)
r--;
else
{
d=(d<<1)%Ca;
t++;
r=t;
}
}
cout<<dp[n]<<endl;
return 0;
}

点击查看程序源码+详细题解

参考各位大牛后写出来的。。。。。。简直不是动归而是找规律！吐槽一下。。
然而我并不理解为什么k*2后也要mod10000
希望有人能为我解答！
#include <iostream>
using namespace std;
int n,m,i,a[50001],k=2;
int main()
{
cin>>n;
a[1]=1;
m=2;
i=2;
while(i<=n)
{
for(int j=1;j<=m;j++)
{
if(i<=n)
{
a[i]=(a[i-1]+k)%10000;
i++;
}

else
break;
}
if(i<=n)
{
m++;
k=(k*2)%10000;
}
else
break;
}
cout<<a[n];
return 0;
}

已经通过汉诺4塔的递归形式找到了汉诺4塔的封闭性式，这个已经很接近通项公式了
对于四柱汉诺塔，用f表示用四柱移动i个盘的最少步数，g表示用三柱移动i个盘,则有状态转移方程
f[1]=1
f[0]=0
g=2^i-1
f=min(2*f[j]+g[j-k])
通过对相邻两项求差可以得到
1个1,2个2,3个4,4个8......
因为Σi*2^(i-1) (1<=i<=n)= Σ(Σ2^(j-1),(i<=j<=n)),(1<=i<=n)
=Σ(Σ2^(j-1),(1<=j<=n)- Σ2^(k-1),(1<=k<=i-1))
=Σ((2^n-1)-(2^(i-1)-1)),(1<=i<=n)
=Σ（2^n-2^(i-1)）,1<=i<=n
=n*2^n-Σ2^i(0<=i<=n-1)
=n*2^n-(2^n-1)
=(n-1)*2^n+1 (1)
于是便可以找一个数m,使m*(m+1)<=n<(m+1)*(m+2)
则h(n)=(m-1)*2^m+1+(2n-m(m+1))*2^(m-1)
=(m+2n-m^2-2)*2^(m-1)+1
推导过程如上，如果有误请大家指正，谢谢

var f:array[0..50010]of longint;k,i,s,ss,n:longint;

begin

readln(n);f[1]:=1;f[2]:=3;f[3]:=5;k:=4;s:=0;ss:=3;

for i:=4 to n do

begin

f[i]:=(f[i-1]+k)mod 10000;inc(s);

if s=ss then begin k:=(k*2)mod 10000;inc(ss);s:=0;end;

end;

writeln(f[n]);

end.

program _1073;

var

  f:array[0..50000]of longint;

  g:array[0..50000]of longint;

  i,j,t,min,k:longint;

procedure main;

begin

  writeln('program _10732;');

  writeln('var');

  writeln('  n:longint;');

  write('  a:array[1..50000]of longint=(');

end;

procedure main2;

begin

  writeln('begin');

  writeln('  read(n);');

  writeln('  writeln(a[n])');

  writeln('end.');

end;

begin

  assign(output,'10732.pas');

  rewrite(output);

  t:=1;

  for i:=1 to 50000 do

    begin

      t:=t*2;

      g[i]:=(t-1) mod 10000;

      t:=t mod 10000;

    end;

  f[1]:=1;f[2]:=3;f[3]:=5;

  for i:=4 to 50000 do

    begin

      min:=maxlongint;

      for k:=2 to i-1 do

        if 2*f[k]+g

这题是个很好的找规律练习题。。这里说的找规律当然不是人工暴力的去算。。而是先写个DP去找。。

首先我们要明确3根塔和4根塔本质的不同：3根塔时。。由于最下面那个盘子是最大的。。所以可以对上面的盘子进行递推。。4根塔时。。不管怎样挪移。。最小的盘子所在的那根柱子是无法使用的。。也就是说我们只能使用3根。。所以状态转移很明显了：

f[i]=min(f[j]*2+g)。。其中f[i]表示4根塔的最小移动步数。。g[i]表示3根塔的最小移动步数。。

但是O(n^2)级别显然无妨应付本题数据。。所以去打个n

记得刘汝佳大神说这个楼下的递推策略是否为最优策略还没有得到论证.....

所以“至少” ≠ “最少”...

但是如果说“至少”的话，那这题又不严谨，如果一种局面可以用4步达到目标，那我说至少3步也可以...

某本神书（《组合数学》）上说这个问题还未解决。

为何我在vj上看到了这道题？？

我很水，神牛莫鄙。

这是dp?

哪 个 牛？？

能讲 一下 递推式 OR 通项 的 来源！！

编译失败...|错误号:-1

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

居然还AC了？！

为什么不能边算边取余呀？

俺用dp做的。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

绝对压缩：

includeint main(){long n,a=1,b=1,c=1,i,j,s=0;scanf("%d",&n);for (i=1;i

盘子n

柱子m

1 个 1

1 的个数+（m-3） 个 2

2 的个数+（m-3） 个 3

3 的个数+（m-3） 个 4

.................

ans=前n项的和