team2012-F3-sol-0009

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
题意：给定一个函数f(x)的形式和 5000 多组[x, f(x)]的数据，求f(x)
解法：参照了学长们的报告后整理如下：
首先 g(x) 是存在反函数的，设 x 的最高位是第 31 位，最低位是第 0 位，那么 x ^ (x / 2) 的第31位与 x 的第31位相等(因为异或的是最高位补的0)，
在 x ^ (x / 2) 的第30位上存的是 x 的第 31 位异或 x 的第 30 位，那么知道了第 31 位和异或值就可以推出第 30 位，然后一直推到第 0 位
然后就可以变成：f'(x) = h2{ g[ h1(x) ] }
这样枚举 m1, s1，求 m2, s2，枚举之后进一步变成：f''(x) = x / m2 * m2 + (x + s2) % m2
其中第一项可以变成 x - x % m2，第二项可以变成 (x % m2 + s2 % m2) % m2，利用 s2 < m2，即 (x % m2 + s2) % m2
若 x % m2 + s2 < m2 时，化为f''(x) = x + s2 > x
若 x % m2 + s2 >= m2 时，化为f''(x) = x + s2 - m2 < x
那么对于每一组 [x, f''(x)] 的大小关系就可以确定出 m2, s2，然后测试看看是不是矛盾，矛盾的话就继续枚举。
}}}
{{{
#include <cstdio>
typedef long long LL;

const int s1 = 100007, m1 = 214748, s2 = 123123, m2 = 201263;

LL g(LL x)
{
    return x ^ (x >> 1);
}

LL h1(LL x)
{
    return x / m1 * m1 + (x + s1) % m1;
}

LL h2(LL x)
{
    return x / m2 * m2 + (x + s2) % m2;
}

LL f(LL x)
{
    return g(h2(g(h1(g(x)))));
}

int main()
{
    LL x;
    while(~scanf("%lld", &x))
        printf("%lld\n", f(x));
    return 0;
}
}}}

题意：给定一个函数f(x)的形式和 5000 多组[x, f(x)]的数据，求f(x)
解法：参照了学长们的报告后整理如下：
首先 g(x) 是存在反函数的，设 x 的最高位是第 31 位，最低位是第 0 位，那么 x ^ (x / 2) 的第31位与 x 的第31位相等(因为异或的是最高位补的0)，
在 x ^ (x / 2) 的第30位上存的是 x 的第 31 位异或 x 的第 30 位，那么知道了第 31 位和异或值就可以推出第 30 位，然后一直推到第 0 位
然后就可以变成：f'(x) = h2{ g[ h1(x) ] }
这样枚举 m1, s1，求 m2, s2，枚举之后进一步变成：f''(x) = x / m2 * m2 + (x + s2) % m2
其中第一项可以变成 x - x % m2，第二项可以变成 (x % m2 + s2 % m2) % m2，利用 s2 < m2，即 (x % m2 + s2) % m2
若 x % m2 + s2 < m2 时，化为f''(x) = x + s2 > x
若 x % m2 + s2 >= m2 时，化为f''(x) = x + s2 - m2 < x
那么对于每一组 [x, f''(x)] 的大小关系就可以确定出 m2, s2，然后测试看看是不是矛盾，矛盾的话就继续枚举。

#include <cstdio>
typedef long long LL;
const int s1 = 100007, m1 = 214748, s2 = 123123, m2 = 201263;
LL g(LL x)
{
    return x ^ (x >> 1);
}
LL h1(LL x)
{
    return x / m1 * m1 + (x + s1) % m1;
}
LL h2(LL x)
{
    return x / m2 * m2 + (x + s2) % m2;
}
LL f(LL x)
{
    return g(h2(g(h1(g(x)))));
}
int main()
{
    LL x;
    while(~scanf("%lld", &x))
        printf("%lld\n", f(x));
    return 0;
}