51dev.com IT技术开发者社区

51dev.com 技术开发者社区

非负矩阵分解

非负矩阵分解(NMF)原理及算法实现

非负矩阵分解(NMF)原理及算法实现

一、矩阵分解回想矩阵分解是指将一个矩阵分解成两个或者多个矩阵的乘积。对于上述的用户-商品(评分矩阵),记为能够将其分解为两个或者多个矩阵的乘积,如果分解成两个矩阵和 。我们要使得矩阵和 的乘积能够还原原始的矩阵当中,矩阵表示的是m个用户于k个主题之间的关系,而矩阵表示的是k个主题与n个商品之间的关系...

UOJ#299. 【CTSC2017】游戏 线段树 概率期望 矩阵

UOJ#299. 【CTSC2017】游戏 线段树 概率期望 矩阵

原文链接www.cnblogs.com/zhouzhendong/p/UOJ299.html不会概率题的菜鸡博主做了一道概率题。写完发现运行效率榜上的人都没有用心卡常数——矩阵怎么可以用数组呢?矩乘怎么可以用循环呢?截止2019-05-15暂居运行效率榜一。首先,根据期望的线性性,容易得知,总期...

UOJ#75. 【UR #6】智商锁  随机化算法 矩阵树定理

UOJ#75. 【UR #6】智商锁 随机化算法 矩阵树定理

原文链接www.cnblogs.com/zhouzhendong/p/UOJ75.html根本没想到。首先我们可以考虑一种做法:找一些图,使得他们各自的生成树个数乘起来等于k。那么只要将他们用一条链连起来就得到答案了。接下来考虑如何得到这些图。 考虑随机生成一个n个点的图,它的生成树个数最大是$n^{n-2}...

UOJ#424. 【集训队作业2018】count  多项式,FFT,矩阵

UOJ#424. 【集训队作业2018】count 多项式,FFT,矩阵

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ424.html主席太神仙了!首先我们把题意转化成:对所有挺好序列建笛卡尔树,有多少笛卡尔树互不同构。容易推出dp式子:$f[i][j]$表示$j$个数,他们的max为i。$$f[i][j]=sum_{k=0}^{j-1}f[i...

UOJ#41. 【清华集训2014】矩阵变换  构造

UOJ#41. 【清华集训2014】矩阵变换 构造

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ41.html首先写个乱搞:一开始每一行都选择第一个非0元素,然后,我们对这个方案不断做更新,直到任意两行选择的值不同。更新方法:如果有两行选了相同的值,那么让靠前的那行选择后一个非0的值。交上去。过了。wtf?然后发现证明这个...

矩阵的旋转

矩阵的旋转

一,给定一个矩阵,用二维数组表示,不一定是方阵(N*N),求矩阵的转置(向右),和向左转置。比如:123456789向右转置:147258369 再比如:123456向左转置362514 二,实现思路假设原来的矩阵是M*N,转置后变成了N*M。设原矩阵是arr[M][N],创建一个新的矩阵rev[N...

BZOJ3583 杰杰的女性朋友 矩阵

BZOJ3583 杰杰的女性朋友 矩阵

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ3583.html  有一个$n$个点构成的有向图。  对于每一个点$i$,给定两组参数,每组参数分别有$k$个值。这两组参数分别记做:$in[i][1cdotsk],out[i][1cdotsk]$。  从点$i$连到点$j...

51Nod1626 B君的梦境 状压dp 矩阵

51Nod1626 B君的梦境 状压dp 矩阵

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1626.html   首先考虑形象的想象本题中的思维空间。我们把整个2*2*3*n的四维空间看作n个2*2*3的三维空间顺次排列。考虑到1*1*1*2的方块,我们如果把边长2放在第4维上,相当于是填充了连续两个三...

Codeforces 177G2 Fibonacci Strings KMP 矩阵

Codeforces 177G2 Fibonacci Strings KMP 矩阵

原文链接https://www.cnblogs.com/zhouzhendong/p/CF117G2.html  定义斐波那契字符串如下:  $s_1="a"$  $s_2="b"$  $s_i=s_{i-1}+s_{i-2}(igeq3)$  给定$k,m$,以及对应的$m$组询问。  每组询问一个字符串$x$,问$...

BZOJ2553 [BeiJing2011]禁忌 AC自动机 矩阵

BZOJ2553 [BeiJing2011]禁忌 AC自动机 矩阵

原文链接http://www.cnblogs.com/zhouzhendong/p/8196279.html  引用一下lych大佬的:  在字母只有前alphabet时,给定N个串,求长度为len的串包含这些N个串的个数最大值的期望值。  我们首先发现总共的字符个数才就75个,那么闭着眼睛先建一个AC自动机,Trie...

BZOJ3240 [Noi2013]矩阵游戏 矩阵 快速幂 卡常

BZOJ3240 [Noi2013]矩阵游戏 矩阵 快速幂 卡常

原文链接http://www.cnblogs.com/zhouzhendong/p/8084891.html  F[1][1]=1F[i,j]=a*F[i][j-1]+b(j!=1)F[i,1]=c*F[i-1][m]+d(i!=1)递推式中a,b,c,d都是给定的常数。求F[n][m]1<=...

BZOJ3286 Fibonacci矩阵 矩阵 快速幂 卡常

BZOJ3286 Fibonacci矩阵 矩阵 快速幂 卡常

n,m,a,b,c,d,e,f<=10^1000000   神奇的卡常题目。  在此感谢"zhouzixuan"——bzoj3286:Fibonacci矩阵  学习他,才15秒卡过此题。  这题的做法应该很明显的,学过矩阵快速幂的大概几眼就看出来了。  对于每一行的转移,是相同的...

HDU4686 Arc of Dream 矩阵

HDU4686 Arc of Dream 矩阵

    a0=A0  ai=ai-1*AX+AY  b0=B0  bi=bi-1*BX+BY  求AoD(n)  n=0时答案为0!!!!  具体的矩阵构建思路指导可以参考例题链接。  这里仅提供运算过程。  Ai=Ai-1*AX+AY  Bi=Bi-1*BX+BY  AiBi=(Ai-1*AX+AY)(Bi-1*BX...

HDU3306 Another kind of Fibonacci 矩阵

HDU3306 Another kind of Fibonacci 矩阵

  A0=1,A1=1,AN=X*AN-1+Y*AN-2(N>=2).求SN,SN=A02+A12+…+An2.  这题是用矩阵做的,一看(sou)就知道。  设si为前i项的答案。  如果要求第i项的ai那么是很简单的。  构建矩阵:      ai-1    &nb...

POJ2778 DNA Sequence AC自动机 矩阵

POJ2778 DNA Sequence AC自动机 矩阵

  现在有一个长度为n(n<=2000000000)的DNA串,其中只可能有A、C、G、T四种字母。现在给出m(m<=10)个危险串(len<=10),求有几种可行的安全串。最终的答案mod100000。  我们先按照输入的危险串构建AC自动机。  对于当前串在AC自动机上的某一个状态k,我们接下来填...