2010-1123

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by 猛犸也钻地

解题报告：

{{{
这题我是找规律的，首先k是偶数的话答案就是0，k是奇数的话，把k赋值为(k-1)/2代入公式：

ans = binomial(n+1+k,2*k+1) * (1<<2*k) * (n*2+1) / (n+1+k) % 1000000007

另外若赋值后的k为奇数，则ans取负数，即ans = (1000000007 - ans) % 1000000007
}}}


代码：

{{{
#include <cstdio>
#include <cstring>
using namespace std;

class BigNum{
public:
    int len;
    long long num[300];
    BigNum(int k = 0){
        len=0;
        memset(num,0,sizeof(num));
        do num[len++]=k%10; while(k/=10);
    }
    BigNum operator *(int k) const{
        BigNum tmp(*this);
        for(int i=0;i<tmp.len;i++) tmp.num[i]*=k;
        for(int i=0;i<tmp.len;i++) if(tmp.num[i]>=10){
            tmp.num[i+1]+=tmp.num[i]/10;
            tmp.num[i]%=10;
            if(i==tmp.len-1) tmp.len++;
        }
        return tmp;
    }
    BigNum operator /(int k) const{
        BigNum tmp(*this);
        for(int i=tmp.len-1;i>0;i--){
            tmp.num[i-1]+=tmp.num[i]%k*10;
            tmp.num[i]/=k;
            if(i==tmp.len-1 && !tmp.num[i]) tmp.len--;
        }
        tmp.num[0]/=k;
        return tmp;
    }
    int operator %(int k) const{
        BigNum tmp(*this);
        for(int i=tmp.len-1;i>0;i--){
            tmp.num[i-1]+=tmp.num[i]%k*10;
            tmp.num[i]/=k;
            if(i==tmp.len-1 && !tmp.num[i]) tmp.len--;
        }
        return tmp.num[0]%k;
    }
};

BigNum binomial(int n, int m){
    BigNum s=1;
    for(int i=1;i<=m;i++) s=s*(n-i+1)/i;
    return s;
}

int main(){
    int n,k;
    while(scanf("%d%d",&n,&k)>0){
        if(k%2==0){
            puts("0");
            continue;
        }else{
            k=(k-1)/2;
            int ans=binomial(n+1+k,2*k+1)*(1<<2*k)*(n*2+1)/(n+1+k)%1000000007;
            if(k%2 && ans) ans=1000000007-ans;
            printf("%d\n",ans);
        }
    }
}
}}}

by 猛犸也钻地

解题报告：

这题我是找规律的，首先k是偶数的话答案就是0，k是奇数的话，把k赋值为(k-1)/2代入公式：
ans = binomial(n+1+k,2*k+1) * (1<<2*k) * (n*2+1) / (n+1+k) % 1000000007
另外若赋值后的k为奇数，则ans取负数，即ans = (1000000007 - ans) % 1000000007

代码：

#include <cstdio>
#include <cstring>
using namespace std;
class BigNum{
public:
    int len;
    long long num[300];
    BigNum(int k = 0){
        len=0;
        memset(num,0,sizeof(num));
        do num[len++]=k%10; while(k/=10);
    }
    BigNum operator *(int k) const{
        BigNum tmp(*this);
        for(int i=0;i<tmp.len;i++) tmp.num[i]*=k;
        for(int i=0;i<tmp.len;i++) if(tmp.num[i]>=10){
            tmp.num[i+1]+=tmp.num[i]/10;
            tmp.num[i]%=10;
            if(i==tmp.len-1) tmp.len++;
        }
        return tmp;
    }
    BigNum operator /(int k) const{
        BigNum tmp(*this);
        for(int i=tmp.len-1;i>0;i--){
            tmp.num[i-1]+=tmp.num[i]%k*10;
            tmp.num[i]/=k;
            if(i==tmp.len-1 && !tmp.num[i]) tmp.len--;
        }
        tmp.num[0]/=k;
        return tmp;
    }
    int operator %(int k) const{
        BigNum tmp(*this);
        for(int i=tmp.len-1;i>0;i--){
            tmp.num[i-1]+=tmp.num[i]%k*10;
            tmp.num[i]/=k;
            if(i==tmp.len-1 && !tmp.num[i]) tmp.len--;
        }
        return tmp.num[0]%k;
    }
};
BigNum binomial(int n, int m){
    BigNum s=1;
    for(int i=1;i<=m;i++) s=s*(n-i+1)/i;
    return s;
}
int main(){
    int n,k;
    while(scanf("%d%d",&n,&k)>0){
        if(k%2==0){
            puts("0");
            continue;
        }else{
            k=(k-1)/2;
            int ans=binomial(n+1+k,2*k+1)*(1<<2*k)*(n*2+1)/(n+1+k)%1000000007;
            if(k%2 && ans) ans=1000000007-ans;
            printf("%d\n",ans);
        }
    }
}