Radio Towers

DIV2-D

题意:
给你一个数n,代表这个线段长度,然后你可以选择奇数,就是用这些奇数加起来正好为n,注意顺序不同也代表不同的方案,问最后到底有多少方案满足条件,这就是所有可能的条件,然后最后再除以2的n次方即可,记得取模要求一下逆元。

思考:
记得要简化题意,其实题意那样说,最后理解下来就是上述所描述的,也想到了下面肯定就是2的n次方,但是上面的n用奇数组成的方案数到底该怎么求呢。当我想来想去想到完全背包的时候,但是背包不考虑顺序啊,并且复杂度也太高了。然后又想搜索,搜索肯定也超时。最后想来想去感觉有点像多诺米骨牌,就是灵感就是觉的像,虽然我说不清,要不然这个方案根本没法直接求,其实答案恰恰就是这个多诺米骨牌,就是菲切那波数列。然后方案就出来就可以了,官方题解也是说恰恰是菲切那波数列,也给出了归纳法的证明。

代码:

int T,n,m;
int va[N];
int dp[N];

int ksm(int a,int b)
{
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return sum%mod;
}

signed main()
{
	IOS;
	cin>>n;
	dp[1] = dp[2] = 1;
	for(int i=3;i<=n;i++) dp[i] = (dp[i-1]+dp[i-2])%mod;
	int a = dp[n]%mod;
	int b = ksm(2,n);
	int ans = (a%mod)*(ksm(b,mod-2)%mod)%mod;
	cout<<ans<<"\n";
	return 0;
}

总结:
当感觉目前的思路正确,但是中间有一步不知道该怎么求的时候,就想一想性质和以前做过的题目,联系一下,一般cf都是这种结论思维性的。大胆去尝试。

上一篇:element Ui select下拉 三级联动 带radio单选框


下一篇:22-radio单选框