【BZOJ4870】组合数问题(动态规划,矩阵快速幂)
规划 快速 动态 矩阵 组合 问题
2023-09-11 14:14:41 时间
【BZOJ4870】组合数问题(动态规划,矩阵快速幂)
题面
题解
显然直接算是没法做的。但是要求的东西的和就是从\(nk\)个物品中选出模\(k\)意义下恰好\(r\)个物品的方案数。\(n\)的范围这么大,往快速幂的方面靠。设\(f[i][j]\)表示从前\(i\)个物品中选了模\(k\)意义下\(j\)个物品的方案数,转移显然,快速幂即可。
时间复杂度\(O(k^3logn)\)。
稍微注意一个细节,\(k=1\)的时候,矩阵的唯一一项不是\(1\),而是\(2\)。所以在构造矩阵的时候不要直接赋值,要加上去。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define ll long long
int n,MOD,K,r;
struct Matrix
{
int s[55][55];
void clear(){memset(s,0,sizeof(s));}
void init(){clear();for(int i=0;i<K;++i)s[i][i]=1;}
int*operator[](int x){return s[x];}
}A;
Matrix operator*(Matrix a,Matrix b)
{
Matrix ret;ret.clear();
for(int i=0;i<K;++i)
for(int j=0;j<K;++j)
for(int k=0;k<K;++k)
ret[i][j]=(ret[i][j]+1ll*a[i][k]*b[k][j])%MOD;
return ret;
}
Matrix fpow(Matrix a,ll b)
{
Matrix s;s.init();
while(b){if(b&1)s=s*a;a=a*a;b>>=1;}
return s;
}
int main()
{
scanf("%d%d%d%d",&n,&MOD,&K,&r);
A.init();A[K-1][0]+=1;
for(int i=1;i<K;++i)A[i-1][i]+=1;
A=fpow(A,1ll*K*n);
printf("%d\n",A[0][r]);
return 0;
}
相关文章
- 【BZOJ4000】[TJOI2015]棋盘(矩阵快速幂,动态规划)
- 【CF1151F】Sonya and Informatics(动态规划,矩阵快速幂)
- 【BZOJ5298】[CQOI2018]交错序列(动态规划,矩阵快速幂)
- 【UOJ#340】【清华集训2017】小 Y 和恐怖的奴隶主(矩阵快速幂,动态规划)
- 【BZOJ1898】[ZJOI2005]沼泽鳄鱼(矩阵快速幂,动态规划)
- 【BZOJ4361】isn(动态规划,容斥)
- 【BZOJ2004】公交线路(动态规划,状态压缩,矩阵快速幂)
- 【Luogu1273】有线电视网(动态规划)
- 基于SLAM算法的路径规划算法
- 《网站情感化设计与内容策略》一10.6 规划内容管理
- [计蒜客][动态规划]蒜头君爬楼梯
- 170、【动态规划】leetcode ——188. 买卖股票的最佳时机 IV:二维数组+一维数组 (C++版本)
- 软件测试流程规划
- Python实现采药问题(+动态规划简单概述)