【每日算法Day 95】美团笔试题：四面体方案个数

【每日算法Day 95】美团笔试题：四面体方案个数

今天就更新一道刚做的美团在线编程题吧。

代码

c++

#include using namespace std;typedef long long ll;const int mod = 1e9 + 7;const int N = 1000010;ll dp[N][2];int main() { int k; scanf("%d", &k); memset(dp, 0, sizeof dp); dp[0][0] = 1; for (int i = 1; i <= k; ++i) { dp[i][0] = (dp[i-1][1] * 3) % mod; dp[i][1] = (dp[i-1][1] * 2 + dp[i-1][0]) % mod; } printf("%lld\n", dp[k][0]); return 0;}

空间优化（c++）

#include using namespace std;typedef long long ll;const int mod = 1e9 + 7;const int N = 1000010;ll dp[2];int main() { int k; scanf("%d", &k); dp[0] = 1; dp[1] = 0; for (int i = 1; i <= k; ++i) { int a = (dp[1] * 3) % mod; int b = (dp[1] * 2 + dp[0]) % mod; dp[0] = a; dp[1] = b; } printf("%lld\n", dp[0]); return 0;}

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