数组构造+逆元

牛客2023寒假训赛3 B

请确保在尝试本题时了解数论中同余等式的相关内容。
如不了解同余以及同余等式的相关性质，可以到oiwiki进行学习了解后再尝试本题。
oiwiki 同余(性质) 逆元 数论知识 戳这里！！！

清楚姐姐最近在学习构造类问题，她现在遇到这样一个题目：

给定一个长度为N的数组c和一个质数m，请你构造另外两个数组a,b满足：

如果可以构造出数组a,b，则首先输出Yes，然后输出任意一种解，否则只需输出一行一个字符串No。
≡为同余符号，它表示两个整数对m取余数的结果相同，对于负数取余数，若结果仍为负数，则需要加上m。例如我们认为在模数7的情况下−12,−5,2同余，即
−12≡−5≡2(mod7)。

题解思路

特殊构造数组a，b的方式，a[i]=a[j],b[i]=-b[j];

#include<iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
ll a[N],b[N],c[N];

int main()
{
    ll n, m;
    cin>>n>>m;

    for (int i = 1; i <= n;i++)
        scanf("%lld", &c[i]);

    if(m==2)
    {
        for (int i = 1; i <= n / 2; i++)
        {
            int j = n - i + 1;
            int ok = 0;
            for (int x = 0; x < 2; x++)
            {
                for (int y = 0; y < 2; y++)
                {
                    if ((x + y) % 2 == c[i] % 2 && (x-y + 2) % 2 == c[j] % 2)
                    {
                        a[i] = a[j] = x;
                        b[i] = y;
                        b[j] = (-y + 2) % 2;
                        ok = 1;
                    }
                }
            }
            if(!ok)
            {
                puts("NO");
                return 0;
            }
        }
            
    }
    else
    {
        ll inv = (m + 1) / 2ll;
        for (int i = 1; i <= n / 2;i++)
        {
            int j = n - i + 1;
            a[i] = a[j] = (c[i] + c[j]) * inv % m;
            b[i] = ((c[i] - c[j]) % m + m)%m * inv % m;
            b[j] = (-b[i]%m + m) % m;
        }
    }
    if(n%2)
    {
        a[n / 2+1] = c[n / 2+1];
        b[n / 2+1] = 0;
    }
    
    puts("YES");
    for (int i = 1;i<=n;i++)
        printf("%lld%c", a[i],i==n?'\n':' ');
    for (int i = 1; i <= n;i++)
        printf("%lld%c", b[i],i==n?'\n':' ');
}