话说这题TLE了n次，我就知道是输入输出问题，刚开始真心相当无奈（套用大牛代码也TLE），后来突然想起来改用C++提交，怒AC。。。（看来大牛平常也用C++提交啊！g++就是一个坑爹编译器.....)
 
公式推出来很简单，根据题意，F(n)=F(n-1)+2F(n-2)+...+nF(1)+1，试了几组测试数据发现F(n)和兔子数列有关，F(N)是兔子数列的第n-1项，有此得F(n)=3F(n-1)-F(n-2)，后来通过最初的公式推导出了这个。。。果断用矩阵快速幂推，发现超时，这是突然看到数据量很大，果断想到了斐波那契模一个数的循环问题。。现在就这个问题证明一下：若斐波那契数列模一个数存在循环节，则循环节必从1开始，且循环最后的两个数必是1和0。。。证明用反证法：若循环节不在第一位，设F(x)=f(y),f(x+1)=f(y+1)，则可以证明F(x-1)=f(y-1)，与之前假设F(x-1)!=f(y-1)不符合，所以循环一定在第一个，也就推出循环后两个数是1和0。。。初始化的时候，用F(n)=3f(n-1)-f(n-2)初始化，循环节折半为75000，代码略

一、循环队列长度公式
 
队列长度=（Q.rear+MaxSize-Q.front）%MaxSize
 
二、队列长度公式各个变量意义
 
以上各个变量的意义如下：
 
Q.rear：队尾。指向数列队尾元素的下一个空间。
 
Q.front：队头。指向数列队头元素。
 
MaxSize：队列的最大长度。如队列Q.data[10]的表示Q.data[0]~Q.data[9]一共十个元素。
 
三、循环队列相关知识说明
 
1、初始条件：Q.front==Q.rear==0；
 
2、进队操作：队列没满时，先将值送到队尾，再将队尾指针加1。即Q.data[Q.rear]，Q.rear=（Q.rear+1）%MaxSize；
 
3、出队操作：队列不空时，先取队头元素，再讲队头元素加一。即x=Q.data[Q.front]，Q.front=（Q.front+1）%MaxSize；
 
4、判断队列是否为空：Q.front==Q.rear，注意这里队头和队尾不一定是指向0号元素。举个例子，初始时Q.front==Q.rear==0，假如我先在Q.data[0]存入一个数，这时Q.front==0，而Q.rear==1。在这个前提下我们再进行出队操作，则此时Q.front==Q.rear==1，队列为空。
 
5、判断队列是否满了：（Q.rear+1）%MaxSize==Q.front。我们要知道一个前提，即队列如果有十个单元，则我们只能使用9个单元，当队尾指针指向最后一个空单元时，则认为队列已满。这虽然牺牲了一个单元，但也避免了判空条件的冲突。我们想一想，假设 MaxSize=3，如果三个单元都装入元素，那Q.rear的值怎么处理，如果Q.front==Q.rear==0的话不是和判空操作冲突了吗？如果Q.rear==2，那不是和进队操作的进队后队尾指针加一的操作冲突了吗？所以为了操作方便，我们默认牺牲一个空间。
 
 
 
 6、Q.rear一定大于Q.front吗？这肯定不对。我们在进队的时候也可以进行出队操作。
 
如下图所示，当队列满时，如果我们进行出队操作，则Q.front>0。此时队列又变为不满的操作，我们可以继续进行进队操作，则Q.rear会从Q.data[MaxSize-1]（即末尾）回到开头。就像下图这样。
 
 
 
 四、队列长度公式推导。
 
由上面介绍的队列的知识，我们可以知道Q.rear有大于、小于和等于Q.front三种情况。
 
以下推导假设MaxSize=10；
 
1、Q.rear>Q.front
 
假设Q.rear=5，Q.front=2，则现在队列占得单元有Q.data[2]、Q.data[3]、Q.data[4]三个，那么队列长度L=Q.rear-Q.front=3。
 
2、Q.rear=Q.front
 
假设Q.rear=5，Q.front=5。我们知道Q.rear是一定指向空单元的，
 
所以队列长度L=Q.rear-Q.front=0；
 
3、Q.rear<Q.front
 
假设Q.rear=3，Q.front=5，那么队列占得单元有Q.front开头的Q.data[5]、Q.data[6]、Q.data[7]...Q.data[9]5个单元，再加上Q.rear往下数的Q.data[2]、Q.data[1]、Q.data[0]三个单元，一共有8个单元。则MaxSize-Q.front=5，MaxSize-Q.front+Q.rear=8，
 
所以队列长度L=MaxSize-Q.front+Q.rear；
 

3的结果我们将变量位置变一下，则L=Q.reare-Q.front+MaxSize；
 
这时我们发现3的结果不就是在1和2的结果上加了一个MaxSize吗。根据数学取余的性质，
 
（x+ky）%y=x（注：x<y，k∈N）,因此综上所述，队列长度公式可以写成：
 
L=（Q.reare-Q.front+MaxSize）%MaxSize
 
 

 
文章目录
 
while
for
awk（效率更高）
 

 
 
while
 
#!/bin/bash

read -p "请输入一个数字：" num
NUM=${num:-100}
SUM=0
i=1

while [ $i -le $NUM ]
do
  let SUM+=i
  let i++
done

echo "$SUM"
 
[root@localhost xunhuan]#  bash sum1.sh 
请输入一个数字：10
55
 
for
 
#!/bin/bash
read -p "请输入一个数字：" num

NUM=${num:-100}
SUM=0
i=1

for i in `seq $NUM`
do
  SUM=$[SUM+i]
  let i++
done

echo "$SUM"
 
[root@localhost xunhuan]# bash for1.sh
请输入一个数字：10
55
 
awk（效率更高）
 
[root@localhost awk]# cat awk1.sh
#!/bin/bash
sum=0
for((i=0;i<=100000;i++))
do
  ((sum+=i))
done
echo $sum
[root@localhost awk]# bash awk1.sh
5000050000
 
[root@localhost awk]# cat awk2.sh

#!/bin/bash

awk 'BEGIN{while(i++<100000)sum+=i;printf("%d\n",sum)}'
[root@localhost awk]# bash awk2.sh
5000050000

循环队列的相关条件和公式： 
 队尾指针是rear,队头是front，其中QueueSize为循环队列的最大长度 
 1. 队空条件：rear==front 
 2. 队满条件：(rear+1) %QueueSIze==front 
 3. 计算队列长度：（rear-front+QueueSize）%QueueSize 
 4. 入队：（rear+1）%QueueSize 
 5. 出队：（front+1）%QueueSize 
 6. 队列中元素的个数： (rear-front+QueueSize)%QueueSize