【算法随记】C(n,m)不越界但A(n,m)越界；C(n,1)+C(n,3)+C(n,5)...等二项式定理；“memset”: 找不到标识符-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法随记】C(n,m)不越界但A(n,m)越界；C(n,1)+C(n,3)+C(n,5)...等二项式定理；“memset”: 找不到标识符。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

https://codeforces.com/contest/893/problem/E

C(n,m)不越界但A(n,m)越界的解决方案

C(n,m) = A(n,m) / (n-m)!

这题要模1e9+7，但是只有加减乘能模，除法模不了。所以这个A(n,m)要存原值，原值也太大了，爆 long long

要是能不要除法，全是乘法就好了

法一：拆成多个质数相乘

先算A(n,m)里有多少个2 3 5 7，再减去(n-m)!中2 3 5 7的个数，最后把剩下的乘起来文章来源地址https://www.toymoban.com/news/detail-677692.html

long long C(int n, int m){
   
    long long ret=1;
 
    unordered_map<int,int> table;
    for(int x=n;x>m;x--){
   
        int tmpx=x;
        for(int i=2;i<=tmpx;i++){
   
            if(tmpx%i==0){
   
                int tmpcnt=1;
                tmpx=tmpx/i;
                while(tmpx%i==0 && tmpx){
   
                    tmpcnt++;
                    tmpx/=i;
                }
                table[i]+=tmpcnt;
            }
        }
    }
    for(int x=n-m;x>=1;x--){
   
        int tmpx=x;
        for(int i=2;i<=tmpx;i++){
   
            if(tmpx%i==0){
   
                int tmpcnt=1;
                tmpx=tmpx/i;
                while(tmpx%i==0 && tmpx){
   
                    tmpcnt++;
                    tmpx/=i;
                }
                table[i]-=tmpcnt;
            }
        }
    }
 
    for(auto it=table.begin(); it!=table.end();it++){
   
        int x=it->first;
        int cnt=it->second;