Top

2019 Wannafly Camp day3


自闭感受

参加Camp的第三天,上午是数据结构专题分享,dls 不打CF,分数可能比我们都低的2300分只打过三场的巨巨队友 wls来给我们讲的​ ​​ 。比起昨天的数论专场,今天感觉好多了,懵逼少很多还能跟上节奏。wls是带着题目来给我们讲常见的数据结构运用,比如堆,并查集,线段树,平衡树等等。下午原本以为是数据结构专题训练,便戏耍的和lyy说下午你专场我回去了哈 ​ 。结果下午题目比day1,day2还难,而且不是想象中的数据结构专题。一开始我便瞄到了F题,好眼熟!!!这不是莫比乌斯反演吗?就开始怼了。lyy开了D,结果这​ SB不会写,我先放了下F题,看了下G题发现G题是个签到题 (上面写的) 。我就叫他看G,然后我切回了我的F。一波推式子,发现思路可行就巴拉巴拉敲了起来,中间因为炸int问题wa了几发,SB了!队友G题比我先过了,确实是个签到题​ ​​。最后有个乌龙,4点多的样子,队友和旁队的一起随机猜吧A题(因为只有2组数据,一共就1024种情况),竟然A了,然后大喊了一声答案,果断一波A的AC流。不知道出题人看到会心咋想

感受:非常难得场上A出一道正儿八经的数论反演题,开森,同时发现队伍配合实在差,必须好好抓抓,不然要GG,尤其新人。

上题解(后期补题会更新其他能力范围内的题解)

F - 小清新数论

做法一:欧拉函数

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1e7+9;
const LL mod = 998244353;
LL phi[maxn],miu[maxn],fac[maxn];//phi--欧拉函数表 miu--莫比乌斯函数表 fac--i最大的素因子辅助打phi表
void init()
{
for (int i = 1; i < maxn; ++i) fac[i] = i;
phi[1] = miu[1] = 1;
for (int i = 2; i < maxn; ++i)
{
if (fac[i] == i)
for (int j = i << 1; j < maxn; j += i)
fac[j] = i;
if (i / fac[i] % fac[i]) phi[i] = (fac[i] - 1)*phi[i / fac[i]], miu[i] = -miu[i / fac[i]]; //如果b质数 a%b!=0 phi(a*b) = phi(a)*b - phi(a)
else phi[i] = fac[i] * phi[i / fac[i]], miu[i] = 0; //当b是质数,a%b==0,phi(a*b)=phi(a)*b
}
for(int i=1;i<maxn;i++)phi[i]=phi[i]+phi[i-1];
}
int main(){
init();
LL n;
cin>>n;
LL NN=n;
LL ans=0;
for(LL i=1;i<=NN;i++){
LL res=(phi[NN/i]*(LL)2-1)%mod;
ans=(ans+miu[i]*res%mod)%mod;
while(ans<0)ans+=mod;
}
printf("%lld\n",ans);
}

做法二:莫比乌斯反演

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int maxn=1e7+1;
ll phi[maxn],miu[maxn],vis[maxn];
void init(){
for(int i=1;i<maxn;++i)vis[i]=i;
phi[1]=miu[1]=1;
for(int i=2;i<maxn;i++){
if(vis[i]==i){
for(int j=i<<1;j<maxn;j+=i)vis[j]=i;
}
if(i/vis[i]%vis[i])miu[i]= -miu[i/vis[i]];
else miu[i]=0;
}

for(int i=1;i<maxn;i++)miu[i]=miu[i]+miu[i-1];
}
ll solve(int n,int m){
ll ans=0;
int N=min(n,m),r;
for(int l =1;l<=N;l=r+1){
r=min(n/(n/l),m/(m/l)); //取分块小的数
ll res=(miu[r]-miu[l-1]+mod)%mod*(n/l)%mod*(n/l)%mod; //miu[r]-miu[l-1]表示l~r区间miu和,
ans=(ans+res+mod)%mod;
}
return ans;
}
int main(){
init();
int n,r;
scanf("%d",&n);
ll ans=0,res;
for(int l=1;l<=n;l=r+1){
r=n/(n/l);
res=(miu[r]-miu[l-1]+mod)%mod*solve(n/l,n/l)%mod;
ans=(ans+res+mod)%mod;
}
printf("%lld\n",ans);
return 0;
}

做法三:杜教筛能过div1,跑了1423ms,对做法一中欧拉函数前n项和,欧拉函数前n项和进行杜教筛,然后套一个分块求解

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
74
75
#include<stdio.h>
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define INV2 499122177
using namespace std;
typedef long long ll;
const int N=1e7+20;
const int mod=998244353;
bool vis[N];
int mu[N],sum1[N];
long long phi[N],sum2[N];
int cnt,prim[N];
int e,e1;
tr1::unordered_map<long long,long long>w,w1; //哈希 w用来求phi前缀和 w1用来求miu前缀和
void get(int maxn)
{
phi[1]=mu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!vis[i])
{
prim[++cnt]=i;
mu[i]=-1;phi[i]=i-1;
}
for(int j=1;j<=cnt&&prim[j]*i<=maxn;j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
else mu[i*prim[j]]=-mu[i],phi[i*prim[j]]=phi[i]*(prim[j]-1);
}
}
for(int i=1;i<=maxn;i++)sum1[i]=sum1[i-1]+mu[i],sum2[i]=(sum2[i-1]+phi[i])%mod; //打一个maxn的phi前缀和表 和miu前缀和表
}
int djsmu(long long x) // 求miu前缀和
{
if(x<=10000000)return sum1[x];
if(w[x])return w[x];
int ans=1;
for(long long l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1ll)*djsmu(x/l);
}
return w[x]=ans;
}
long long djsphi(long long x) //求phi 前缀和
{
if(x<=10000000)return sum2[x];
if(w1[x])return w1[x];
long long ans=x%mod*(x+1)%mod*INV2%mod;
for(long long l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans=(ans-(r-l+1)%mod*djsphi(x/l)+mod)%mod;
}
while(ans<0)ans+=mod;
return w1[x]=ans%mod;
}
int main(){
get(10000000);
ll n,r;
scanf("%lld",&n);
ll ans=0,res;
for(ll l=1;l<=n;l=r+1){
r=n/(n/l);
res=(ll)(djsmu(r)-djsmu(l-1)+mod)%mod*((djsphi(n/l)%mod*(ll)2%mod-1+mod)%mod)%mod;
ans=(ans+res+mod)%mod;
}
printf("%lld\n",ans);
return 0;
}

G - 排列**

搞清楚每个数组都是干什么的。

  • P 原数组
  • Ap 前缀数组
  • q Ap中第i大的位置(相同的先取左边,例如 AP={2,1, 1},第1小的位置是2而不是3.)

现在题目给了q,可以根据q倒推出Ap,然后倒推出P

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
include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn =1e5+10;
int a[maxn];
int q[maxn];
int main(){
int n;
scanf("%d",&n);
int cnt=0;
int pre=maxn+10;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>pre)
q[a[i]]=cnt;
else
q[a[i]]=++cnt;
pre=a[i];
}
cnt=q[1];
printf("%d ",cnt);
for(int i=2;i<=n;i++){
if(q[i]<q[i-1])
printf("%d ",q[i]);
else{
printf("%d ",++cnt);

}
}
return 0;
}