2014
11-05

# Lucky Coins Sequence

As we all know,every coin has two sides,with one side facing up and another side facing down.Now,We consider two coins’s state is same if they both facing up or down.If we have N coins and put them in a line,all of us know that it will be 2^N different ways.We call a "N coins sequence" as a Lucky Coins Sequence only if there exists more than two continuous coins’s state are same.How many different Lucky Coins Sequences exist?

There will be sevaral test cases.For each test case,the first line is only a positive integer n,which means n coins put in a line.Also,n not exceed 10^9.

There will be sevaral test cases.For each test case,the first line is only a positive integer n,which means n coins put in a line.Also,n not exceed 10^9.

3
4

2
6

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define LL long long
#define FF(i, n) for (int i = 0; i < n; i++)
#define M 2

int ans[M];
int ret[M][M], mod = 10007;
int init[M][M];
int s[M][M] = { 1, 1,
1, 0 };

void ini(int n)
{
FF(i, n) FF(j, n) init[i][j] = s[i][j];
}

void matmul(int a[][M], int b[][M], int n)
{
int tp[M][M] = {0};
FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
tp[i][j] = (tp[i][j]+(LL)a[i][k]*b[k][j]) % mod;
FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void qmod(int n, int b)
{
FF(i, n) FF(j, n) ret[i][j] = (i==j);
for ( ; b; b >>= 1)
{
if (b & 1) matmul(ret, init, n);
matmul(init, init, n);
}
}

int cal(int a, int b)
{
a %= mod;
int res = 1;
for ( ; b; b >>= 1)
{
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}

int main()
{
int n;
while (cin >> n)
{
ini(M);
qmod(M, n+1);
cout << (cal(2,n)-2*ret[0][1]%mod+mod)%mod << endl;
}
return 0;
}

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

2. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

4. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮