CF1484B Restore Modulo 题解

题目链接
我的洛谷Blog

题目大意

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

  1. a a a 的长度为 n n n
  2. a 1 = s m o d    m a_1=s \mod m a1​=smodm
  3. a i = ( a i − 1 + c ) m o d    m   ∣   ( 1 < i ≤ n ) a_i=(a_{i-1}+c) \mod m \space | \space (1 < i \le n) ai​=(ai−1​+c)modm ∣ (1<i≤n)
  4. 0 ≤ c < m 0 \le c < m 0≤c<m
  5. m m m 尽可能的大

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

解题思路

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

首先,因为 0 ≤ c < m 0 \le c <m 0≤c<m,我们可以把 m o d    m \mod m modm 的操作换成:如果 ≥ m \ge m ≥m,就减去 m m m。

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

  1. a i = a i − 1 + c − m a_i=a_{i-1}+c-m ai​=ai−1​+c−m
  2. a i = a i − 1 + c a_i=a_{i-1}+c ai​=ai−1​+c

可以发现,如果 a i − 1 + c ≥ m a_{i-1}+c \ge m ai−1​+c≥m,就一定有 a i < a i − 1 a_i<a_{i-1} ai​<ai−1​。因为 c − m < 0 c-m<0 c−m<0

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

  1. 如果 a i ≤ a i + 1   ∣   1 ≤ i < n a_i \le a_{i+1} \space | \space 1 \le i <n ai​≤ai+1​ ∣ 1≤i<n,且所有 a i + 1 − a i a_{i+1}-a_i ai+1​−ai​ 都相等,那么输出 0 0 0,因为生成序列式不需要取模
  2. 当满足 a i > a i + 1   ∣   1 ≤ i < n a_i > a_{i+1} \space | \space 1 \le i <n ai​>ai+1​ ∣ 1≤i<n,如果所有 a i + 1 − a i a_{i+1}-a_i ai+1​−ai​ 都相等,输出 0 0 0,否则输出 − 1 -1 −1
  3. 现在,已经满足了既有 a i > a i + 1 a_i> a_{i+1} ai​>ai+1​,也有 a i ≤ a i + 1 a_i \le a_{i+1} ai​≤ai+1​。那么,我们可以根据 a i ≤ a i + 1 a_i \le a_{i+1} ai​≤ai+1​ 的地方来求出 c c c。如果不能求出一个统一的 c c c,输出 − 1 -1 −1。
  4. 在求出了统一的 c c c 之后,对于每一个 a i > a i + 1 a_i > a_{i+1} ai​>ai+1​ 的地方,可以求出 m = a i + c − a i + 1 m=a_i+c-a_{i+1} m=ai​+c−ai+1​。如果求出的 m m m 是统一的且 m > c m>c m>c,则输出 m m m 和 c c c,否则输出 − 1 -1 −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;
}
上一篇:Codeforces Round #716 (Div. 2) C. Product 1 Modulo N


下一篇:Modulo Equality