P3414 SAC#1 - 组合数题解

2021-06-08 20:04

阅读：326

标签：inf 运算符重载 nbsp tps style ble iostream 有一个 ace

https://www.luogu.org/problemnew/show/P3414（题目传送）

这道题提醒大家一定要认真审题。看清楚后发现n的数据范围稍微小于long long类型的范围（看不清被0吓到的估计都去写近百行高精度和运算符重载了吧。。。），又知道关于组合数的

一个定理：

　　　　卢卡斯定理：（求解C(n,m)%p）C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

一些公式：

技术图片

这样，解题的核心就是求2^(n-1)，这里可以用快速幂来做。

AC代码：

#include
#includeusing namespace std;
const long long p=6662333;
long long ksm(long long a,long long b)
{
    long long ans=1,c=a;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    long long n;
    cin>>n;
    cout2,n-1);
    return 0;
}

题很简单，重要的是题带给我们的思考。考试时有一个知识点不知道，难度很容易就涨上去了。所以平时还是要多学，同时不能忘了学过的东西（公式书上可都有啊）。在做题时的审题也很重要，想想码上2小时后突然发现审错题时有多悲伤啊。。。

P3414 SAC#1 - 组合数题解

标签：inf 运算符重载 nbsp tps style ble iostream 有一个 ace

原文地址：https://www.cnblogs.com/InductiveSorting-QYF/p/10686205.html

上一篇：Elasticsearch6.x indices apis（索引api）

下一篇：CentOS7.6下模拟iSCSI，Windows来连

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：P3414 SAC#1 - 组合数题解
文章链接：http://soscw.com/index.php/essay/92351.html

亲，登录后才可以留言！

P3414 SAC#1 - 组合数题解

评论

热门文章

推荐文章

最新文章

置顶文章

P3414 SAC#1 - 组合数 题解

评论

热门文章

推荐文章

最新文章

置顶文章

P3414 SAC#1 - 组合数题解