CodeForces 223C - Partial Sums 矩阵乘法..矩阵压缩...

CodeForces 223C - Partial Sums 矩阵乘法..矩阵压缩...

这道题有两种方法...组合数学和矩阵乘法..组合数学暂时还没看懂...矩阵乘法..练习赛时根本没往这方面想....囧..太水了...

大神的解析​​here​​

总结....以前做矩阵乘法做多是在通过地推关系构造矩阵时下功夫..而本题..矩阵构造相当直观..但是裸做会超时..这时需要观察矩阵的性质..当有对称相等之类的情况..可以想办法降阶...

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 2005using namespace std; ll N,K,a[MAXN],h[MAXN],b[MAXN],temp[MAXN]; void mul(ll *a ,ll *b){ int i,j; memset(temp,0,sizeof(temp)); for(i=1;i<=N;i++) for(j=1;j<=i;j++) temp[i]=(temp[i]+a[j]*b[i-j+1])%oo; for (i=1;i<=N;i++) a[i]=temp[i];}void getmtrix(){ int i; for (i=1;i<=N;i++) h[i]=1; memset(b,0,sizeof(b)); b[1]=1; for (i=0;i<30;i++) { if (K & (1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。