871. Drifting Subsets

Let $f$$f$ be a function from a finite set $S$$S$ to itself. A drifting subset for $f$$f$ is a subset $A$$A$ of $S$$S$ such that the number of elements in the union $A\cup f(A)$$A \cup f(A)$ is equal to twice the number of elements of $A$$A$.
We write $D(f)$$D(f)$ for the maximal number of elements among all drifting subsets for $f$$f$.

For a positive integer $n$$n$, define $f_n$$f_n$ as the function from $\{0,1,\dots ,n-1\}$$\{0, 1, \dots, n - 1\}$ to itself sending $x$$x$ to $x^3+x+1modn$$x^3 + x + 1 \bmod n$.
You are given $D(f_5)=1$$D(f_5) = 1$ and $D(f_{10})=3$$D(f_{10}) = 3$.

Find ${\displaystyle \sum _{i=1}^{100}D(f_{{10}^5+i})}$$\displaystyle\sum_{i = 1}^{100} D(f_{10^5 + i})$.

871. 漂移子集

记 $f$$f$ 为某从有限集合 $S$$S$ 到 $S$$S$ 的一个函数。若 $S$$S$ 的一个子集 $A$$A$ 满足：$A\cup f(A)$$A \cup f(A)$ 的元素个数是 $A$$A$ 的元素个数的 $2$$2$ 倍，则称 $A$$A$ 是 $f$$f$ 的一个 漂移子集。记 $D(f)$$D(f)$ 为：所有 $f$$f$ 的漂移子集中，元素个数的最大值。

对某正整数 $n$$n$，记 $f_n$$f_n$ 为 $\{0,1,\dots ,n-1\}$$\{0, 1, \dots, n - 1\}$ 上的函数，满足 $f(x)=(x^3+x+1)modn$$f(x) = (x^3 + x + 1) \bmod n$。 已知：$D(f_5)=1$$D(f_5) = 1$、$D(f_{10})=3$$D(f_{10}) = 3$。

求 ${\displaystyle \sum _{i=1}^{100}D(f_{{10}^5+i})}$$\displaystyle\sum_{i = 1}^{100} D(f_{10^5 + i})$。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。