题解

17 条题解

  • 0
    @ 2017-07-05 15:17:11

    只能拿20分的高精度

    #include<iostream>
    #include<string>
    #define L 20000000
    using namespace std;
    string add(string a,string b)
    {
        string ans;
        int na[L]={0},nb[L]={0};
        int la=a.size(),lb=b.size();
        for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
        for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
        int lmax=la>lb?la:lb;
        for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
        if(na[lmax]) lmax++;
        for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
        return ans;
    } 
    string sub(string a,string b)
    {
        string ans;
        int na[L]={0},nb[L]={0};
        int la=a.size(),lb=b.size();
        for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
        for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
        int lmax=la>lb?la:lb;
        for(int i=0;i<lmax;i++)
        {
            na[i]-=nb[i];
            if(na[i]<0) na[i]+=10,na[i+1]--;
        }
        while(!na[--lmax]&&lmax>0)  ;lmax++;
        for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
        return ans;
    }
    string mul(string a,int b)
    {
        string ans;
        int La=a.size(),na[L];
        fill(na,na+L,0);
        for(int i=La-1;i>=0;i--) na[La-i-1]=a[i]-'0';
        int w=0;
        for(int i=0;i<La;i++) na[i]=na[i]*b+w,w=na[i]/10,na[i]=na[i]%10;
        while(w) na[La++]=w%10,w/=10;
        La--;
        while(La>=0) ans+=na[La--]+'0';
        return ans;
    }
    string div(string a,int b)
    {
        string r,ans;
        int d=0;
        if(a=="0") return a;//特判
        for(int i=0;i<a.size();i++)
        {
                r+=(d*10+a[i]-'0')/b+'0';//求出商
                d=(d*10+(a[i]-'0'))%b;//求出余数
        }
        int p=0;
        for(int i=0;i<r.size();i++)
        if(r[i]!='0') {p=i;break;}
        return r.substr(p);
    }
    int mod(string a,int b)
    {
        int d=0;
        for(int i=0;i<a.size();i++) d=(d*10+(a[i]-'0'))%b;//求出余数
        return d;
    }
    int main(){
        int n,m; cin>>n>>m;
        string s="0",c="1";
        for(int i=4;i<=n;++i){
            c=div(mul(c,4*i-2),i+1);
            s=add(s,c);
        }
        cout<<mod(s,m);
    }
    
  • 0
    @ 2014-09-30 09:44:43

    你们赢了- - 看见中国剩余定理我就不想做了 我还以为是裸Catalan加上一点点处理呢- -

  • 0
    @ 2009-10-22 22:23:49

    现在很流行占楼?

  • 0
    @ 2009-10-22 14:35:41

    模数是p^k怎么解决,怎么处理除数中有p的部分?

  • 0
    @ 2009-10-20 17:39:01

    拍砖

  • 0
    @ 2009-10-14 22:05:40

    OrZ教主………… 快看吐了……

  • 0
    @ 2009-10-13 22:58:08

    什么是中国剩余定理?

  • 0
    @ 2009-10-13 19:37:28

    中国剩余定理………………LHX教主总是喜欢出题虐人

  • 0
    @ 2009-10-12 22:56:32

    本题直把我弄到天旋地转,日转星移...

    orz lssssssssss...

  • 0
    @ 2009-10-15 15:49:52

    orz lhx教主!catalan数前n-2项累加和!

    说说此题思路吧。分解质因数,设要求mod p^k的值,那就把p的因子记录,其余就乘除到余数上,除法用扩展欧几里得。最后用中国剩余定理。

    要敢于用qword

  • 0
    @ 2009-10-12 21:46:07

    占楼~~~~~

  • 0
    @ 2009-10-12 18:40:27

    有点难度啊!

  • 0
    @ 2009-10-12 16:58:27

    先坐坐

  • 0
    @ 2009-10-12 14:46:18

    占楼~~~~~orz

  • 0
    @ 2009-10-12 14:43:12

    占楼~~~~~orz

  • 0
    @ 2009-10-12 14:21:08

    占楼~~~~~orz宋神牛

  • 0
    @ 2009-10-12 12:06:03

    应该是分解质因数然后中国剩余定理合并吧...

    有除法就用逆元 - -

  • 1

信息

ID
1670
难度
8
分类
数论 | 组合数学 | Catalan数列 点击显示
标签
递交数
89
已通过
10
通过率
11%
上传者