- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
问题需要生成一个类似于斐波那契数列的序列的第 n-th
元素。但是,这有点棘手,因为 n
非常大(1 <= n <= 10^9)。答案然后模1000000007。序列定义如下:
使用生成函数,我得到以下公式:
如果我使用序列方法,那么答案可以是模数,但运行速度非常慢。事实上,我多次得到time limit exceeded
。我还尝试使用表来预生成一些初始值(缓存),但速度仍然不够快。另外,array/vector
(C++) 中可以存储的最大元素数量与 10^9 相比太小了,所以我猜这种方法也行不通。
如果我使用直接公式,那么它的运行速度非常快,但仅适用于较小的 n
。对于 n
大,double 将被截断,而且我将无法使用该数字修改我的答案,因为 modulo 仅适用于整数。
我没有想法,我认为必须有一个非常好的技巧来解决这个问题,不幸的是我想不出一个。任何想法将不胜感激。
这是我最初的方法:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <set>
#include <stack>
#include <sstream>
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
ull count_fair_coins_by_generating_function(ull n) {
n--;
return
(sqrt(3.0) + 1)/((sqrt(3.0) - 1) * 2 * sqrt(3.0)) * pow(2 / (sqrt(3.0) - 1), n * 1.0)
+
(1 - sqrt(3.0))/((sqrt(3.0) + 1) * 2 * sqrt(3.0)) * pow(-2 / (sqrt(3.0) + 1), n * 1.0);
}
ull count_fair_coins(ull n) {
if (n == 1) {
return 1;
}
else if (n == 2) {
return 3;
}
else {
ull a1 = 1;
ull a2 = 3;
ull result;
for (ull i = 3; i <= n; ++i) {
result = (2*a2 + 2*a1) % 1000000007;
a1 = a2;
a2 = result;
}
return result;
}
}
void inout_my_fair_coins() {
int test_cases;
cin >> test_cases;
map<ull, ull> cache;
ull n;
while (test_cases--) {
cin >> n;
cout << count_fair_coins_by_generating_function(n) << endl;
cout << count_fair_coins(n) << endl;
}
}
int main() {
inout_my_fair_coins();
return 0;
}
更新比赛结束后,我将基于 tskuzzy
想法的解决方案发布给感兴趣的人。再次感谢 tskuzzy
。您可以在此处查看原始问题陈述: http://www.codechef.com/problems/CSUMD
首先需要算出1个硬币
和2个硬币
的概率,然后得到一些初始值得到序列。完整的解决方案在这里:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <set>
#include <stack>
#include <sstream>
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
const ull special_prime = 1000000007;
/*
Using generating function for the recurrence:
| 1 if n = 1
a_n = | 3 if n = 2
| 2a_{n-1} + 2a_{n-2} if n > 2
This method is probably the fastest one but it won't work
because when n is large, double just can't afford it. Plus,
using this formula, we can't apply mod for floating point number.
1 <= n <= 21
*/
ull count_fair_coins_by_generating_function(ull n) {
n--;
return
(sqrt(3.0) + 1)/((sqrt(3.0) - 1) * 2 * sqrt(3.0)) * pow(2 / (sqrt(3.0) - 1), n * 1.0)
+
(1 - sqrt(3.0))/((sqrt(3.0) + 1) * 2 * sqrt(3.0)) * pow(-2 / (sqrt(3.0) + 1), n * 1.0);
}
/*
Naive approach, it works but very slow.
Useful for testing.
*/
ull count_fair_coins(ull n) {
if (n == 1) {
return 1;
}
else if (n == 2) {
return 3;
}
else {
ull a1 = 1;
ull a2 = 3;
ull result;
for (ull i = 3; i <= n; ++i) {
result = (2*a2 + 2*a1) % 1000000007;
a1 = a2;
a2 = result;
}
return result;
}
}
struct matrix_2_by_2 {
ull m[2][2];
ull a[2][2];
ull b[2][2];
explicit matrix_2_by_2(ull a00, ull a01, ull a10, ull a11) {
m[0][0] = a00;
m[0][1] = a01;
m[1][0] = a10;
m[1][1] = a11;
}
matrix_2_by_2 operator *(const matrix_2_by_2& rhs) const {
matrix_2_by_2 result(0, 0, 0, 0);
result.m[0][0] = (m[0][0] * rhs.m[0][0]) + (m[0][1] * rhs.m[1][0]);
result.m[0][1] = (m[0][0] * rhs.m[0][1]) + (m[0][1] * rhs.m[1][1]);
result.m[1][0] = (m[1][0] * rhs.m[0][0]) + (m[1][1] * rhs.m[1][0]);
result.m[1][1] = (m[1][0] * rhs.m[0][1]) + (m[1][1] * rhs.m[1][1]);
return result;
}
void square() {
a[0][0] = b[0][0] = m[0][0];
a[0][1] = b[0][1] = m[0][1];
a[1][0] = b[1][0] = m[1][0];
a[1][1] = b[1][1] = m[1][1];
m[0][0] = (a[0][0] * b[0][0]) + (a[0][1] * b[1][0]);
m[0][1] = (a[0][0] * b[0][1]) + (a[0][1] * b[1][1]);
m[1][0] = (a[1][0] * b[0][0]) + (a[1][1] * b[1][0]);
m[1][1] = (a[1][0] * b[0][1]) + (a[1][1] * b[1][1]);
}
void mod(ull n) {
m[0][0] %= n;
m[0][1] %= n;
m[1][0] %= n;
m[1][1] %= n;
}
/*
exponentiation by squaring algorithm
| 1 if n = 0
| (1/x)^n if n < 0
x^n = | x.x^({(n-1)/2})^2 if n is odd
| (x^{n/2})^2 if n is even
The following algorithm calculate a^p % m
int modulo(int a, int p, int m){
long long x = 1;
long long y = a;
while (p > 0) {
if (p % 2 == 1){
x = (x * y) % m;
}
// squaring the base
y = (y * y) % m;
p /= 2;
}
return x % c;
}
To apply for matrix, we need an identity which is
equivalent to 1, then perform multiplication for matrix
in similar manner. Thus the algorithm is defined
as follows:
*/
void operator ^=(ull p) {
matrix_2_by_2 identity(1, 0, 0, 1);
while (p > 0) {
if (p % 2) {
identity = operator*(identity);
identity.mod(special_prime);
}
this->square();
this->mod(special_prime);
p /= 2;
}
m[0][0] = identity.m[0][0];
m[0][1] = identity.m[0][1];
m[1][0] = identity.m[1][0];
m[1][1] = identity.m[1][1];
}
friend
ostream& operator <<(ostream& out, const matrix_2_by_2& rhs) {
out << rhs.m[0][0] << ' ' << rhs.m[0][1] << '\n';
out << rhs.m[1][0] << ' ' << rhs.m[1][1] << '\n';
return out;
}
};
/*
|a_{n+2}| = |2 2|^n x |3|
|a_{n+1}| |1 0| |1|
*/
ull count_fair_coins_by_matrix(ull n) {
if (n == 1) {
return 1;
} else {
matrix_2_by_2 m(2, 2, 1, 0);
m ^= (n - 1);
return (m.m[1][0] * 3 + m.m[1][1]) % 1000000007;
}
}
void inout_my_fair_coins() {
int test_cases;
scanf("%d", &test_cases);
ull n;
while (test_cases--) {
scanf("%llu", &n);
printf("%d\n", count_fair_coins_by_matrix(n));
}
}
int main() {
inout_my_fair_coins();
return 0;
}
最佳答案
你可以用矩阵指数的形式写出序列的项:
可以使用 exponentiation by squaring 快速评估.这导致 O(log n)
解决方案应该在时间限制内很好地解决问题。
仅供引用,如果您需要与大数进行乘法运算(在这种情况下不适用,因为答案取模 1000000007),您应该查看 Karatsuba algorithm .这为您提供了二次时间乘法。
关于c++ - 如何加快系列生成?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11381277/
我正在尝试使用以下 keytool 命令为我的应用程序生成 keystore : keytool -genkey -alias tomcat -keystore tomcat.keystore -ke
编辑:在西里尔正确解决问题后,我注意到只需将生成轴的函数放在用于生成标签的函数下面就可以解决问题。 我几乎读完了 O'Reilly 书中关于 D3.js 的教程,并在倒数第二页上制作了散点图,但是当添
虽然使用 GraphiQL 效果很好,但我的老板要求我实现一个用户界面,用户可以在其中通过 UI 元素(例如复选框、映射关系)检查呈现给他们的元素并获取数据,这样做将为该人生成 graphql 输入,
我尝试在 Netbean 6.8 中使用 ws-import 生成 Java 类。我想重新生成 jax-ws,因为在 ebay.api.paypalapi 包中发现了一个错误(我认为该错误是由于 Pa
我有一个 perl 脚本,它获取系统日期并将该日期写入文件名。 系统日期被分配给 TRH1 变量,然后它被设置为一个文件名。 $TRH1 =`date + %Y%m%d%H%M`; print "TR
我是 Haskell 的新手,需要帮助。我正在尝试构建一种必须具有某种唯一性的新数据类型,因此我决定使用 UUID 作为唯一标识符: data MyType = MyType { uuid ::
我制作了一个脚本,它可以根据 Mysql 数据库中的一些表生成 XML。 该脚本在 PHP 中运行。 public function getRawMaterials($apiKey, $format
所以这是我的项目中的一个问题。 In this task, we will use OpenSSL to generate digital signatures. Please prepare a f
我在 SAS LIFEREG 中有一个加速故障时间模型,我想绘制它。因为 SAS 在绘图方面非常糟糕,我想实际重新生成 R 中曲线的数据并将它们绘制在那里。 SAS 提出了一个尺度(在指数分布固定为
我正在为 Django 后端制作一个样板,并且我需要能够使它到达下一个下载它的人显然无法访问我的 secret key 的地方,或者拥有不同的 key 。我一直在研究一些选项,并在这个过程中进行了实验
我正在创建一个生成采购订单的应用程序。我可以根据用户输入的详细信息创建文本文件。我想生成一个看起来比普通文本文件好得多的 Excel。有没有可以在我的应用程序中使用的开源库? 最佳答案 目前还没有任何
我正在尝试使用 ScalaCheck 为 BST 创建一个 Gen,但是当我调用 .sample 方法时,它给了我 java.lang.NullPointerException。我哪里错了? seal
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我尝试编写一些代码,例如(在verilog中): parameter N = 128; if (encoder_in[0] == 1) begin 23 binary_out = 1;
我正忙于在 Grails 项目中进行从 MySQL 到 Postgres 的相当复杂的数据迁移。 我正在使用 GORM 在 PostGres 中生成模式,然后执行 MySQL -> mysqldump
如何使用纯 XSLT 生成 UUID?基本上是寻找一种使用 XSLT 创建独特序列的方法。该序列可以是任意长度。 我正在使用 XSLT 2.0。 最佳答案 这是一个good example 。基本上,
我尝试安装.app文件,但是当我安装并单击“同步”(在iTunes中)时,我开始在设备上开始安装,然后停止,这是一个问题,我不知道在哪里,但我看到了我无法解决的奇怪的事情: 最佳答案 似乎您没有在Xc
自从我生成 JavaDocs 以来已经有一段时间了,我确信这些选项在过去 10 年左右的时间里已经得到了改进。 我能否得到一些有关生成器的建议,该生成器将输出类似于 .Net 文档结构的 JavaDo
我想学习如何生成 PDF,我不想使用任何第三方工具,我想自己用代码创建它。到目前为止,我所看到的唯一示例是我通过在第 3 方 dll 上打开反射器查看的代码,以查看发生了什么。不幸的是,到目前为止我看
我正在从 Epplus 库生成 excel 条形图。 这是我成功生成的。 我的 table 是这样的 Mumbai Delhi Financial D
我是一名优秀的程序员,十分优秀!