首页 技术 正文
技术 2022年11月16日
0 收藏 403 点赞 3,545 浏览 4652 个字
Day8-例1
难度级别:B; 运行时间限制:1000ms; 运行空间限制:256000KB; 代码长度限制:2000000B
试题描述
给定n、m的值,求

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAIAAAABxCAYAAAAd8Kt3AAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAAhXSURBVHhe7Z2JdqM6DIZFgGw0ff/nTLMDyUgGgyEmZbHBHes7p3falBtS/FubhQleCDDesir/ZTyFBeA5LADPYQF4DgvAc1gAnsMC8BwWgOewADyHBeA5LADPYQF4DgvAc6wIIIkDCILiK9p8la+qr8eQfH2XrzJLYkUA5/QFh/0WQvw+WK3g+yuBGAf+ER0gWdOrGTxycSizMNZcwDNLIYcI1uET0tsD1skB0usRXk8a+RAidj5OYGUYvr++IM9xoKM1wP0GsNnB+XQUrz+p/SSMIQyKY5llsTMPXzmkNNGzC5r9PVzPx8brYRjCCQXBLI8dATwzNP8IDj6ZfUnhFoq4gHEDKyORZxn+N4StCPhqCv9PcUHxM7M8xgVQ+floU5t+hDKBB+kC4wKKBxg3MG8BpJ9ftaK8/IHJH45/FEISR7BLuA7gAsYFUPj5EOKOPC+7/TQDQ2ZR+L4Az7ESBDJ/BxaA57AAPIcF4DksAM9hAXgOC8BztHUAKuemtzPcxIrO0oSw3btdOPpOdnC53CCP9vBKz+WrfwOtBTieThDHUfnT0uSQPctvGeN8rAR+bSI4d/RuRduiw8c01WwqfyZsnYv5JQY43bOyh++d7HaxsqBzPF8hQ03uXTFA/zm/BoEkAv1g5HC7XK1194abBLal9l5PN30AWauo7H421ems66iuz9NcRa2OjZPyleH0ygLUwWiSwQVnrA0RiDhkU3QWu0rDWhnqcxAd1Vt6w2JF9XsXw88dYCteyyHFgIiC9F1EXdbluLye8DVyDHoJQAzG9oMIbunoD/CRAC8CnjMXHSZuQrMTjeR7/8MEnuLvDXBwUrhka3hl12qgqJ0uF422B9iFL8gmZmq9BEAUItiD3hvc4Hw3nzPSOQ1eVzuI/sfu/oc2DbehMd11R3UEzwfO/E0x64o2uwjWcK37KXDmk1SmNNn2FgBxPJ1hV97w8UZ2meSLughW2rM5gxiYAW3usjFWkD007rOY1eEL33cdi4Gt2ulwxt/RIsiM6Lfmmz4M/j/J7+0/iEC9FcwEFIS6WlypBiZY9Z6Bq3hTW1Fd3FC2zmHgpbTTFzMd8gA2pUWoLAW5iglWcpR0hAhEUPJO/jhDvLMQD7iI0ufYF7KiKQaOVH7RCVt2VKuzWlqNcL2pBSPvvZgYfI62HcdrWkar71Dfnw8iKII1c7e5VR3VLZci2+k3sXKi8t6LIeLTMemjkwjmLhS5QmWCxWDlOGN30zMhzZ1TXe30VVC4SlEE4889WbtLFYqcgTKg8wPW2yJgm4Quo/joZjAFFzWC8ec21hVMVakLfdI3Ithj6mOiSDIEmjnX86UIqFqfofk7pGMVr/E3GVjpU9dWwnUC2f0kvl8SQ94L/6BP1UJbhaIWNLC0DwHl2D+NAa7Np6isqb8jsnvDXclcvSHo1jF9oUGXpd16YW1a6mYSY59iiUJRGzXCVmMTaT5pMH5ugNbgAIdEL1gafFqNDLYH8T5TF6VEGovv0zzftNTNJEZlKApFSYcILBWKuigiZ6K4GZVm/vkR6N1RGXUL13BJId7bWH5WyraG1g1MYNwO/VYtNF0o0lFFzgRe7BBDq6uY+crgyzyaCFZ4IWgnkzu6+rr7qPE+Uze1kMUcZGrqZhIrjuhzoehuPzOQ1TQkxL8wxZQUtq2ZL/cwQGhAnukNsrjVeqYM2tRNLeoSsFvb41j7KPpCEfX32c8IigINgcEWPCANkzeTXuTRRJFL356bt2PUQZsStNVlW2SqJTGMVS22C0URBom2mzubFxtnfx7BVq2gIU0XEcETAzVZY5cYHTTF3bi2PY5VARSBVzmHMO+dpa9P9e04gEGsKZIoLgIyMv0aq2Rw0NQVQNe2x7H2aUQ6dSsvc7Sfr+ih+HYIt9Ca2ILa/CMdx5gy/0Q7I3EJKwIo0qmysxcvcKK7wpZQBzfSzP6G+Uf0x5gz/+2MxJX0T2JFAPldKcGaqJH3pDm4HbNNiey7Zn87RZz0+RV341L6JzEuAKq2FSXUeSL+Bqpv75htqj/WzX6icQwOGglr7GpfbZHq9I/WGFxZLjcqADXomyPib1Onf/rZ1jDtHRZCd0x+H7fa17BIstqI1+i+mikg7oExAahB32wRv0KfwW2Y9k5/rHbaUts7bWo10pKp7kYsG//AT7Z2YhVQYkQApPQq6Jsz4lfpMbht064ngOpXFMCWm1yPomxrLyCXeHCuv3FyPwDNvOpOYrpgMwZ9zHQmW4D8Lm8jnzfiZ8wwSQCLRvyMEUYLYO6I/3uX/P/9hQswSgBLRPx5doHLDF1FvjFYAEtE/DKfNnkDJlMwSABFxF+Weees8ZcVPn7QhHkGXdElIn5hcYS74QdN2aD3JV0i4heDX7Vwu9NJ+z/RSwDzR/zxe29/GKEEGNP8WgmUffKLx98G7sxh3vloARoR/8JwBmCHTgE0In4H4AzADp1XtY74XYAzAFtoLyvNfqW3wgE4A7CFsdvDmb8JG1bPYQF4DgvAc1gAnsMC8BxnBCC3Pp9jAwmmZrQAaI1AbHo8cdsXufDT2JCJmY3FLQDtIUCliK5dRxm7jBaAfFgCr9D9bTgI9JzBAqh8v/gy85wcZjkGC8DGc3KY5RjlAsgK6J6To26L+tsXp3tuMC4G6HhOjtwWtc+XS7dI+8woAYhdLxzb744Zx2AByLt0Ju+dwzjBcAtQ3qWj22CBY4C/x2ABfHpODscAf49BAqj24RH+39BzckrkBk8uPyX0f2S4CyAMPidHFpaqp2nQcwXYRcwGN4V6zjgLwPw3sAA8hwXgOSwAz2EBeA4LwHNYAJ7DAvAcFoDnsAA8hwXgOSwAz2EBeA4LwGsA/gFr63V18OsRjgAAAABJRU5ErkJggg==” alt=”” />的值。

答案对10^9+7取模。

输入
一行,两个整数n、m。
输出
一行,一个整数,表示答案mod 10^9+7的值。
输入示例
5 3
输出示例
36363
其他说明
n<=10^9 m<=50

题解:矩阵乘法+变形+二项式定理:

COJ 2124 Day8-例1

 #include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
typedef long long LL;
const LL mod=;
const int maxn=+;
struct matx{
int h,w;LL x[maxn][maxn];matx(){memset(x,,sizeof(x));}
matx operator*(matx a){
matx b;b.h=h;b.w=a.w;
for(int k=;k<w;k++)
for(int i=;i<h;i++)
for(int j=;j<a.w;j++)b.x[i][j]=(b.x[i][j]+x[i][k]*a.x[k][j])%mod;return b;
}
void init(int h,int w){this->h=h;this->w=w;return;}
}A,B;
LL C[maxn][maxn];int n,m;
LL powi(LL x,LL y){
LL ans=;x%=mod;for(int i=y;i;i>>=,x=x*x%mod)if(i&)ans=ans*x%mod;return ans;
}
matx powm(matx a,int n){
matx ans=a,tmp=a;n--;for(int i=n;i;i>>=,tmp=tmp*tmp)if(i&)ans=ans*tmp;return ans;
}
LL inv(LL a){return powi(a,mod-);}
void initc(){
for(int i=;i<=m;i++)C[i][]=,C[i][i]=;
for(int i=;i<=m;i++)for(int j=;j<i;j++)C[i][j]=(C[i-][j]+C[i-][j-])%mod;return;
}
void initmatx(){
A.init(,m+);B.init(m+,m+);A.x[][]=;
for(int i=;i<=m;i++)for(int j=;j<=i;j++)B.x[j][i]=C[i][j];
for(int i=;i<=m;i++)B.x[i][m+]=C[m][i];
B.x[m+][m+]=inv(m);return;
}
inline int read(){
int x=,sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(long long x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=;long long buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int main(){
n=read();m=read();initc();initmatx();A=powm(B,n);
write((A.x[][m+]*powi(m,n))%mod);
return ;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,995
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,509
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,352
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,136
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,769
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,847