hexo-blog/source/_posts/oi/funny-strings.md

---

title: Funny Strings tags:

• Constructive Algorithm
• Implementation
• Multiplicative Inverse id: "1605" categories:
• [OI, Common Skill]
• [OI, Number Theory] date: 2017-10-29 11:35:59 ---

题目描述

Let's consider a string of non-negative integers, containing $N$ elements. Suppose these elements are $S_1, S_2, \ldots, S_N$, in the order in which they are placed inside the string. Such a string is called 'funny' if the string $S_1+1, S_2, S3, \ldots, S{N-1}, S_N-1$ can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings $2, 2, 2, 3$ and $1, 2, 1, 2, 2$ are funny, but the string $1, 2, 1, 2$ is not. Your task is to find a funny string having $N$ elements, for which the sum of its elements $S_1+S_2+ \cdots +S_N$ is equal to $K$.

题意概述

定义序列的旋转操作为将序列的最后一个元素移到最前面，定义两个序列等价当且仅当可以通过若干次旋转操作使它们相同，定义一个序列是 funny 的当且仅当将它的第一个元素加一、最后一个元素减一后得到的序列和原序列等价。要求构造一个长度为$N$、元素之和为$K$的 funny 序列（所有元素均为非负整数）。

数据范围：$2 \le N \le 1000, \; 1 \le K \le 30000, \; (N, K)=1$。

算法分析

我们只考虑$1 \le K \le N$的情况，因为其他情况都可以通过把所有数减去同一个数得到这种情况。 显然，第一个数一定比最后一个数小$1$，否则新序列和原序列中某些数字出现的次数不同。假设我们有新旧序列如下：

0_______1（旧）

1_______0（新）

新旧序列中空位上的数字是一样的。这意味着我们只要知道了旋转次数，就可以构造出序列。假设旋转次数是$a$，那么第$i$位的数就旋转到了第$((i+a-1)\%N+1)$位。下面模拟$N=9, a=7$的构造过程：

第$8$位

0______11

1______10

第$6$位

0____1_11

1____1_10

第$4$位

0__1_1_11

1__1_1_10

第$2$位

01_1_1_11

11_1_1_10

第$9$位，构造完成

010101011

110101010

由于元素之和为$K$，因此序列中有$K$个$1$，也就是说，从第$1$位开始，模拟$K$次，到达第$N$位。那么$N-1 \equiv K \times a \pmod N$，$a \equiv (N-1) \times K^{-1} \pmod N$。因为$(N, K)=1$，所以$a$一定存在，接下来只要模拟即可。当然也可以用暴力求出$a$。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 1010;
  int n, k, a[N];
  void input() { io > n > k; }
  void init() {
    int t = k / n;
    for (int i = 1; i <= n; ++ i) a[i] = t, k -= t;
  }
  void process() {
    int sum = n - 1;
    while (sum % k) sum += n;
    int p = sum / k + 1;
    for (; p < n; p = (p - 1 + sum / k) % n + 1) ++ a[p]; ++ a[n];
    for (int i = 1; i <= n; ++ i) io < a[i] < ' ';
    io < '\n';
  }

public:
  void solve() { input(), init(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}