网站改版设计,WordPress无刷新音乐,网站开发服务器多少钱,中国最近新闻大事件文章目录题目题解code题目
九连环是一种源于中国的传统智力游戏。 如图所示#xff0c;九个的圆环套在一把“剑”上#xff0c;并且互相牵连。游戏的目标是把九个圆环全部从“剑”上卸下。 圆环的装卸需要遵守两个规则 1#xff0e;第一个#xff08;最右边#xff09;环…
文章目录题目题解code题目
九连环是一种源于中国的传统智力游戏。 如图所示九个的圆环套在一把“剑”上并且互相牵连。游戏的目标是把九个圆环全部从“剑”上卸下。 圆环的装卸需要遵守两个规则 1第一个最右边环任何时候都可以任意装上或卸下 2如果第k个环没有被卸下且第k个环右边的所有环都被卸下则第kl个环第k个环左边相邻的环 可以任意装上或卸下与魔方的千变万化不同解九连环的最优策略是唯一的。 为简单起见我们以“四连环”为例演示这一过程。这里用1表示环在“剑”上0表示环已经卸下。 初始状态为1111每步的操作如下
1101根据规则2卸下第2个环1100根据规则1卸下第1个环0100根据规则2卸下第4个环0101根据规则1装上第1个环0111根据规则2装上第2个环0110根据规则1卸下第1个环0010根据规则2卸下第3个环0001根据规则1装上第1个环0001根据规则2卸下第2个环0000根据规则1卸下第1个环
由此可见卸下“四连环”至少需要10步。 随着环数增加需要的步数也会随之增多。例如卸下九连环就至少需要341步。 请你计算有n个环的情况下按照规则全部卸下至少需要多少步
Input 输入文件第一行为一个整数m表示测试点数目。 接下来m行每行一个整数n。 1≤n≤10^51≤m≤10 Output 输出文件共m行对应每个测试点的计算结果
Sample Input 3 3 5 9 Sample Output 5 21 341
题解
直接给递推式f(n)f(n−1)2∗f(n−2)1f(n)f(n-1)2*f(n-2)1f(n)f(n−1)2∗f(n−2)1结论就是2n13\frac{2^{n1}}{3}32n1 从三个不同的方向走向一起 1.1.1.买一本高中数学必修5里面有九连环的结论详细证明 2.2.2.打表发现规律
n123456712510214285
转换成二进制规律越发明显
n1234567125102142851101011010101011010101010101
好看吧发现1,01,01,0是不相邻的就可以考虑二进制乘法竹格利兹 1010101×111010101101010111111111(271−1)\begin{aligned} 1010101\\×11\\1010101\\1010101~~\\11111111\\(2^{71}-1)\end{aligned}1010101×1110101011010101 11111111(271−1)
101010×111010101010101111110(261−2)\begin{aligned} 101010\\×11\\101010\\101010~~\\1111110\\(2^{61}-2)\end{aligned}101010×11101010101010 1111110(261−2) 总结一下就是 2n13\frac{2^{n1}}{3}32n1 3.3.3.感性理解观看四连环的例子我们发现首先是把四连环111111111111变成两连环110011001100然后就可以把nnn环拿走然后用同样的步数变回四连环011101110111然后就是同理去拿走n−1n-1n−1环所以我们设f(n)f(n)f(n)表示nnn连环的方案数那么可以表示成拿走n−2n-2n−2环的方案数然后把拿走最后一个环把最右边的第一个环装回来111再用同样的步数变成n−2n-2n−2环的方案数继续处理n−1n-1n−1环的方案数 f(n)f(n−1)2∗f(n−2)1f(n)f(n-1)2*f(n-2)1f(n)f(n−1)2∗f(n−2)1 1≤n≤1051\le n\le 10^51≤n≤105所以就要高精啦然后再套一个FFTFFTFFT优化看代码吧如果有任何不懂的欢迎评论
code
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define MAXN 80005
struct complex {double real, i;complex () {}complex ( double x, double y ) {real x;i y;}
};
complex operator ( complex a, complex b ) {return complex ( a.real b.real, a.i b.i );
}
complex operator - ( complex a, complex b ) {return complex ( a.real - b.real, a.i - b.i );
}
complex operator * ( complex a, complex b ) {return complex ( a.real * b.real - a.i * b.i, a.real * b.i b.real * a.i );
}
double pi acos ( -1.0 );int rev[MAXN];void FFT ( complex *c, int f, int len ) {for ( int i 0;i len;i )if ( i rev[i] )swap ( c[i], c[rev[i]] );for ( int i 1;i len;i 1 ) {complex omega ( cos ( pi / i ), f * sin ( pi / i ) );for ( int j 0;j len;j ( i 1 ) ) {complex w ( 1, 0 );for ( int k 0;k i;k , w w * omega ) {complex x c[j k], y w * c[i j k];c[j k] x y;c[i j k] x - y;}}}
}struct big {int g[MAXN], len;big () {memset ( g, 0, sizeof ( g ) );len 0;}big ( int x ) {memset ( g, 0, sizeof ( g ) );len 0;if ( ! x ) {len 1;return;}while ( x ) {g[len ] x % 10;x / 10;}}big operator * ( const big b ) {static complex A[MAXN], B[MAXN];int new_len len b.len, limit 1, l 0;while ( limit new_len ) {limit 1;l ;}for ( int i 0;i limit;i )rev[i] ( rev[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for ( int i 0;i limit;i ) {A[i] complex ( i len ? g[i] : 0, 0 );B[i] complex ( i b.len ? b.g[i] : 0, 0 );}FFT ( A, 1, limit );FFT ( B, 1, limit );for ( int i 0;i limit;i )A[i] A[i] * B[i];FFT ( A, -1, limit );static int ans[MAXN];for ( int i 0;i limit;i )ans[i] ( int ) ( A[i].real / limit 0.5 );for ( int i 0;i limit;i )if ( ans[i] 9 ) {ans[i 1] ans[i] / 10;ans[i] % 10;}-- limit;while ( limit 0 ans[limit] 0 )limit --;len limit;for ( int i 0;i limit;i )g[i] ans[i];}big operator / ( int x ) {int sum 0, new_len 0;for ( int i len - 1;i 0;i -- ) {sum ( sum 1 ) ( sum 3 ) g[i];if ( sum x )g[i] 0;else {if ( ! new_len ) new_len i 1;g[i] sum / x;sum % x;}}len max ( new_len, 1 );}void print () {for ( int i len - 1;i 0;i -- )printf ( %d, g[i] );printf ( \n );}
}result, tmp;int main() {int m, n;scanf ( %d, m );while ( m -- ) {scanf ( %d, n );n ;result ( 1 ), tmp ( 2 );while ( n ) {if ( n 1 )result * tmp;tmp * tmp;n 1;}result / 3;result.print();}return 0;
}
