题解 P1313 【计算系数】

· · 题解

本题分为两个部分

1. 杨辉三角计算

2. 快速幂

1. 杨辉三角

这里使用了（一维）矩阵加法的方法

一开始矩阵为[1]

然后复制一份, 并在之前添加0, 成为[0, 1]

之后将两个矩阵相加

[1] +[0, 1]

=[1, 1]

同理可知

[1, 1] + [0, 1, 1] = [1, 2, 1]

[1, 2, 1] + [1, 2, 1] = [1, 3, 3, 1]

......

2. 快速幂, 不多说了

代码

    #include<iostream>
    #include<vector>
    using namespace std;
    class matrix{ //单行矩阵类
    private:
            vector<int> data;

    public:
            matrix push\_front(int unit){  //在矩阵头部添加数
                this->data.insert(this->data.begin(), unit);
                return *this;
            }
            matrix push_back(int unit){  //在矩阵尾部添加数，直接vector
                this->data.push_back(unit);
                return *this;
            }
            int& operator[] (int index){  //矩阵标签检索（index）
                return this->data[index];
            }
            matrix operator+ (matrix mat){  //矩阵加法
                matrix ans;
                while(this->data.size() < mat.data.size()){  //矩阵自动扩容
                    this->data.push_back(0);
                }
                while(this->data.size() > mat.data.size()){  //矩阵自动扩容
                    mat.data.push_back(0);
                }
                for(int i = 0; i<this->data.size(); i++){  //矩阵对位相加（记得mod）
                    ans.push_back((this->data[i] + mat.data[i])%10007);
                }
                return ans;
            }
            int size(){  //取矩阵大小
                return this->data.size();
            }
    };
    int pwr(int base, int expr){  //快速幂
        int ans=1;
        base %= 10007;  //记得mod， 不mod就WA*2
        while(expr>0){
            if(expr%2){
                ans = ans*base%10007;  //mod
            }
            expr /= 2;
            base = base*base%10007;  //mod
        }
        return ans;
    }
    matrix x, y;
    int main(){
        ios::sync_with_stdio(false);
        x.push_back(1);  //新建[1]
        int a, b, k, n;
        cin>>a>>b>>k>>n;
        for(int i=0; i<k; i++){
            y = x;
            y.push_front(0);  //复制成[0, 1]
            x = x+y;  //相加
        }
        int ans;
        ans = x[n];
        ans = (((ans*pwr(a, n))%10007)*pwr(b, k-n))%10007;  //其实括号都可以不打，但是一定要每乘一次mod一次，不然WA*4
        cout<<ans<<endl;
    }