CF_#421(Div. 1)_D

题目传送门
题意:
外星球每隔T秒中只有一秒可以被观测到,其它T-1秒无法被观测。n个天文学家(分别编号为1,…,n)轮流观测天空1秒,且第i+1个科学家在第i个天文学家后ai+1秒后才执行观测,而第一个天文学家则在第n个天文学家后a1秒后才执行观测,且第一个天文学家在0秒时执行第一次观测(即第一个天文学家观测的时间是[0,1),第二个科学家在[a2,a2+1)时观测,而最后一个天文学家在[a2+a3+…+an-1,a2+a3+…+an-1+1)时观测,之后再过a1秒后第一个天文学家继续观测)。

由于外星球具体在首次观测之后的T秒中的哪一秒出现是不确定的,若外星球在[i,i+1)时出现(0<=i<T-1),且天文学家j是首个观测到星球的人,则称j抢占了[i,i+1)时间片段。
已知T,n,a1,….,an其中(1<=T<=1e9,1<=n<=1e5,1<=a1,…,an<=1e9)。输出每个天文学家所抢占的时间片段数。

解法:
把n个科学家分成多个组,每组的人的观测的时间点集合在模T之后是相同的,那么他们就构成了一个环,我们只需要对每个组排序,然后就可以愉快的算出各个科学家的时间片段数了。如何确定这名科学家在哪一组和组内的排序依靠建立同余方程,并用裴蜀定理和扩展欧几里德求解。
懒得写了具体实现不如看官方题解233

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//created by missever
#include<bits/stdc++.h>
#define MAX 1000000007
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int maxn = 2e5 + 5;
int a[maxn],tot,mm,ans[maxn];
vector<P> g[maxn];
unordered_map<int,int> mp;
void extend_Euclid(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
extend_Euclid(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - (a / b) * y;
}
int get_modans(int a,int m,int b)
{
if(a == 0) return 0;
if(b == 0) return 0;
int d = __gcd(a,m);
int x,y;
extend_Euclid(a / d,m / d,x,y);
x = 1LL * x * b / d % m;
x = (x % m + m) % m;
x %= mm;
return x;
}
bool cmp(const P &a,const P &b){
if(a.first == b.first) return a.second > b.second;
else return a.first < b.first;
}
void solve(vector<P> &f){
int n = f.size();
sort(f.begin(),f.end(),cmp);
f.push_back(P(mm + f[0].first,0));
for(int i = 0;i < n; i++) ans[f[i].second] = f[i + 1].first - f[i].first;
}
int main(){
int t,n,i;
scanf("%d%d",&t,&n);
scanf("%d",&a[n]);
for(i = 1;i < n; i++) scanf("%d",&a[i]);
for(i = 1;i <= n; i++){
a[i] %= t;
a[i] += a[i - 1];
if(a[i] >= t) a[i] -= t;
}
int k = __gcd(a[n] + t,t);
mm = t / k;
for(i = 0;i < n; i++){
int x = a[i] % k;
if(mp[x] == 0) mp[x] = ++tot;
g[mp[x]].push_back(P(get_modans(a[n],t,(a[i] - x + t) % t),i));
}
for(i = 1;i <= tot; i++) solve(g[i]);
for(i = 0;i < n; i++) printf("%d ",ans[i]);
return 0;
}