• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 盧卡斯定理

    使用算法:快速冪逆元、組合公式 

    實現:

    #include <stdio.h>
    using namespace std;
    typedef long long LL;
    LL POW(LL a,LL b,int p)//快速冪求逆元
    {
        LL ans = 1;
        while(b){
            if(b&1)
                ans = (ans%p*a%p) % p;
            a = (a%p*a%p) % p;
            b >>= 1;
        }
        return ans%p;
    }
    LL C(int n,int m,int p)
    {
        if(m > n)return 0;
        if(m == n)return 1;
        if(m > n - m)m = n - m;
        LL a = 1, b = 1 ;
        for(LL i = 0 ; i < m ; i++){
            a = a * (n - i) % p;
            b = b * (i + 1) % p;
        }
        return a * POW(b,p-2,p) % p;//用費馬小定理:a*b的逆元模p 等價于 a/b模p
    }
    LL lucas(int n,int m,int p){
        if(!m||!n)
            return 1;
        return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--){
            int n,m,p;
            scanf("%d%d%d",&n,&m,&p);
            printf("%lld\n",lucas(n,m,p));
        }
        return 0;
    }

     

    版權聲明:本文為qq_40991687原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/qq_40991687/article/details/102907266

    智能推薦

    hdu5698 瞬間移動(組合數取模&&盧卡斯定理&&快速冪)

    有一個無限大的矩形,初始時你在左上角(即第一行第一列),每次你都可以選擇一個右下方格子,并瞬移過去(如從下圖中的紅色格子能直接瞬移到藍色格子),求到第nn行第mm列的格子有幾種方案,答案對10000000071000000007取模。 把這個方格填數: 0 0 0 0 0 0 0 1 1 1 1 1 0 1 2 3 4 5 0 1 3 6 10 15 發現和楊輝三角形有很大關系 1 1 1 1 2...

    hive 導出數據之一列多行,轉為一行多列

    需求:提取數據 說明:原數據是一列多行,需要轉化為一行多列 待查詢表為:temp_05 待查詢數據為: 待查詢數據如圖: 需要提取的數據表頭如下: 預定日期 昨日價格 前天價格 2018-02-01 2018-02-02 2018-02-03 2018-02-04 可用提數 SQL 數據如圖: 以下為嘗試過程 數據如圖: 數據如圖: 數據如圖: 數據如圖:...

    asp.net做一個簡易的聊天室

    要求: 結果: 關鍵代碼: Default.aspx Default.aspx.cs Default2.aspx Default2.aspx.cs Default3.aspx Default3.aspx.cs Default4.aspx...

    動態SQL和多表關聯-筆記

    《動態SQL與多表關聯》筆記 學習目標 能夠使用動態SQL完成SQL拼接 能夠使用resultMap完成多表查詢 能夠使用一對一查詢 能夠使用一對多查詢 (注:多對多其實就是兩個一個多) 映射文件:為什么要resultMap 目標 定義結果映射 使用結果映射 回顧 在mybatis中有2種配置文件: 核心配置文件,如:sqlMapConfig.xml 實體類映射文件,如:UserMapper.xm...

    【OpenGL C++ UE4】獲取模型頂點及面索引數據,并優化存儲結構供UE4繪制

    目錄 一、功能需求 二、成果 三、環境配置 四、詳細步驟 4.1 Max制作三棱錐并處理 4.2 核心代碼 4.2.1 傳入結構體數據 4.2.2 頂點去重、更新索引 4.2.3 輸出本地CSV文件 4.3 UE4繪制 一、功能需求 想必你肯定會問我一個問題,UE4直接導入模型不好么? 哈哈,前提是在做畢設時,導師提供的只有頂點與面索引數據,沒有模型。 下文詳細介紹了畢設開發中的難點,涉...

    猜你喜歡

    解決Pyinstaller打包numpy和pandas庫文件過大問題

    解決Pyinstaller壓縮numpy和pandas庫文件過大問題 文件包類型和網上的方法 Windows下docker的安裝 在docker下實現打包     今天是2021年的第一天,先祝各位小伙伴現年快樂哈。最近因為做了一個項目,需要打包文件,文件中包含了numpy和pandas庫,結果打包出來幾百行的代碼居然要900m,人都傻了,翻遍了全網找解決方...

    【混沌工程】基于ChaosBlade實現網絡故障模擬

    一、前言 很久之前曾基于linux內核自帶的TC和netem模擬一些公網中遇到的極端情況(延遲、丟包、重復、損壞和亂序等),驗證了我們傳輸程序的健壯性! 具體細節可見這篇老博客: https://blog.csdn.net/u013128262/article/details/84784663 最近在復現kafka生產端一個timeout異常場景時,發現之前方案時因為內核和OS版本問題有些差異而無...

    使用FileZilla連接時超時,無法連接到服務器

    用FileZilla連接服務器時,顯示錯誤: 解決方法: 檢查基本的內容 主機是否寫錯 端口是否自定義,默認21 檢查用戶名和密碼是否錯誤 如果連接的是公司內網 使用ping命令,測試一下是否能收到數據 收不到則需要開啟VPN,再ping,看是否能接收數據(請老鐵們用自己最合適的方法解決) 如果開啟VPN后能接收數據,則可以連接一下服務器,如果不行(怎么可能不行),則跳轉3并依次嘗試 開啟VPN后...

    反匯編:結構體拷貝傳參

    一、結構體拷貝傳參 二、引用和常引用傳參 三、大結構體做形參/數組拷貝...

    精品国产乱码久久久久久蜜桃不卡