loj2253|loj2253 「SNOI2017」礼物
对于一个在位置 \(i\) 的数，他等于 \(i^k+sum_{1,k-1}\)。
二项式定理推 \(i^k\)，矩阵快速幂即可。
#include
#include
using namespace std;
typedef long long ll;
int k, c[15][15];
ll n;
const int mod=1e9+7;
struct Matrix{
int num[15][15];
Matrix operator*(const Matrix &x)const{
Matrix re;
for(int i=0;
i<=k+1;
i++)
for(int j=0;
j<=k+1;
j++){
re.num[i][j] = 0;
for(int l=0;
l<=k+1;
l++)
re.num[i][j] = (re.num[i][j] + (ll)num[i][l]*x.num[l][j]) % mod;
}
return re;
}
}yua, zhu, dan;
Matrix ksm(ll b){
while(b){
if(b&1) dan = dan * zhu;
zhu = zhu * zhu;
b >>= 1;
}
return dan;
}
int main(){
cin>>n>>k;
for(int i=0;
i<=k;
i++)
yua.num[0][i] = dan.num[i][i] = 1;
c[0][0] = zhu.num[k][k+1] = dan.num[k+1][k+1] = 1;
for(int i=1;
i<=k;
i++){
c[i][0] = 1;
for(int j=1;
j<=i;
j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
for(int i=0;
i<=k;
i++)
for(int j=i;
j<=k;
j++)
zhu.num[i][j] = c[j][i];
zhu.num[k+1][k+1] = 2;
Matrix ans=yua*ksm(n-1);
cout<<(ans.num[0][k+1]+ans.num[0][k])%mod< 【loj2253|loj2253 「SNOI2017」礼物】转载于:https://www.cnblogs.com/poorpool/p/8571759.html
推荐阅读
- 八、「料理风云」
- 「#1-颜龙武」区块链的价值是什么（）
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 「按键精灵安卓版」关于全分辨率脚本的一些理解（非游戏app）
- 「我的2017」——2017|「我的2017」——2017,大事件盘点
- 「适合发朋友圈的可爱短句文案」
- 「漫威之父」斯坦·李去世，回味老爷子在漫威中客串的各种角色
- 史前艺术的审美类型「清央美术」
- 「未来30年」你的孩子会成为社会精英吗（）
- 「日记」他乡，温暖的日子