CF819D 题解

· · 题解

复读一遍 CF 题解。的确是一种非常妙的理解方式。

考虑同一个天文学家会在那些 \text{mod} \ T 的时间下观测。

显然，如果设 st_i =(\sum_{j=2}^ia_j)\bmod T,S = \sum_{j=1}^na_j，那么 i 这位天文学家只会在 (st_i+kS)\bmod T,k\in N 这些时间时观测。

接下来考虑如何统计答案，我们考虑每一位天文学家会第一次“到达”哪些余数。

考虑挖掘一点性质，我们来将每一个天文学家的路径转化到图上。

如果我们把每一个余数 x 看做图上的一个点，向 (x+S)\bmod T 连边的话，通过剩余系那套理论不难证明：

既然被划成了若干个环，那我们来考虑多个天文学家在同一个环中的答案情况。

首先，如果有多个天文学家的 st_i 相等，显然除了最前面那位答案都是零。

图画出来也不难发现，每一个天文学家的答案就是它沿着环的方向到环上的下一个天文学家的距离（如果环内只有一个点就是环的大小）。

现在的问题在于，如何求出上面所说的那个距离。

我们考虑给每个环定义一个起始点，下标为 0，其他的点这样顺次编号过去，这样距离就被转化成了编号之差。

很明显，每个环的起始点选 t,0\le t<\gcd(S,T) 是非常靠谱的，因为这样其他所有环内的点都可以被表示为 (t+kS)\bmod T,k\in N。

如何求出某个余数 x 在环内的编号？使用上面写出的形式，即得到

(x\bmod \gcd(S,T))+kS\equiv x (\bmod\ T)

的最小自然数解，用 exgcd 求解这个同余方程即可。

最后遍历每一个环，对每一个天文学家求出答案就完了。

代码：

注意特判一个环中只有一个天文学家的情况。

#include <map>
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long ll;
const int maxn = 2e5+5;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll st[maxn],S,d,x,y;
int n,T,a[maxn],ans[maxn];
struct pair{
    int pos,id;
    pair(int X=0,int Y=0):pos(X),id(Y){};
    bool operator <(pair b)const{return pos<b.pos;}
};
std :: map<int,bool> vis;
std :: map<int,std::vector<pair>> cys;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b)return x=1,y=0,void();
    exgcd(b,a%b,x,y);ll t = x;
    x = y,y = t-y*(a/b);
}
int main(){
    scanf("%d %d",&T,&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    st[1] = 0;for(int i=2;i<=n;++i)st[i] = (st[i-1]+a[i])%T;
    S = (st[n]+a[1])%T,d = gcd(S,T);
    for(int i=1;i<=n;++i){
        if(!vis[st[i]]){
            vis[st[i]] = 1;
            exgcd(S,T,x,y),x *= (st[i]-st[i]%d)/d,y *= (st[i]-st[i]%d)/d;
            x = (x%(T/d)+T/d)%(T/d),cys[st[i]%d].push_back(pair(x,i));
        }
    }
    std :: map<int,std::vector<pair>> :: iterator it = cys.begin();
    for(;it != cys.end();++it){
        std :: sort(it->second.begin(),it->second.end());
        std :: vector <pair> :: iterator It = it->second.begin(),nxt = It;
        while(++nxt,nxt != it->second.end())ans[It->id] = nxt->pos-It->pos,It = nxt;
        --nxt,ans[nxt->id] = (it->second.size()==1?T/d:(it->second.begin()->pos-nxt->pos+(T/d))%(T/d));
    }
    for(int i=1;i<=n;++i)printf("%d ",ans[i]);
    return 0;
}