AT2272 [ARC066B] Xor Sum 题解-白红宇

AT2272 [ARC066B] Xor Sum 题解

阅读量：452 次

发布时间：2019-03-06

本文共 642 字，大约阅读时间需要 2 分钟。

分析数列1, 2, 4, 5, 8, 10, 13, 14, 18时，我们发现难以直接看出明显的规律。于是，我们决定从OEIS上搜索这个数列，发现它对应于一个递推公式：

f(x) = f(x/2) + f((x-1)/2) + f((x-2)/2)

通过对递推式的分析和编写程序计算更多的数值，我们能够更深入地理解这个数列的生成规律。程序如下：

#include #include 
    
     using namespace std;ll solve(ll xx) {    if (xx <= 20) return a[xx];    if (ma[xx]) return ma[xx];    if (xx % 2) {        ma[xx] = (2 * solve(xx / 2) % mod + solve(xx / 2 - 1) % mod) % mod;    } else {        ma[xx] = (2 * solve(xx / 2 - 1) % mod + solve(xx / 2) % mod) % mod;    }    return ma[xx];}int main() {    ll n;    scanf("%lld", &n);    ll ans = solve(n);    printf("%lld\n", ans);    return 0;}

通过上述程序，我们可以计算出数列的后续项，并进一步分析其规律。

转载地址：http://plpyz.baihongyu.com/

你可能感兴趣的文章

Objective-C实现Interpolation search插值查找算法（附完整源码）

查看>>

Objective-C实现intersection交集算法(附完整源码)

查看>>

Objective-C实现intro sort内省排序算法(附完整源码)

查看>>

Objective-C实现inverse matrix逆矩阵算法(附完整源码)

查看>>

Objective-C实现inversions倒置算法(附完整源码)