In mathematics you don't understand things, you just get used to them.

分类 笔记 下的文章

「CF 1514A」Perfectly Imperfect Array

Link.

就看序列中是否存在不为平方数的元素即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
ll T,n,x;
bool check(ll x)
{
    for(ll i=1;i*i<=x;++i)    if(i*i==x)    return true;
    return false;
}
int main()
{
    for(sf(T);T;--T)
    {
        sf(n);
        bool fl=0;
        for(int i=1;i<=n;++i)
        {
            sf(x);
            if(!check(x))    fl=1;
        }
        if(fl)    puts("YES");
        else    puts("NO");
    }
    return 0;
}

「CF 1514B」AND 0, Sum Big

Link.

和最大的情况就是每个数都只有一个 $0$(二进制下),于是答案就是 $n^{k}$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
const int MOD=1e9+7;
int main()
{
    int T,n,k;
    for(sf(T);T;--T)
    {
        sf(n),sf(k);
        ll ans=1;
        for(int i=1;i<=k;++i)    ans*=n,ans%=MOD;
        pf(ans);
    }
    return 0;
}

「CF 1514C」Product 1 Modulo N

Link.

把所有与 $n$ 互质的数拉出来,如果 product 不满足要求,就把最后一个剔除。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int n;
ll op(ll x,ll y){return x*y%n;}
int main()
{
    sf(n);
    std::vector<ll> ans;
    for(int i=1;i<=n;++i)    if(__gcd(i,n)==1)    ans.emplace_back(i);
    if(accumulate(ans.begin(),ans.end(),1,op)!=1)    ans.pop_back();
    pf(ans.size());
    for(int i:ans)    pf(i,' ');
    return 0;
}

「CF 1514D」Cut and Stick

Link.

答案是 $\max\{1,2x-l\}$,$l$ 为区间长度,$x$ 为众数出现次数。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 5e5 + 5, MAXM = 720 + 5;

char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar( ) ( p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1 ++ )

template<typename _T>
void read( _T &x ){
    x = 0; char c = getchar( ); _T f = 1;
    while( c < '0' || c > '9' ){ if( c == '-' )    f = -1; c = getchar( ); }
    while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar( ); }
    x *= f;
}

template<typename _T>
void write( _T x ){
    if( x < 0 ){ putchar( '-' ); x = -x; }
    if( x > 9 ){ write( x / 10 ); }
    putchar( x % 10 + '0' );
}

template<typename _T>
void swapp( _T &one, _T &another ){ int temp = one; one = another; another = temp; }

template<typename _T>
_T MIN( _T one, _T another ){ return one > another ? another : one; }

template<typename _T>
_T MAX( _T one, _T another ){ return one > another ? one : another; }

int N, M;
int cube, each, kase, isa[MAXN], cnt[MAXN], pos[MAXN], vis[MAXN], bel[MAXN];
int lps[MAXM], rps[MAXM], App[MAXM][MAXM];
vector<int> disc, fur[MAXN];

int getID( int x ){ return lower_bound( disc.begin( ), disc.end( ), x ) - disc.begin( ) + 1; }

void build( ){
    memset( cnt, 0, sizeof( cnt ) );
    for( int i = 1; i <= cube; ++ i ){
        kase ++;
        for( int j = i; j <= cube; ++ j ){
            App[i][j] = App[i][j - 1];
            for( int k = lps[j]; k <= rps[j]; ++ k ){
                if( vis[isa[k]] != kase )    cnt[isa[k]] = 0;
                cnt[isa[k]] ++; App[i][j] = MAX( App[i][j], cnt[isa[k]] );
                vis[isa[k]] = kase;
            }
        }
    }
    memset( cnt, 0, sizeof( cnt ) );
}

int query( int opl, int opr ){
    if( bel[opl] == bel[opr] ){
        int res = 0; kase ++;
        for( int i = opl; i <= opr; ++ i ){
            if( vis[isa[i]] != kase )    cnt[isa[i]] = 0;
            cnt[isa[i]] ++; res = MAX( res, cnt[isa[i]] );
            vis[isa[i]] = kase;
        }
        return res;
    }
    int res = 0;
    res = App[bel[opl] + 1][bel[opr] - 1];
    for( int i = opl; i <= rps[bel[opl]]; ++ i ){
        int lim = fur[isa[i]].size( ) - 1;
        while( pos[i] + res <= lim && fur[isa[i]][pos[i] + res] <= opr )    res ++;
    }
    for( int i = lps[bel[opr]]; i <= opr; ++ i ){
        while( pos[i] - res >= 0 && fur[isa[i]][pos[i] - res] >= opl )    res ++;
    }
    return res;
}

signed main( ){
    read( N ); read( M ); each = 720; cube = ( N - 1 ) / each + 1;
    for( int i = 1; i <= N; ++ i ){ read( isa[i] ); disc.push_back( isa[i] ); }
    sort( disc.begin( ), disc.end( ) );
    disc.erase( unique( disc.begin( ), disc.end( ) ), disc.end( ) );
    for( int i = 1; i <= N; ++ i ){
        isa[i] = getID( isa[i] );
        fur[isa[i]].push_back( i );
        pos[i] = fur[isa[i]].size( ) - 1;
    }
    for( int i = 1; i <= cube; ++ i ){
        lps[i] = rps[i - 1] + 1; rps[i] = rps[i - 1] + each;
        if( i == cube )    rps[i] = N;
        for( int j = lps[i]; j <= rps[i]; ++ j )    bel[j] = i;
    }
    build( );
    int opl, opr;
    while( M -- > 0 ){
        read( opl ); read( opr );
        write( max( 1, 2 * query( opl, opr ) - ( opr - opl + 1 ) ) );
        putchar( '\n' );
    }
    return 0;
}

「CF 1514E」Baby Ehab's Hyper Apartment

Link.

// Oops, something went wrong.

「CF 1525A」Potion-making

Link.

显然。

#include<bits/stdc++.h>
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int main()
{
    int T,k;
    sf(T);
    while(T-->0)
    {
        sf(k);
        int p1=k,p2=100-k,x=gcd(p1,p2);
        p1/=x;
        p2/=x;
        pf(p1+p2);
    }
    return 0;
}

「CF 1525B」Permutation Sort

Link.

注意到答案只有 $0/1/2/3$,分类讨论即可。

吃了三发罚时

#include<bits/stdc++.h>
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int T,n,a[60];
int main()
{
    for(sf(T);T;--T)
    {
        sf(n);
        for(int i=1;i<=n;++i)    sf(a[i]);
        int flag=1;
        for(int i=2;i<=n;++i)
        {
            if(a[i]!=a[i-1]+1)
            {
                flag=0;
                break;
            }
        }
        if(!flag)
        {
            if(a[1]==n && a[n]==1)    puts("3");
            else if(a[n]==n || a[1]==1)    puts("1");
            else    puts("2");
        }
        else    puts("0");
    }
    return 0;
}

「CF 1525C」Robot Collisions

Link.

显然我不会。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
template<typename T>void sf(T &x) {
    x = 0;
    T f = 0;
    char c = getchar();

    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            f = 1;

    for (; c >= '0' && c <= '9'; c = getchar())
        x = (x << 3) + (x << 1) + (c^'0');

    if (f)
        x = -x;
}
template<typename T>void pf(T x, char l = '\n') {
    static T s[100], t;

    if (x < 0)
        putchar('-'), x = -x;

    do
        s[++t] = x % 10, x /= 10;

    while (x)
        ;

    while (t)
        putchar(s[t--]^'0');

    putchar(l);
}
struct st {
    int a, b, id;
} Sts[300005], Uji[300005], Qql[300005];
bool cmp(st A, st B) {
    return A.a < B.a;
}
int reait[300005];
int n, m;
int U(int x, int y) {
    int res = 0;

    if (Sts[x].a < Sts[y].a) {
        if (Sts[x].b == 0)
            res += Sts[x].a, Sts[x].a = 0;

        if (Sts[y].b == 1)
            res += (m - Sts[y].a), Sts[y].a = m;

        return (res + abs(Sts[x].a - Sts[y].a)) / 2;
    } else {
        if (Sts[x].b == 1)
            res += (m - Sts[x].a), Sts[x].a = m;

        if (Sts[y].b == 0)
            res += Sts[y].a, Sts[y].a = 0;

        return (res + abs(Sts[x].a - Sts[y].a)) / 2;
    }
}
signed main() {
    int T;
    sf(T);

    while (T--) {
        sf(n), sf(m);

        for (int i = 1; i <= n; i++)
            reait[i] = -1;

        int rks = 0, tss = 0;

        for (int i = 1; i <= n; i++) {
            sf(Sts[i].a);
            Sts[i].id = i;
        }

        for (int i = 1; i <= n; i++) {
            char res = getchar();

            while (res != 'L' && res != 'R')
                res = getchar();

            Sts[i].b = res == 'R';
        }

        for (int i = 1; i <= n; i++) {
            if (Sts[i].a & 1)
                Qql[++tss] = Sts[i];
            else
                Uji[++rks] = Sts[i];
        }

        sort(Uji + 1, Uji + rks + 1, cmp);
        sort(Qql + 1, Qql + tss + 1, cmp);
        stack <int> Q;
        Q.push(1);

        for (int i = 2; i <= rks; i++) {
            if (Uji[i].b == 0 && !Q.empty()) {
                int u = Q.top();
                Q.pop();
                reait[Uji[i].id] = reait[Uji[u].id] = U(Uji[i].id, Uji[u].id);
            } else
                Q.push(i);
        }

        while (!Q.empty()) {
            int u = Q.top();
            Q.pop();

            if (!Q.empty()) {
                int v = Q.top();
                Q.pop();
                reait[Uji[u].id] = reait[Uji[v].id] = U(Uji[u].id, Uji[v].id);
            }
        }

        Q.push(1);

        for (int i = 2; i <= tss; i++) {
            if (Qql[i].b == 0 && !Q.empty()) {
                int u = Q.top();
                Q.pop();
                reait[Qql[i].id] = reait[Qql[u].id] = U(Qql[i].id, Qql[u].id);
            } else
                Q.push(i);
        }

        while (!Q.empty()) {
            int u = Q.top();
            Q.pop();

            if (!Q.empty()) {
                int v = Q.top();
                Q.pop();
                reait[Qql[u].id] = reait[Qql[v].id] = U(Qql[u].id, Qql[v].id);
            }
        }

        for (int i = 1; i <= n; i++)
            printf("%lld ", reait[i]);

        printf("\n");
    }

    return 0;
}

「CF 1525D」Armchairs

Link.

设 $f(i,j)$ 表示考虑把第 $j$ 个人放进前 $i$ 个座位里的方案,转移。

多久没写 DP 了啊,这种水平的 DP 都写漏一堆东西。

#include<bits/stdc++.h>
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int n,a[5010],fr[5010],t0,oc[5010],t1,op[5010];
ll dp[5010][5010],ans=std::numeric_limits<ll>::max();
inline int fs(int x){return x<0?-x:x;}
int main()
{
    sf(n);
    for(int i=1;i<=n;++i)
    {
        sf(a[i]);
        if(a[i])    oc[++t1]=i;
        else    fr[++t0]=i;
    }
    for(int i=1;i<=t1;++i)    for(int j=0;j<=n;++j)    dp[i][j]=1e18;
    for(int i=1;i<=t1;++i)    for(int j=1;j<=n;++j) {
        dp[i][j]=dp[i][j-1];
        if(!a[j])    dp[i][j]=std::min(dp[i][j],dp[i-1][j-1]+fs(oc[i]-j));
    }
    pf(dp[t1][n]);
    return 0;
}

「CF 1525E」Assimilation IV

Link.

// Oops, something went wrong.

「CF 1525F」Goblins And Gnomes

Link.

// Oops, something went wrong.

Description

Link.

对于一棵树,选出一条链 $(u,v)$,把链上结点从 $u$ 到 $v$ 放成一个 长度 $l$ 的数组,使得 $\sum_{i=1}^{l}\sum_{j=1}^{i}a_{j}$ 最大,$a$ 是点权。

Solution

可以发现那个式子等价于 $\sum_{i=1}^{l}ia_{i}$。

考虑点分,设当前根为 $x$。选出来的 $u,v$ 一定是叶子(点权为正),因为没有什么本质差别,所以可以一起算。我们把 $x$ 在 $(u,v)$ 中的位置记作 $o$,$(u,v)$ 的权值就为 $\sum_{i=1}^{l}ia_{i}=\sum_{i=1}^{o}ia_{i}+l\sum_{i=o+1}^{l}a_{i}+\sum_{i=o+1}^{l}(i-l)a_{i}$,这是个一次函数,令 $b_{1}=\sum_{i=1}^{l}ia_{i}=\sum_{i=1}^{o}ia_{i},b_{2}=\sum_{i=o+1}^{l}(i-l)a_{i},k=l$,得 $\sum_{i=1}^{l}ia_{i}=k\times\sum_{i=o+1}^{l}a_{i}+b_{1}+b_{2}$。

#include<bits/stdc++.h>
typedef long long ll;
#define sf(x) scanf("%d",&x)
#define ssf(x) scanf("%lld",&x)
struct Line {
    ll k,b;
    Line():k(0),b(0){}
    Line(ll _k,ll _b):k(_k),b(_b){}
}lns[10000010];
std::vector<int> G[200010];
ll a[200010],ans,stk[6][200010];
// stk[0]: sum(i=1~l)i*a[i]
// stk[1]: sum(i=o+1~l)(i-l)*a[i]
// stk[2]: sum(i=o+1~l)a[i]
// stk[3]: all the nodes we passed and possible to be the final node
// stk[4]: l
// stk[5]: where to belong to
int n,szf[200010],tot,tr[800010],top,rt,del[200010],siz[200010],mxdep,dep[200010];
ll ff(ll x,int i){return lns[i].k*x+lns[i].b;}
ll getk(int i){return lns[i].k;}
bool chk(ll x,int i,int j){return ff(x,i)>ff(x,j);}
void ins(int l,int r,int now,int t)
{
    if(l^r)
    {
        if(chk(l,t,tr[now]) && chk(r,t,tr[now]))    tr[now]=t;
        else if(chk(l,t,tr[now]) || chk(r,t,tr[now]))
        {
            int mid=(l+r)>>1;
            if(chk(mid,t,tr[now]))    tr[now]^=t^=tr[now]^=t;
            if(chk(l,t,tr[now]))    ins(l,mid,now<<1,t);
            else    ins(mid+1,r,now<<1|1,t); 
        }
    }
    else if(chk(l,t,tr[now]))    tr[now]=t;
}
int find(int l,int r,int now,int t) // query line id
{
    if(l^r)
    {
        int mid=(l+r)>>1,res;
        if(mid>=t)    res=find(l,mid,now<<1,t);
        else    res=find(mid+1,r,now<<1|1,t);
        if(chk(t,res,tr[now]))    return res;
        else    return tr[now];
    }
    else    return tr[now];
}
void clear(int l,int r,int now)
{
    int mid=(l+r)>>1;
    tr[now]=0;
    if(l^r)    clear(l,mid,now<<1),clear(mid+1,r,now<<1|1);
}
void get_root(int now,int las,int all)
{
    siz[now]=1;
    szf[now]=0;
    for(int to:G[now])
    {
        if((to^las) && !del[to])
        {
            get_root(to,now,all);
            siz[now]+=siz[to];
            szf[now]=std::max(szf[now],siz[to]);
        }
    }
    szf[now]=std::max(szf[now],all-siz[now]);
    if(szf[now]<szf[rt])    rt=now;
}
void get_value(int now,ll prf0,ll prf1,ll prf2,int wr,int las)
{
    if((now^rt) && !wr)    wr=now;
    mxdep=std::max(mxdep,dep[now]=dep[las]+1);
    bool lef=1;
    for(int to:G[now])    if((to^las) && !del[to])
        lef=0,get_value(to,prf0+prf2+a[to],prf1+a[to]*dep[now],prf2+a[to],wr,now);
    if(lef)
        ++top,stk[0][top]=prf0,stk[1][top]=prf1,stk[2][top]=prf2-a[rt],
        stk[3][top]=now,stk[4][top]=dep[now],stk[5][top]=wr;
}
void get_ans(int now)
{
    del[now]=1;
    top=mxdep=0;
    get_value(now,a[now],0,a[now],0,0);
    ++top;
    stk[0][top]=a[now];
    stk[1][top]=stk[2][top]=stk[5][top]=0;
    stk[3][top]=now;
    stk[4][top]=1;
    stk[5][top+1]=stk[5][0]=-1;
    clear(1,mxdep,1);
    int i=1,j;
    while(i<=top)
    {
        j=i;
        while(stk[5][i]==stk[5][j])    ans=std::max(ff(stk[4][j],find(1,mxdep,1,stk[4][j]))+stk[0][j],ans),++j;
        j=i;
        while(stk[5][i]==stk[5][j])    lns[++tot]=Line(stk[2][j],stk[1][j]),ins(1,mxdep,1,tot),++j;
        i=j;
    }
    clear(1,mxdep,1);
    i=top;
    while(i)
    {
        j=i;
        while(stk[5][i]==stk[5][j])    ans=std::max(ff(stk[4][j],find(1,mxdep,1,stk[4][j]))+stk[0][j],ans),--j;
        j=i;
        while(stk[5][i]==stk[5][j])    lns[++tot]=Line(stk[2][j],stk[1][j]),ins(1,mxdep,1,tot),--j;
        i=j;
    }
    for(int to:G[now])    if(!del[to])    rt=0,get_root(to,now,siz[to]),get_ans(rt);
}
int main()
{
    sf(n);
    for(int i=1,x,y;i<n;++i)
    {
        sf(x),sf(y);
        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }
    for(int i=1;i<=n;++i)    ssf(a[i]);
    szf[0]=n+1;
    get_root(1,0,n);
    get_ans(rt);
    printf("%lld\n",ans);
    return 0;
}

Description

Link.

给定一个长度为 $n$ 的数组让你填数,需要满足 $m$ 个形如 $([l_{1},r_{1}],[l_{2},r_{2}])$ 的要求,这两个区间填好后需要一样,问方案数。

Solution

Let us only consider one limit $([l_{1},r_{1}],[l_{2},r_{2}])$, the number of ways is $10^{r-l+1}$.
Connecting every $i\in[l_{1},r_{1}]$ and $j\in[l_{2},r_{2}]$, we can construct a graph.
Counting the number of connected subgraphs, denoted as $x$, the answer is $9\times10^{x-1}$, and the complexity is $\mathcal{O}(n^{2}\alpha(n))$.
Each interval could be splited into $\log_{2}r-l+1$ subintervals, so that we can solve this in $\mathcal{O}(n\log_{2}n\alpha(n))$.

#include <bits/stdc++.h>
typedef long long ll;
#define sf(x) scanf("%d",&x)
#define ssf(x) scanf("%lld",&x)
struct DSU {
    int fa[100010];
    void init(int l) {
        std::iota(fa + 1, fa + l + 1, 1);
    }
    int find(int x) {
        return (x ^ fa[x]) ? fa[x] = find(fa[x]) : x;
    }
    void ins(int x, int y) {
        if (x ^ y)
            fa[x] = y;
    }
} dsu[20];
int n, m, opl0, opr0, opl1, opr1;
ll ans = 1;
int main() {
    sf(n), sf(m);

    for (int i = 0; i ^ 20; ++i)
        dsu[i].init(n);

    while (m-- > 0) {
        sf(opl0), sf(opr0), sf(opl1), sf(opr1);
        int cur0 = opl0, cur1 = opl1;

        for (int i = 19; ~i; --i) {
            if (cur0 + (1 << i) - 1 <= opr0) {
                dsu[i].ins(dsu[i].find(cur0), dsu[i].find(cur1));
                cur0 += (1 << i);
                cur1 += (1 << i);
            }
        }
    }

    for (int j = 19; j; --j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            dsu[j - 1].ins(dsu[j - 1].find(i), dsu[j - 1].find(dsu[j].find(i)));
            dsu[j - 1].ins(dsu[j - 1].find(i + (1 << (j - 1))), dsu[j - 1].find(dsu[j].find(i) + (1 << (j - 1))));
        }
    }

    for (int i = 1; i <= n; ++i)
        if (dsu[0].fa[i] == i)
            ans = ans * (ans == 1 ? 9 : 10) % 1000000007;

    printf("%lld\n", ans);
    return 0;
}

Description

Link.

$ n $ distinct integers $ x_1,x_2,\ldots,x_n $ are written on the board. Nezzar can perform the following operation multiple times.

  • Select two integers $ x,y $ (not necessarily distinct) on the board, and write down $ 2x-y $ . Note that you don't remove selected numbers.

Now, Nezzar wonders if it is possible to have his favorite number $ k $ on the board after applying above operation multiple times.

Solution

Let us onsider how to express all the number we can express.
Since $2x-y=x+(x-y)$, the expression is $x_{i}+\sum_{j,k}x_{j}-x{k}$.
Since $x_{i}=x_{1}+(x_{1}-(x_{1}+(x_{1}-x_{i})))$, the expression could be written as $x_{1}+\sum_{i}x_{i}-x_{1}$, which means the answer exists where $\sum_{i}x_{i}-x_{1}=K-x_{1}$ has solutions.
Beout's identity works.

#include<bits/stdc++.h>
typedef long long ll;
#define sf(x) scanf("%d",&x)
#define ssf(x) scanf("%lld",&x)
int main()
{
    int T,n;
    ll k;
    sf(T);
    while(T-->0)
    {
        sf(n),ssf(k);
        ll g=0,x1,x;
        ssf(x1);
        for(int i=2;i<=n;++i)    ssf(x),g=std::__gcd(x-x1,g);
        puts((k-x1)%g==0?"YES":"NO");
    }
    return 0;
}