CF1484B Restore Modulo 题解

· · 题解

题目链接
在我的Blog查看

题目大意

给出一个序列 a，问是否能找到四个数 n,m,s,c，满足以下条件

  1. a$ 的长度为 $n
  2. a_1=s \mod m
  3. a_i=(a_{i-1}+c) \mod m \space | \space (1 < i \le n)
  4. 0 \le c < m

如果不能找到这样的四个数，输出 -1
如果 m 可以任意大，输出 0
否则，输出最大可能的 m 和其对应的 c，如果有多个可能的 c，输出任意一个

解题思路

一道较为简单的数论+模拟题，但似乎在赛时卡掉了很多人

首先，因为 0 \le c <m，我们可以把 \mod m 的操作换成：如果 \ge m，就减去 m。

那么，对于 (1 < i \le n)，就有如下两种可能：

  1. a_i=a_{i-1}+c-m
  2. a_i=a_{i-1}+c

可以发现，如果 a_{i-1}+c \ge m，就一定有 a_i<a_{i-1}。因为 c-m<0

现在，我们按顺序判断如下几种情况

  1. 如果 a_i \le a_{i+1} \space | \space 1 \le i <n，且所有 a_{i+1}-a_i 都相等，那么输出 0，因为生成序列式不需要取模
  2. 当满足 a_i > a_{i+1} \space | \space 1 \le i <n，如果所有 a_{i+1}-a_i 都相等，输出 0，否则输出 -1
  3. 现在，已经满足了既有 a_i> a_{i+1}，也有 a_i \le a_{i+1}。那么，我们可以根据 a_i \le a_{i+1} 的地方来求出 c。如果不能求出一个统一的 c，输出 -1。
  4. 在求出了统一的 c 之后，对于每一个 a_i > a_{i+1} 的地方，可以求出 m=a_i+c-a_{i+1}。如果求出的 m 是统一的且 m>c，则输出 m 和 c，否则输出 -1
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int Maxn=1e5+10;
int n,m,val;
int a[Maxn];
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
bool check()
{
    if(n==1)return 1;
    bool flag=1;
    for(int i=1;i<n;++i)
    if(a[i]>a[i+1] || a[i]+m!=a[i+1])
    {flag=0;break;}
    if(flag)return 1;
    flag=1;
    for(int i=1;i<n;++i)
    if(a[i]<=a[i+1]){flag=0;break;}
    if(flag)
    {
        int tmp=a[1]-a[2];
        for(int i=2;i<n;++i)
        if(a[i]-a[i+1]!=tmp){flag=0;break;}
        if(flag)return 1;
    }
    return 0;
}
int calc()
{
    int tmp;
    for(int i=1;i<n;++i)
    {
        if(a[i]<=a[i+1] && a[i]+m!=a[i+1])
        return 0;
        if(a[i]<=a[i+1])continue;
        if((a[i]+m)-a[i+1]<=val)return 0;
        tmp=(a[i]+m)-a[i+1];
    }
    for(int i=1;i<n;++i)
    {
        if(a[i]<=a[i+1])continue;
        if(a[i]+m-a[i+1]!=tmp)return 0;
    }
    return tmp;
}
int main()
{
    // freopen("in.txt","r",stdin);
    int T=read();
    while(T--)
    {
        n=read();
        val=-1;
        for(int i=1;i<=n;++i)
        a[i]=read(),val=max(val,a[i]);
        for(int i=1;i<n;++i)
        if(a[i]<=a[i+1])m=a[i+1]-a[i];
        if(check()){puts("0");continue;}
        int tmp=calc();
        if(!tmp){puts("-1");continue;}
        printf("%d %d\n",tmp,m);
    }
    return 0;
}