洛谷P1573 栈的操作 [2017年6月计划 数论11]

P1573 栈的操作

题目描述

现在有四个栈，其中前三个为空，第四个栈从栈顶到栈底分别为1,2,3,…,n。每一个栈只支持一种操作：弹出并 压入。它指的是把其中一个栈A的栈顶元素x弹出，并马上压入任意一个栈B中。但是这样的操作必须符合一定的规则才能进行。规则1：A栈不能为空。规则 2：B栈为空或x比B栈栈顶要小。

对于给定的n，请你求出把第四个栈的n个元素全部移到第一个栈的最少操作次数。

由于最少操作次数可能很多，请你把答案对1000007取模。

输入输出格式

输入格式：

一行，一个n

输出格式：

一行，一个正整数，为把最少操作次数 mod 1000007的值

输入输出样例

输入样例#1：

2

输出样例#1：

3

说明

对于30%的数据，n<=8

对于60%的数据，n<=60

对于100%的数据，n<=2*10^9

四根柱子的汉诺塔问题。

f3[i]表示三根汉诺塔柱子，有i个盘子的操作数

f4[i]表示四跟汉诺塔柱子，有i个盘子的操作数

可得：f4[i] = 2f4[j] + f3[i - j],1 <= i < j <= n

可以这样理解：先把j个盘子放到第三根柱子上，操作数f4[j],然后把剩余的i - j个盘子通过三根柱子放到第四根柱子上，方案数f3[i - j ]，

然后把j个盘子通过四根柱子放到第四个盘子上

打表出来发现他们的差值有规律：

1 2 2 4 4 4 8 8 8 8 16 16 16 16 16 32 32 32 32 32 32.....

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <algorithm>
#include <vector>
#include <queue>
inline void read(long long &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();}
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a < b ? a : b;}
inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}

const int INF = 0x3f3f3f3f;
const int MOD = 1000007;
long long n;
long long base = 1, k = 1, m = 1;
long long ans = 0;

int main()
{
    read(n);
    long long k = 1;
    long long i;
    for(;k <= n;n -= k, ++k)
    {
        ans += (k * (base % MOD)) % MOD;
        ans %= MOD;
        base <<= 1;
        base %= MOD;
    }
    printf("%lld", (ans + (((n % MOD) * (base % MOD)) % MOD)) % MOD);
    return 0;
}