51nod 1120 机器人走方格 V3

Type:Lucas+Catalan序列+逆元

题目

N * N的方格,从左上到右下画一条线。一个机器人从左上走到右下,只能向右或向下走。并要求只能在这条线的上面或下面走,不能穿越这条线,有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10007的结果。

Input

输入一个数N(2 <= N <= 10^9)。

Output

输出走法的数量 Mod 10007。

Input示例

4

Output示例

10

题解

画图会发现就是一个Catalan序列,
但我一开始没理解题意,原来只是不能跨过斜线,但可以在斜线上走…

在Excel中画了一下,因为两边是对称的,所以我们只需要求一边,将最终的答案*2即可.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=10007;

LL Pow(LL a,LL b,LL p){
    LL ans=1;
    while(b){
        if(b&1)
        {
            b--;
            ans=(ans*a)%p;
        }
        b>>=1;
        a=(a*a)%p;
    }
    return ans;
}

LL Comb(LL a,LL b,LL p)
{
    if(a < b) return 0;
    if(a == b) return 1;
    if(b > a-b) b = a-b;
    LL ans = 1, ca = 1, cb = 1;
    for(LL i=0; i<b; ++i)
    {
        ca = (ca*(a-i))%p;
        cb = (cb*(b-i))%p;
    }
    ans = (ca*Pow(cb, p-2,p))%p;
    return ans;
}
LL Lucas(LL n, LL m, LL p)
{
    LL ans = 1;
    while(n && m && ans)
    {
        ans = (ans * Comb(n%p, m%p, p))%p;
        n /= p;
        m /= p;
    }
    ///如果等于0则返回1
    return ans==0?1:ans;
}

void extgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
LL inv(LL a,LL n){
    LL d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

int main(){
    LL N;
    while(cin>>N){
        N=N-1;
        LL d1,d2;
        LL x=Lucas(2*N,N,mod);
        LL d=inv(N+1,mod);
        //cout<<"Lucas: "<<x<<endl;
        //cout<<"Inv: "<<d<<endl;
        cout<<2*x*d%mod<<endl;
    }
    return 0;
}

51nod 1119 机器人走方格V2

Type: 组合数学,二项式定理,逆元

题目

M * N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10^9 + 7的结果。

Input

第1行,2个数M,N,中间用空格隔开。(2 <= m,n <= 1000000)

Output

输出走法的数量 Mod 10^9 + 7。

Input示例

2 3

Output示例

3

题解

画一下图会发现这就是杨辉三角,而我们需要求的是C(N+M-2,N-1)
用逆元和递推公式算一下就可以了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1000000+10;
int m,n;

LL inv[maxn];
void init(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    }
}

LL solve(int N,int M){
    ///ans=C(N,M)
    //cout<<N<<" "<<M<<endl;
    LL ans=1;
    for(int i=1;i<=M;++i){
        ans=ans*(N-i+1)*1ll%mod*inv[i]%mod;
    }
    return ans;
}

int main(){
    init();
    while(cin>>m>>n){
        cout<<solve(n+m-2,n-1)<<endl;
    }
    return 0;
}

51nod 1383 整数分解为2的幂

Type: 组合数学,母函数

题目

任何正整数都能分解成2的幂,给定整数N,求N的此类划分方法的数量!由于方案数量较大,输出Mod 1000000007的结果。
比如N = 7时,共有6种划分方法。

7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4

Input

输入一个数N(1 <= N <= 10^6)

Output

输出划分方法的数量Mod 1000000007

Input示例

7

Output示例

6

题解

生成函数

我们可以将题意理解为:

有1,2,4,…,2^N<=1000000 种物品可以选择,每种物品可以选择数量为无限,问你当背包重量为 M 时有多少种选择.

列出生成函数为:

g(m)=(1+x+x^2+x^3+…)(1+x^2+x^4+x^6+…)
(1+x^4+x^8+x^12+…)(1+x^8+x^16+x^24+…)
…(1+x^19) | (因为x^20>1e6)

只需要求出展开式中每项的序数即可,输入 N 输出 K[N]

我们给定一个数组 c1 作为储存系数用.

只需要将每个括号内的式子乘入数组 c1 即可.

限制条件为
i=2^t <= 1000000
j+i <= 1000000

所有的计算都向第一个括号 (1+x+x^2+…+x^1000000)
为基准进行合并,合并到 j+i>1000000 为止.

其他部分解释放在代码中

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1000100;
int c1[maxn]={1};

inline void init(int n){
    for(int i=1;i<=n;i<<=1){
        for(int j=0;(j+i)<=n;++j){
            ///j+i是 当前值为j,加上第log2(i)括号内的等差幂次i
            ///后计算出目标待加值为 (j+i)
            ///即幂次为(j+i)的母函数系数计算过程为:
            /// (k)x^(i+j)=(k1)x^j*x^i*(k2)x^(i+j)
            /// 即 k=k1+k2
            /// 即 c1[j+i]=c[j]+c[j+i]
            ///x^i系数为1因为生成函数第log2(i)个括
            ///号中所有x^i的系数为1
            c1[j+i]=(c1[j+i]+c1[j])%mod;
        }
    }
}


int main(){
    init(1000000);
    int N;

    while(cin>>N){
        cout<<c1[N]<<endl;
    }
    return 0;
}