牛客周赛 E-茜茜的计算器

原题链接：E-茜茜的计算器

题目大意：在计算器上显示的0~9十个数字，如果这个计算器有n个位置，可以显示n个数字，问能显示多少种不同的对称数字。只能横轴和竖轴对称。

思路：容斥，最终的答案是横轴对称的数量+纵轴对称的数量-都对称的数量。可以横轴对称的数字有0 1 8 3，这四个数字可以在n个位置随意放置，一定是对称的，那么横轴对称的数量就是 $4^{n}$ 。对于纵轴对称的数字，需要对n的奇偶性质进行讨论，如果奇数，那么中间的那一个位置，可以放0和8二种数字，而且因为是纵轴对称，那么只要确定了一边另一边也就确定了，所以奇数的数量就是 $2*2^{n/2}$ ,如果是偶数那么中间就没有0和8，那么数量就是 $2^{n/2}$ 。对于都对称的数字，那么就是由0和8这二个数字组成的数，那么如果是n是奇数，那么数量就是 $2*2^{n/2}$ ,如果是偶数，那么数量就是 $2^{n/2}$ .

//冷静，冷静，冷静
//调不出来就重构
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1e9+7;
ll ksm(ll a,ll b)
{
	ll ans=1;
	do
	{
		if(b&1)ans*=a;
		a*=a;b>>=1;
		ans%=mod;a%=mod;
	}while(b);
	return ans;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n;cin>>n;
	ll ans=ksm(4,n);
	if(n&1)
	{
		ans=ans+2*ksm(4,n/2)%mod;ans%=mod;
		ans=ans-2*ksm(2,n/2)%mod;ans%=mod;
	}
	else
	{
		ans=ans+ksm(4,n/2)%mod;ans%=mod;
		ans=ans-ksm(2,n/2)%mod;ans%=mod;
	}
	cout<<(ans%mod+mod)%mod;
    return 0;

}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/718672.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！