组合数问题 题解(虚数)

组合数问题

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;
}
全部评论

相关推荐

点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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