题解：AT_arc129_c [ARC129C] Multiple of 7

· · 题解

题目大意

给定一个整数 N（1 \le N \le 10^6），需要构造一个仅由数字 1 到 9 组成的字符串 s，长度不超过 10^6，使得满足以下条件的区间 (l, r) 的个数恰好为 N：

题目保证一定有解。

分析

转化思路：子串整除 7 \Leftrightarrow 后缀模值相等

假设一个合法构造的字符串为 a_1 a_2 \dots a_L（每个 a_i \in \{1,\dots,9\}）。定义后缀数字：

S_i = \overline{a_i a_{i+1} \dots a_L} \quad (\text{十进制})

及其模 7 的余数：

s_i = S_i \bmod 7,\qquad s_{L+1} = 0\ (\text{空串})

区间 [l, r] 对应的数字为：

\operatorname{num}(l,r) = \frac{S_l - S_{r+1}}{10^{L-r}}

由于 10 与 7 互质，该数能被 7 整除当且仅当（也就是说我们可以不考虑 10 的影响）：

S_l \equiv S_{r+1} \pmod 7 \quad\Longleftrightarrow\quad s_l = s_{r+1}

因此问题转化为：构造一个长度为 L+1 的序列 s[1..L+1]（s_{L+1}=0），使得满足 1 \le l \le r \le L 且 s_l = s_{r+1} 的整数对 (l,r) 的个数恰好为 N。

统计思路

假设某个余数值 v 在序列中出现了 c 次，那么从这些位置中任选两个不同的位置都能贡献一个合法区间，数量为：

\binom{c}{2} = \frac{c(c-1)}{2}

所有不同余数贡献的区间数之和即为总合法区间数：

\sum_{v} \binom{c_v}{2} = N

于是，问题进一步转化为：将 N 拆分成若干个组合数 \binom{c}{2} 的和，使得总元素个数 L = \sum c 尽可能小（不超过 10^6）。

构造方法

我们该如何构造 s 数组。

贪心拆分

为了使总长度尽可能短，每次应选取尽可能大的 c，使得 \binom{c}{2} \le N，然后从 N 中减去 \binom{c}{2}，重复此过程直到 N=0。将每次选择的 c 记录下来，作为一段的长度。

贪心一定有效， 因为组合数 \binom{c}{2} 增长较快，优先选大段可以用更少的元素贡献更多的对数。实际上，对于 N \le 10^6，段数最多只有 3\sim 4 段，远小于余数种类数 7。

例：

填充模值

得到各段长度后，我们构造序列 s[0..L-1]（下标从 0 开始，最后补一个 s[L]=0）。
为了让同一段内的元素具有相同的余数值（从而使该段内任意两个位置产生 \binom{c}{2} 个区间），并且不同段之间不产生额外区间，必须给不同段分配互不相同的余数值。

由于段数 \le 6，我们可以使用 1,2,3,4,5,6 这些非零余数分配（代码中从 1 开始，每段递增 1，打表容易发现分配的数字小于 7 即可满足构造）。

最后在末尾补上 s[L]=0。

还原数字串 a

得到后缀模值序列 s 后，我们需要还原出每一位的数字 a_i。递推关系为（注意数字串长度为 L，下标从 0 开始）：

s[i] \equiv s[i+1] + a[i] \times 10^{L-1-i} \pmod 7 \qquad (0 \le i < L)

移项：

a[i] \times 10^{L-1-i} \equiv s[i] - s[i+1] \pmod 7

设 t = (s[i] - s[i+1]) \bmod 7。我们需要解出 a[i] \in \{0,\dots,6\}（若为 0 则映射为 7，因为数字只能是 1\sim 9，而 7 \equiv 0 \pmod 7）。

利用乘法逆元：

在模 7 下，10 \equiv 3，3 的逆元是 5（因为 3 \times 5 = 15 \equiv 1），所以 10^k 的逆元是 5^k。于是：

a[i] \equiv t \times 5^{L-1-i} \pmod 7

代码实现

由于只有 7 种可能，我们可以直接枚举 d = 0 \dots 6，寻找满足 d \times 10^{L-1-i} \equiv t \pmod 7 的 d 即可。若 d=0 则令 a[i]=7，否则 a[i]=d。枚举法常数极小且不会出错。

注意还原时需从右向左遍历（i = L-1 到 0），因为需要用到 s[i+1]。

复杂度分析

参考代码


#include<bits/stdc++.h>
#define int long long
using namespace std;

string ans="";
int s[1000005];
vector<int> lens;
int n,l,pos,pos,cur=1,;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    while(n>0){
        int len = 2;
        while(len*(len-1)/2<=n) len++;
        len--;
        lens.push_back(len);
        n -= len*(len-1)/2;
    }
    for (int i=0;i<lens[i];i++) l += lens[i];
    for (int i=0;i<lens.size();i++){
        for (int j=0;j<lens[i];j++) s[pos++] = cur;
        cur++;
    }
    s[l]=0;
    for (int i=l-1;i>=0;i--){
        int t=(s[i]-s[i+1]+7)%7,pow10=1,exp=l-1-i;
        for (int k=0;k<exp;k++) pow10=(pow10*10)%7;
        int val;
        for (int d=0;d<7;d++) {
            if ((d*pow10)%7==t) {
                val = d;
                break;
            }
        }
        if (val==0) val = 7;
        ans.push_back('0'+val);
    }
    reverse(ans.begin(),ans.end());//我们是从右往左构造，需要反转。
    cout<<ans;
    return 0;
}