233 Matrix

比眉伴天荒 2022-01-08 00:25 207阅读 0赞

[233 Matrix][]

有一\\(n\\times m\\)的矩阵\\(\\\{a\\\}\\)，定义\\(a\[0\]\[0\]=0,a\[0\]\[1\]=233,a\[0\]\[2\]=2333,a\[0\]\[3\]=23333...\\),然后给出\\(a\[1\]\[0\],a\[2\]\[0\],...,a\[n\]\[0\]\\),未给出或定义的位置满足\\(a\[i\]\[j\]=a\[i-1\]\[j\]+a\[i\]\[j-1\]\\),询问\\(a\[n\]\[m\]\\)的值\\(mod\\ 10000007\\)，\\(n ≤ 10,m ≤ 10^9\\)。

### 解 ###

显然对于第0行，我们有转移方程\\(a\[0\]\[i\]=a\[0\]\[i-1\]\\times 10+3\\)，这个是可以转移的，显然需要增添辅助1，注意到n很小，故考虑整个压维，故设状态矩阵（以n=2为例）

\\\[\\begin\{bmatrix\}1&a\[0\]\[i\]&a\[1\]\[i-1\]&a\[2\]\[i-1\]\\end\{bmatrix\}\\\]

不难得知转移方程

\\\[\\begin\{bmatrix\}1&3&0&0\\\\0&10&1&1\\\\0&0&1&1\\\\0&0&0&1\\end\{bmatrix\}\\\]

于是根据规律，填写转移矩阵和状态矩阵即可。

参考代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #define il inline
    #define ri register
    #define ll long long
    #define yyb 10000007
    using namespace std;
    struct matrix{
        ll jz[12][12];
        il void clear(){
            memset(jz,0,sizeof(jz));
        }
        il void unit(){
            clear();ri int i;
            for(i=0;i<12;++i)jz[i][i]=1;
        }
        il void print(){
            ri int i,j;
            for(i=0;i<12;++i,putchar('\n'))
                for(j=0;j<12;++j)
                    printf("%lld ",jz[i][j]);
            putchar('\n');
        }
        il matrix operator*(matrix x){
            matrix y;y.clear();
            ri int i,j,k;
            for(i=0;i<12;++i)
                for(j=0;j<12;y.jz[i][j]%=yyb,++j)
                    for(k=0;k<12;++k)
                        y.jz[i][j]+=jz[i][k]*x.jz[k][j]%yyb;
            return y;
        }template<class free>
        il matrix operator^(free y){
            matrix ans,x(*this);ans.unit();
            while(y){
                if(y&1)ans=ans*x;
                x=x*x,y>>=1;
            }return ans;
        }
    }tran,state;
    int main(){
        ll n,m;int i,j;
        while(scanf("%lld%lld",&n,&m)!=EOF){
            state.jz[0][0]=1,state.jz[0][1]=233;
            for(i=2;i<=n+1;++i)scanf("%lld",&state.jz[0][i]);
            tran.jz[0][0]=1,tran.jz[0][1]=3,tran.jz[1][1]=10;
            for(i=2;i<=n+1;++i)
                for(j=1;j<=i;++j)
                    tran.jz[j][i]=1;
            state=state*(tran^m);
            printf("%lld\n",state.jz[0][n+1]);
            tran.clear(),state.clear();
        }
        return 0;
    }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10887331.html

[233 Matrix]: http://acm.hdu.edu.cn/showproblem.php?pid=5015