首页 > ACM题库 > HDU-杭电 > HDU 3519-Lucky Coins Sequence[解题报告]HOJ
2014
11-05

HDU 3519-Lucky Coins Sequence[解题报告]HOJ

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)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮