4547: Hdu5171 小奇的集合 Time Limit: 2 Sec Memory Limit: 256 MB Submit: 263 Solved: 113 [Submit][Status][Discuss] Description  有一个大小为n的可重集S，小奇每次操作可以加入一个数a+b(a,b均属于S)，求k次操作后它可获得的S的和的最大 值。（数据保证这个值为非负数） Input 第一行有两个整数n,k表示初始元素数量和操作数，第二行包含n个整数表示初始时可重集的元素。 对于100%的数据，有 n<=10^5，k<=10^9，|ai|<=10^5 Output 输出一个整数，表示和的最大值。答案 …

题目链接 题意：给出n,k，以及n个正数，把n个数放在一个集合里，进行k次操作，每次操作取最大的数和次大的数放进集合。问k次操作结束后，集合中所有数的和。 思路：假设初始时刻，次大和最大分别为a0,a1，那么得到的就是一个类斐波那契数列。初始为a0,a1,fn = fn-1 + fn 最后求和。 利用这个性质。。。 我们直接构造完矩阵。。。求出F(n+2)即可。。 需要注意。。。矩阵中每一项是小于1E7+7的。。。矩乘的时候会爆int... 所以mat要用LL存。。我好傻啊。。。 /* *********************************************** Author :111qqz Created …

题目链接 题意：Step 1: Calculate a new NN matrix C = AB. Step 2: Calculate M = C^(N*N). Step 3: For each element x in M, calculate x % 6. All the remainders form a new matrix M’. Step 4: Calculate the sum of all the elements in M’. 思路： 水题。。就一个trick... 朴素的矩阵乘法的复杂度是n^3的。。。按照题目的顺序求的话。。。。求M矩阵时会超时。。。（而且1000*1000的数组也不能放到结构体里...? 我们 …

题意：给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值 思路： ** 把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，CA的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要快速幂求出A^k即可。** M67_十个利用矩阵乘法解决的经典题目 这个转化好美啊。。。 /* *********************************************** Author :111qqz …

题目链接 题意：给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1) 给出l个c,计算m = D(c) = c**d** mod n,其中m为要输入的明文对应的ascii编码，d的计算方法：> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key。 问明文。 思路： 出题人JGShining（极光炫影）傻逼。 题意都说不清？ 大小写字母一个意思？ 脑袋有坑的出题人。 出题人傻逼。 出题人傻逼。 出题人傻逼。 好了。这道题需要用到扩展欧几里得算法求逆元。。。ksm(a,mod-2)的方法是基于 …

acdreamer_逆元学习笔记 摘重点： ksm(a,mod-2)的方法求逆元只适用于mod为质数且 gcd(a,mod)==1 扩展欧几里得算法求逆元只适用于gcd(a,mod)==1 扩展欧几里得算法求逆元 acdreamer的博客里提到一种通用的方法，正确性未知。（然而有b|a的前提呵呵呵呵呵） 但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求 与 互素。实际上我们还有一 种通用的求逆元方法，适合所有情况。 …

题目链接 题意： Given a n × n matrix A and a positive integer k, find the sum S = A + _A_2 + _A_3 + … + Ak. 思路： 对k进行二分。 比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。 以及错误的递归方式： 无形中增加了多少次。。。。。。怎么像小学生呢。。。 正确的写法。。。 /* …

(\alpha+\beta\geq\frac12) 20180101_test: (\alpha+\beta\geq\frac12) $$\left[ \begin{matrix}a&b\c&\alpha\end{matrix} \right]$$ \left( \begin{matrix}a&b\c&\alpha\end{matrix} \right)

题目链接 题意：求f[n] % 10000,f为斐波那契数。 思路：按照题目给出的公式，或者按照加速线性递推式的方法都可以。。。 因为把模数的1E4手滑写成1E4+7结果调了半天也是没谁了呵呵呵呵。 /* *********************************************** Author :111qqz Created Time :Tue 18 Oct 2016 01:18:40 AM CST File Name :code/poj/3070.cpp ************************************************ */ #include <cstdio> …

找到了篇四年前空间中的旧文，也是有点感动2333. 快速求解多项递推式 问题描述: 已知 F(n) = AF(n-1) + BF(n-2) + CF(n-3)+..... 求解 F(n)%P 分析: ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 如果n的值不大,一般来说在1000000之内,则可以考虑直接递推求解,只要预先花O(n)时间复杂度,可打出一张表,运行时直接查表就可以了. 另一方面,如果n值可能很大,如10^9,用这种方法无论是在内存还是时间上开销都太大,根本无法满足.本文将介绍一种与矩阵相关的高效通用算法. 举个例子: …