CF1484B Restore Modulo 题解

Priori_Incantatem

2021-03-22 15:48:30

题解

题目链接
在我的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,则输出 mc,否则输出 -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;
}