AtCoder Beginner Contest 212

F - Greedy Takahashi

题意

有 $n$ 座城市， $m$ 辆公交车。第 $i$ 辆公交车从 $a_i$ 开往 $b_i$ ，出发时间为 $s_i+0.5$ ，到达时间为 $t_i+0.5$ 。当高桥到达某座城市时，他会等待直到第一辆公交车到达，并坐上这辆公交，如果没有公交车到达，则留在这座城市（保证公交车的到达时间各不相同）。有 $q$ 组询问，每组 $(x,y,z)$ 表示高桥如果在 $y$ 时间到达 $x$ 城市，在 $z$ 时间会在哪里。如果在公交车上，输出公交车的起点和终点，否则输出所在城市。

数据范围： $n,m,q\leq 10^5$ 。

题解

对于每个城市，高桥的最终位置与到达城市的时间有关。但我们考虑每辆公交车，高桥的最终位置就被确定了。可以利用倍增维护：记 $f_{i,j}$ 表示第 $i$ 辆公交车后乘坐的第 $2^j$ 辆公交车的编号， $f_{i,0}$ 即到达第 $i$ 辆公交车的终点后乘坐的第一辆公交车的编号。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+5;
vector<pii> g[N];
struct edge
{
    int a,b,s,t;
}e[N];
int f[N][25];
int get(int u,int val)
{
    auto it=lower_bound(g[u].begin(),g[u].end(),make_pair(val,0));
    if(it==g[u].end()) return -1;
    else return it->second;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int a,b,s,t;cin>>a>>b>>s>>t;
        e[i]={a,b,s,t};
        g[a].push_back({s,i});
    }
    for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
    memset(f,-1,sizeof(f));
    for(int i=1;i<=m;i++) f[i][0]=get(e[i].b,e[i].t);
    for(int j=0;j<20;j++)
        for(int i=1;i<=m;i++)
            if(f[i][j]!=-1) f[i][j+1]=f[f[i][j]][j];
    while(q--)
    {
        int x,y,z;cin>>x>>y>>z;
        int u=get(y,x);
        if(u==-1||z<=e[u].s) 
        {
            cout<<y<<'\n';
            continue;
        }
        for(int j=20;j>=0;j--)
            if(f[u][j]!=-1&&e[f[u][j]].s<z) u=f[u][j];
        if(z>e[u].t) cout<<e[u].b<<'\n';
        else cout<<e[u].a<<' '<<e[u].b<<'\n';
    }
    return 0;
}

G - Power Pair

题意

求满足

$0\leq x,y\leq p-1$
存在正整数 $n$ ，使得 $x^n\equiv y\pmod p$

的 $(x,y)$ 的对数，结果对 $998244353$ 取模。

数据范围： $2\leq p\leq 10^{12}$ ， $p$ 是质数。

题解

根据阶的定义，要求的就是

1+\sum_{i=1}^{p-1}\delta_p(i)

对于质数 $p$ 有 $\delta_p(x)=\dfrac{\varphi(p)}{\gcd(\varphi(p),x)}$ ，则原式可化为

1+\sum_{i=1}^{p-1}\dfrac{\varphi(p)}{\gcd(\varphi(p),i)}

令 $n=p-1$ ，则

\begin{aligned} &=1+\sum_{i=1}^n\dfrac{n}{\gcd(n,i)}\\ &=1+\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}\frac{n}{d}[\gcd(n,i\times d)=d]\\ &=1+\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}\frac{n}{d}[\gcd(\frac{n}{d},i)=1]\\ &=1+\sum_{d|n}\frac{n}{d}\varphi(\frac{n}{d})\\ &=1+\sum_{d|n}d\varphi(d) \end{aligned}

然后枚举对 $n$ 作质因数分解，根据定义求 $\varphi(d)$ 就做完了。

另一种理解方式是借助原根：设 $p$ 的原根为 $g$ ，令 $x=g^a,y=g^b$ ，则 $x^n\equiv y\pmod p$ 可写作 $g^{na}\equiv g^b\pmod p$ ，即 $na\equiv b\pmod {p-1}$ 。这个问题就相当于，在一个长度为 $p-1$ 的环上每次走 $a$ 步，一共会到达多少个不同的点。这是一个经典问题，答案是 $\dfrac{p-1}{\gcd(p-1,a)}$ 。剩下的推导同上。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=998244353;
ll phi(ll x)
{
    ll ans=x;
    for(ll i=2;i*i<=x;i++)
        if(x%i==0)
        {
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    n--;
    ll ans=1;
    for(ll i=1;i*i<=n;i++)
        if(n%i==0) 
        {
            ans=(ans+(__int128)i*phi(i))%p;
            if(i*i!=n) ans=(ans+(__int128)n/i*phi(n/i))%p;
        }
    cout<<ans<<'\n';
    return 0;
}

H - Nim Counting

题意

给定 $n,k$ ，给出 $k$ 个数 $a_1,a_2,\cdots,a_k$ 。每次可以选定一个数 $m$ 满足 $1\leq m\leq n$ ，并选定 $m$ 堆石子，每堆石子的数量在 $a$ 中。求所有先手必胜的方案数，结果对 $998244353$ 取模。

数据范围： $1\leq n\leq 2\times10^5,1\leq k<2^{16},1\leq a_i< 2^{16}$ 。

题解

令 $F=\sum\limits_{i=1}^kx^{a_i}$ ，则答案为 $\sum\limits_{w>0}[x^w]\sum\limits_{i=1}^nF^i$ ，其中 $x^a\ op\ x^b=x^{a\oplus b}$ 。

考虑 $G=F^2$ ，则

g_k=\sum_{i\oplus j=k}f_if_j

所以这就是异或卷积，为了求出 $F^i$ 每项的系数，可以先做一遍 FWT，然后快速幂，最后再 IFWT 回去就好了。又由于 $FWT(A+B)=FWT(A)+FWT(B)$ ，最终每项的系数就是 $\dfrac{F-F^{n+1}}{1-F}$ 。

代码

#include<algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
const int mod=998244353;
const int inv2=499122177;
const ll
Cor[2][2]={{1,0},{1,1}},
Cand[2][2]={{1,1},{0,1}},
Cxor[2][2]={{1,1},{1,mod-1}},
ICor[2][2]={{1,0},{mod-1,1}},
ICand[2][2]={{1,mod-1},{0,1}},
ICxor[2][2]={{inv2,inv2},{inv2,mod-inv2}};
ll fpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void FWT(ll *F,const ll c[2][2],int n)
{
    for(int len=1;len<n;len<<=1)
        for(int p=0;p<n;p+=len+len)
            for(int i=p;i<p+len;i++)
            {
                ll sav0=F[i];
                F[i]=(c[0][0]*F[i]+c[0][1]*F[i+len])%mod;
                F[i+len]=(c[1][0]*sav0+c[1][1]*F[i+len])%mod;
            }
}
void bitmul(ll *F,const ll C[2][2],const ll IC[2][2],int n,int k)
{
    FWT(F,C,n);
    for(int i=0;i<n;i++)
    {
        if(F[i]==1) F[i]=k;
        else F[i]=(fpow(F[i],k+1)+mod-F[i])*fpow(F[i]+mod-1,mod-2)%mod;
    }
    FWT(F,IC,n);
}
ll f[N],g[N],a[N],b[N];
#define cpy(f,g,n) memcpy(f,g,sizeof(ll)*(n))
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        int x;cin>>x;
        f[x]=1;
    }
    cpy(a,f,(1<<16));
    bitmul(a,Cxor,ICxor,(1<<16),n);
    ll ans=0;
    for(int i=1;i<(1<<16);i++) ans=(ans+a[i])%mod;
    cout<<ans<<'\n';
    return 0;
}

ACM

#倍增 #阶与原根 #FWT

AtCoder Beginner Contest 212

https://je3ter.github.io/2023/11/14/ACM/AtCoder Beginner Contest 212/

作者

Je3ter

发布于

2023年11月14日

许可协议

AtCoder Beginner Contest 213 上一篇

AtCoder Regular Contest 154 D 下一篇