526互联

ARC118

发布时间 2023-11-30 19:30:10作者: Call_me_Eric

ARC118

第一次做arc场，被爆杀QAQ

ARC118A

link

ARC118A题意

ARC国家的消费税率是 \(t\) 。其中 \(t\) 是正整数。
ARC国家有整数屋。整数屋先生以不含税价格 \(A\) 日元处理着各个正整数 \(A\)，这个含税价格是 \(\lfloor\frac{100 + t}{100}A \rfloor\) 日元。但是，对于实数 \(x\)，\(\lfloor x \rfloor\) 表示 \(x\) 以下的最大整数。

虽然是经营所有正整数的整数屋，但存在不作为含税价格出现的正整数金额。在这些金额中，请找从小到大的第 \(N\) 个。

简要题意：

定义函数$$f(A)=A+\lfloor \frac{t*A}{100}\rfloor$$
定义集合$$S={A\in \mathbb{Z}|f(A)}$$
求第 \(N\) 个没出现在集合 \(S\) 的正整数。

ARC118A题解

不难发现，函数 \(f(A)\) 是由两个函数 \(f_1(A)=A\) 和 \(f_2(A)=\lfloor \frac{t*A}{100}\rfloor\) 组成的，第一个函数在 \(\mathbb{Z}\) 上连续，第二个每次越过 \(100k(k\in \mathbb{Z})\) 之后都会突变 \(1\)，故每一个没出现在 \(S\) 中的数字都满足 \(f_2(A-1) + 1 = f_2(A)\)。
不难推出，第 \(N\) 个没出现的数字就是 \(f(x)-1,x=\lceil \frac{100N}{t}\rceil\)。
没了。

ARC118A代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=  0, f=  1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
int t, N;
int A;
signed main(){
    t = read();N = read();
    A = (100LL * N) / t + ((100ll * N) % t ? 1ll : 0ll);
    printf("%lld\n",A + (t * A) / 100ll - 1ll);
    return 0;
}

ARC118B

link
当前用时:1:18:27.06

ARC118B题意

tips:不要看luogu翻译的解释。
给出一个长度为 \(k\) 的数列 \(a\)，其总和为 \(n\)，和另一个数字 \(m\)。
现让你构造长度同样为 \(k\) 的数列 \(b\)，满足以下要求：

  • \(\sum_{i=1}^kb_i=m\)
  • \(\max_{i=1}^k{|\frac{b_i}{m}-\frac{a_i}{n}|}\) 最小

给出构造方案。

ARC118B题解

看题看半天发现翻译没get到关键点
然后手写ceil又挂了（

首先通分第二个条件：$$|\frac{b_i}{m}-\frac{a_i}{n}|=|\frac{b_i\times n-a_i\times m}{n\times m}|$$
发现上式变量只有 \(b_i\)，于是二分 \(({b_i\times n-a_i\times m})\) 的最小值。
发现 \(b_i\in[\lceil\frac{a_i\times m-mid}{n}\rceil,\lfloor\frac{a_i\times m+mid}{n}\rfloor]\)，然后判断并构造一组解即可。
注意 \(ceil\) 的写法啊（恼

ARC118B代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=  0, f=  1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10;
int k, n, m,a[maxn], b[maxn], c[maxn], l[maxn], r[maxn];
bool check(int mid){
    int suml = 0, sumr = 0;
    for(int i = 1;i <= k;i++){
        l[i] = ceil(1.0 * (a[i] * m - mid) / n);
        r[i] = (a[i] * m + mid) / n;
        if(l[i] < 0)l[i] = 0; c[i] = 0;
        suml += l[i];sumr += r[i];
    }
    int rest = m - suml;
    // printf("rest = %lld,",rest);
    // printf("mid = %lld\n",mid);
    // for(int i  = 1;i <= k;i++){printf("l[%lld]=%lld r[%lld]=%lld\n",i,l[i],i,r[i]);}
    if(!(suml <= m && m <= sumr))return false;
    for(int i = 1;i <= k;i++){
        c[i] = l[i] + min(r[i] - l[i],rest);
        rest -= (c[i] - l[i]);
    }
    return rest == 0;
}
signed main(){
    k = read(); n = read(); m = read();
    for(int i = 1;i <= k;i++){a[i] = read();}
    int L = 0, R = 1e9, mid = 0;
    while(L <= R){
        mid = L + R >> 1;
        if(check(mid)){
            for(int i = 1;i <= k;i++)b[i] = c[i];
            // printf("mid = %lld\n",mid);
            R = mid - 1;
        }
        else L = mid + 1;
    }
    // check(60);
    for(int i = 1;i <= k;i++)printf("%lld ",b[i]);
    return 0;
}

ARC118C

link

当前用时：2:10:15.38

ARC118C题意

构造一个长度为 \(n\) 的数列 \(a\)，满足：

  • \(\forall 1\le i\le n,1\le a_i\le10^4\)
  • \(\forall 1\le i,j\le n,\gcd(i,j)>1\) 且当 \(i\neq j\) 时 \(a_i\neq a_j\)
  • \(\gcd(a_1,a_2,\dots,a_n)==1\)

给出构造方案。

ARC118C题解

不难想到方法。
构造多列数字形如：

  • \(2\times3\times1,2\times3\times2,\dots,2\times3\times k\)
  • \(2\times5\times1,2\times5\times2,\dots,2\times5\times k\)
  • \(\dotsb\)
  • \(2\times prime_t\times1,2\times prime_t\times2,\dots,2\times prime_t\times k\)

直到数字数量为 \(n-1\)。
然后令 \(a_n=\prod_{i=1}^tprime_i\)。
然后就能保证满足上述条件。
证明略，可以对拍。
不过注意重复元素不能重复用。

ARC118C代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=  0, f=  1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e4 + 10;
int n;
int prime[maxn], tot, a[maxn];
bool book[maxn];
signed main(){
    n = read();
    for(int i = 2;i < maxn;i++){
        if(!book[i])prime[++tot] = i;
        for(int j = 1;j <= tot && prime[j] * i < maxn;j++){
            book[prime[j] * i] = 1;
            if(i % prime[j] == 0)break;
        }
    }
    memset(book,0,sizeof(book));
    int tmp = 1,pim = 1, point = 1;
    while(point < n){
        pim++;tmp *= prime[pim];
        int cnt = 2 * prime[pim], i = 0;
        while(cnt * (i + 1) <= 1e4 && point < n){
            i++;
            if(book[cnt * i])continue;
            a[point++] = i * cnt;
        }
    }
    a[n] = tmp * (pim == 2 ? prime[pim + 1] : 1);
    a[n - 1] = (pim == 2 ? (prime[pim + 1] * 2) : a[n - 1]);
    for(int i = 1;i <= n;i++)printf("%d ",a[i]);
    return 0;
}

ARC118D

link

ARC118D题意

给定质数 \(P\) 和两个正整数 \(a,b\)，要求构造一个长度为 \(P\) 的序列满足：

  • \(1\le A_i\le P-1\)；
  • \(A_1=A_P=1\)；
  • \((A_1,A_2,\dots,A_{P-1})\) 是一个 \(1\sim P-1\) 的排列；
  • \(\forall 2\le i\le P\)，满足下列四个条件中的至少一个：
    1. \(A_i\equiv aA_{i-1}\pmod P\)；
    2. \(A_{i-1}\equiv aA_i\pmod P\)；
    3. \(A_i\equiv bA_{i-1}\pmod P\)；
    4. \(A_{i-1}\equiv bA_i\pmod P\)。

\(\texttt{Data Range}:2\le P\le 10^5,1\le a,b\le P-1\)，\(P\) 为质数。

ARC118D题解

不难发现，如果将每个数字 \(x\) 看做一个点，那么 \(x\) 会连向 \(x\times a\pmod p\)，\(x\times a^{-1}\pmod p\)，\(x\times b\pmod p\)，\(x\times b^{-1}\pmod p\) 这四个点。
然后再做下去就是哈密顿回路是NP问题，然后就没有思路了。

去看了下官方题解发现，可以根据这个构造一个矩阵，在矩阵上可以 \(O(n)\) 找回路。（真的是太巧妙了）

具体而言，令 \(n\) 是满足 \(a^n\equiv 1\pmod p\) 的最小正整数。
然后得到一个集合 \(S = \{x|x=a^i,i\in[0,n]\}\)。
然后找到最小的正整数 \(m\) 满足 \(b^m\pmod p\in S\)。
首先判断 \(n\times m=p-1\)，如果不等无解。
然后建立一个 \(n\times m\) 的矩阵，其中每一个位置 \((i,j)\) 填入 \(a^{i-1}\times b^{j-1}\)，然后就可以从 \((1,1)\) 出发，走遍所有的格点，然后就没了。

证明？

  • 每个 \([1,p-1]\) 的数字在矩阵中出现至少一次：
    1. 不妨设一个数字 \(X=a^xb^y\)，则 \(X = a^x(b^m)^tb^r\)，其中 \(y\equiv r\pmod m\)，故一定有 \(r<b\)。
    2. 又因为 \(\exist k,b^m=a^k\)，则 \(X=a^xa^{kt}b^r=a^{x+kt}b^r\)。
    3. 但是由于 \(a^i\) 有循环节 \(n\)，故令 \(z\equiv x+kt\pmod n\)，则 \(X=a^zb^r\)。
    4. 此时 \(z+1\le n,r+1\le m\)，在矩阵中，证毕。
  • 每个 \([1,p-1]\) 的数字在矩阵中最多出现一次：
    1. 不妨设 \(X=a^ib^j=a^xb^y\) 且 \(i\neq x,j\neq y\)。
    2. 那么一定有 \(a^{i-x}\equiv b^{y-j}\pmod p\)。（如果 \(y<j\) 就两边都取逆元）
    3. 我们知道，前文定义中 \(\exists k,b^m=a^k\) 且 \(\forall i\in[1,m),\nexists j,a^j\equiv b^i\pmod p\)。
    4. 而 \(1\le y-j<m\)。
    5. 故不存在这样两对 \((i,j)\) 和 \((x,y)\)，使得上式被满足。
    6. 证毕。

特别的，这个矩阵可以从 \((n,k)\) 走到 \((1,k)\)，但是不能从 \((k,m)\) 走到 \((k,1)\)，找回路的时候需要注意。

ARC118D代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=  0, f=  1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e6 + 10;
int qpow(int x,int a,int mod){
    int res = 1;
    while(a){
        if(a & 1) res = res * x % mod;
        x = x * x % mod;a >>= 1;
    }
    return res;
}
int p, a, b, inva, invb;
bool book[maxn];
vector<int> arr;
signed main(){
    p = read(); a = read(); b = read();
    inva = qpow(a,p - 2,p);invb = qpow(b,p - 2,p);
    int n = 1, m = 1, x = a, y = b;
    while(n <= p){book[x] = 1;if(x == 1)break;x = (x * a % p);n++;}
    while(m <= p){if(book[y])break;y = y * b % p;m++;}
    if(n * m != p - 1 || !book[y]){puts("No");return 0;}
    puts("Yes");
    if(n == 1 || m == 1){
        if(n == 1){swap(a, b);}x = 1;
        for(int i = 1;i <= p;i++){printf("%lld ",x);x = x * a % p;}
        puts(""); return 0;
    }
    if((m & 1) == 0){
        x = 1;
        for(int i = 1;i <= m;i++){
            arr.push_back(x);
            x = x * b % p;
        }
        x = x * invb % p;x = x * a % p;
        for(int i = 1;i <= m;i += 2){
            for(int j = 2;j <= n;j++){
                arr.push_back(x);
                x = x * a % p;
            }
            x = x * inva % p;x = x * invb % p;
            for(int j = 2;j <= n;j++){
                arr.push_back(x);
                x = x * inva % p;
            }
            x = x * a % p;x = x * invb % p;
        }
        for(int i : arr)printf("%lld ",i);
        puts("1");
        return 0;
    }
    else{
        swap(a,b);swap(inva,invb);swap(n, m);
        x = 1, y = 1;
        for(int i = 1;i <= m;i += 2){
            for(int j = 1;j <= n;j++){
                arr.push_back(x * y % p);
                x = x * a % p;
            }
            y = y * b % p;x = x * inva % p;
            for(int j = 1;j <= n;j++){
                arr.push_back(x * y % p);
                x = x * inva % p;
            }
            x = x * a % p;y = y * b % p;
        }
        for(int i : arr)printf("%lld ",i);
        puts("1");
    }
    return 0;
}

ARC118E

link

ARC118E题意

给出一个 \((n+2)\times(n+2)\) 的网格图。
定义一个排列 \(P\) 和它的一个函数 \(f(P)\)。
其中 \(f(P)\) 表示，将所有 \((i,P_i)\) 点标记，则 \(f(P)\) 等于所有从 \((0,0)\to (n+1,n+1)\) 且不经过任意一个标记点的方案数。
现在这个排列有些位置没有填好（对应的 \(P_i=-1\)），问所有可能填好的排列情况的 \(f(P')\) 的总和是多少。

ARC118E题解

首先先想一个问题，如果给出一个填好的排列，怎么算 \(f(P)\)。
这里给出一个trick，利用容斥来计数。
具体而言，让一条路径的贡献是 \((-1)^{经过标记点的数量}\)，证明显然。
然后对于填好的序列，设 \(f_{i,j}\) 表示到点 \((i,j)\) 的方案数，则 \((-1)^{lim_{i,j}}\times f_{i,j}\to f_{i+1,j}\) 和 \(f_{i,j+1}\)。

那对于没填好的序列呢，怎么办？
统计下未确定的点的总数为 \(m\)。
设 \(f_{i,j,k,a,b}\) 表示到点 \((i,j)\)，已经钦定了 \(k\) 个未确定的标记点的位置，且当前状态下行 \(i\) (\(a=0\Leftrightarrow\) 没有标记点 / \(a=1\Leftrightarrow\) 有标记点)，列 \(j\) (\(b=0\Leftrightarrow\) 没有标记点 / \(b=1\Leftrightarrow\) 有标记点)的方案数。
显然有

\[+f_{i,j,k,a,b}\to f_{i+1,j,k,row_{i+1},b} \]

\[+f_{i,j,k,a,b}\to f_{i,j+1,k,a,line_{j+1}} \]

当 \(a=0,b=0\) 时

\[-f_{i,j,k,a,b}\to f_{i+1,j,k+1,row_{i+1},1} \]

\[-f_{i,j,k,a,b}\to f_{i,j+1,k+1,1,line_{j+1}} \]

最后答案

\[ans=\sum_{i=0}^mf_{n+1,n+1,i,0,0}\times (m-i)! \]

没有然后了。
浇浇计数题QWQ

ARC118E代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=  0, f=  1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 210, mod = 998244353;
int f[maxn][maxn][maxn][2][2];
int n, a[maxn], m,fac[maxn];
bool lim[maxn][maxn],line[maxn],row[maxn];
signed main(){
    fac[0] = 1; n = read();
    for(int i = 1;i <= n;i++)a[i] = read();
    for(int i = 1;i <= n;i++){
        fac[i] = fac[i - 1] * i % mod;
        if(a[i] != -1){
            m++; lim[i][a[i]] = line[a[i]] = row[i] = 1;
        }
    }
    m = n - m;int *x;
    f[0][0][0][1][1] = 1;
    for(int i = 0;i <= n + 1;i++)for(int j = 0;j <= n + 1;j++)
        for(int k = 0;k <= m;k++)
            for(int a = 0;a < 2;a++)for(int b = 0;b < 2;b++){
                int t = f[i][j][k][a][b];if(!t || lim[i][j])continue;
                if(!lim[i + 1][j]){
                    x = &f[i + 1][j][k][row[i + 1]][b];
                    *x += t;if(*x > mod)*x -= mod;
                }
                if(!lim[i][j + 1]){
                    x = &f[i][j + 1][k][a][line[j + 1]];
                    *x += t;if(*x > mod)*x -= mod;
                }
                if(a || b)continue;

                if(!lim[i + 1][j]){
                    x = &f[i + 1][j][k + 1][row[i + 1]][1];
                    *x -= t;if(*x < 0)*x += mod;
                }
                if(!lim[i][j + 1]){
                    x = &f[i][j + 1][k + 1][1][line[j + 1]];
                    *x -= t;if(*x < 0)*x += mod;
                }
            }
    int ans = 0;
    for(int i = 0;i <= m;i++){ans = (ans + f[n + 1][n + 1][i][0][0] * fac[m - i]) % mod;}
    printf("%lld\n",ans);
    return 0;
}