组合数问题 题解(虚数)

组合数问题

https://ac.nowcoder.com/acm/contest/9986/F

题目链接

题目大意

计算

题目思路

如果是计算

显然

两式相加

而下面就有点神奇要类比,想到虚数第一次真想不到

最终

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,mod=998244353;
ll n;
ll qpow(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1){
            ans=ans*base%mod;
        }
        b=b>>1;
        base=base*base%mod;
    }
    return ans;
}
int main(){
    scanf("%lld",&n);
    ll ans=((qpow(2,n)+2*qpow(-4,n/4))*qpow(4,mod-2)%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 10:56
点赞 评论 收藏
分享
_mos_:我以为手抄报简历就已经很顶了,没想到还有表格简历
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务