P3414 SAC#1 - 組合數(shù)

題目背景

本題由世界上最蒟蒻最辣雞最撒比的SOL提供。

寂月城網(wǎng)站是完美信息教室的官網(wǎng)。地址：http://191.101.11.174/mgzd?。

題目描述

辣雞蒟蒻SOL是一個傻逼，他居然覺得數(shù)很萌！

今天他萌上了組合數(shù)。現(xiàn)在他很想知道simga(C(n,i))是多少；其中C是組合數(shù)（即C(n,i)表示n個物品無順序選取i個的方案數(shù)），i取從0到n所有偶數(shù)。

由于答案可能很大，請輸出答案對6662333的余數(shù)。

輸入輸出格式

輸入格式：

?

輸入僅包含一個整數(shù)n。

?

輸出格式：

?

輸出一個整數(shù)，即為答案。

?

輸入輸出樣例

輸入樣例#1：
3 輸出樣例#1：
4

說明

對于20%的數(shù)據(jù)，n <= 20；

對于50%的數(shù)據(jù)，n <= 1000；

對于100%的數(shù)據(jù)，n <= 1 000 000 000 000 000 000 (10^18)

/*楊輝三角第n行的和為2^n偶數(shù)項即為2^(n-1) */ #include<iostream> #include<cstdio> #define mod 6662333 using namespace std; long long n; long long mul(long long a,long long b){long long res=0;while(b){if(b&1)res=(res+a)%mod;a=(a+a)%mod;b>>=1;}return res; } long long pow(long long a,long long b){long long res=1;while(b){if(b&1)res=mul(res,a)%mod;a=mul(a,a)%mod;b>>=1;}return res; } int main(){cin>>n;cout<<pow(2,n-1); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/thmyl/p/7573896.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P3414 SAC#1 - 组合数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。