CFR534

CFR534 div1

CF1103A

题意:看问答页面的补充

code

CF1103B Game with modulo

题意:交互题。猜出$a \in [1,1e9]$,不超过60次询问$(x,y),x,y \in [0,2e9],返回x \% a和y \%a是 \ge 还是<$

请先思考后再展开

首先$ask(a-1 \ge a)等价于mod|a$,这点很显然

然后如果$l<r,ask(l \ge r)等价于(l,r]内有mod的倍数$

(期望可能是2)+30+(分解质因数后对每种质因子分别做二分)次的考场做法:随机出一对$l<r,ask(l \ge r)$,然后发现一定能让$l或r=\frac{l+r}{2}$,缩小到具体数后分解质因数判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char str[N];bool cmp(int x,int y){ printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",str);if(str[0]=='e')exit(1);return str[0]=='x'; }
bool chk(int m){return cmp(m-1,m);}
void main()
{
while(1)
{
scanf("%s",str+1);if(strcmp(str+1,"start")!=0) return;
int x,y;while(1){ x=rd(0,M-1),y=rd(x+1,M);if(cmp(x,y)) break; }
while(x+1!=y){ int m=(1ll*x+y)/2;if(cmp(x,m)) y=m; else x=m; }
int m=x+1,ans=x+1;fo(d,2,sqrt(m)) if(m%d==0){
int z=0;while(m%d==0) m/=d,z++;int ret=z;
for(int l=0,r=z-1;l<=r;){ int mid=(l+r)/2;if(chk(ans/qpower(d,z-mid))) ret=mid,r=mid-1; else l=mid+1; }
ans/=qpower(d,z-ret);
} if(m>1 and chk(ans/m)) ans/=m;
printf("! %d\n",ans);fflush(stdout);
}
}

60次的做法1:从$l=0,r=1$开始,失败就$l=r,r*=2$,找到第一个$ask(l \ge r)$的区间,此时显然有$r<2mod$(经典trick),因此可以像上面那样二分

CF1103C Johnny Solving

题意:$n \le 2.5e5点m \le 5e5边$,连通简单无向图(保证每个点度数大于等于3)和一个限制k,需要你构造以下两种情况中的一种:

  1. 找出一条路径,$点数\times k \ge n$
  2. 找出k个环,使得每个环的长度大于3而且不是3的倍数,并且要求保证每个环中至少有一个点在这k个环里只出现一次
请先思考后再展开

刚开始看题的时候内心想法:这种题,肯定是非A即B,找个简单的,另一个在限制下一定存在

然后看到有无解:哦,那应该是找个简单的,另一个复杂度会很低

看题解:原来没无解啊,老千层饼了,虽然好像以前也碰到过写着-1然后没无解来着……


搞个dfs生成树,如果树高<n/k,$叶子数 \ge n/(n/k) \ge k$,以每个叶子作为代表点;因为没有横叉边,至少的两条边都连向祖先,

如果$d_x-d_A+1和d_x-d_B+1$都是3的倍数,则$|d_A-d_B|是3的倍数,因此可以形如x-A..B-x$。code

CF1103D Professional layer

题意:$n \le 1e6$个正整数二元组$(a_i \le 1e12 ,b_i \le 1e9 )$,给定正整数$K \le 1e12$,选出若干个二元组,将他们的a除以a的一个约数$d \le K$,最小化$(\sum [选i])*(\sum [选i] b_i)$且能使得最后$gcd(a_i)=1$。无解-1

请先思考后再展开

求出有z种公共质因子,那么我们要选出若干个(显然不超过z个)数对他们做修改,然后搞定了的质因子集的并为全集

无脑设$dp(i,S,cnt)=前i个二元组选了cnt个,已去除的公共质因子集为S,的最小bi和$,无脑做就是$O(z3^zn)$

注意到每个数的其他质因子可以直接去掉,剩下每种数只需要保留b前z小。

类似的,对于某次要去除的质因子集S,那么在能搞定S的数中只有b前z小的数才有资格用这个S转移。

因为z大了剩下的数会少,函数比较复杂就没有写暴力算极值,所以上面这部分复杂度略过

dp时上面的方程不用改,每次枚举这个数可用转移的补集子集,这部分不会超过$O(z3^z*z)$

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
map< ll,vc<int> > num;
pll a[N];ll f[15][1<<15],g[15][1<<15];vc<int> can[N];
void main()
{
ll n=qread(),K=qread(),D=0;fo(i,1,n) a[i].FR=qread(),D=gcd(D,a[i].FR);fo(i,1,n) a[i].SE=qread();
vc<ll> pr;for(ll d=2;d*d<=D;d++) if(D%d==0) { pr.PB(d);while(D%d==0) D/=d; } if(D>1) pr.PB(D); int z=sz(pr);
fo(i,1,n){ ll nw=1;for(auto p:pr) while(a[i].FR%p==0) a[i].FR/=p,nw*=p; num[nw].PB(a[i].SE); }
n=0;for(auto i:num) {sort(all(i.SE));fo(j,0,sz(i.SE)-1) if(j<z) a[++n]={i.FR,i.SE[j]};}
fo(s,1,bin(z)-1)
{
priority_queue<pii> q;
fo(i,1,n)
{
ll ss=1,now=a[i].FR;fo(i,0,z-1) if(s&bin(i)) while(now%pr[i]==0) now/=pr[i],ss*=pr[i];
if(ss<=K){ if(sz(q)<z) q.push({a[i].SE,i}); else if(q.top().FR>a[i].SE) q.pop(),q.push({a[i].SE,i}); }
}
while(sz(q)) can[q.top().SE].PB(s),q.pop();
}
mem(f,0x3f);f[0][0]=0;
fo(i,1,n) if(sz(can[i]))
{
fo(ct,0,z) fo(s,0,bin(z)-1) g[ct][s]=f[ct][s];
fo(ct,0,z-1) for(auto ad:can[i]) for(auto s=ad;s<bin(z);s=(s+1)|ad) chmin(f[ct+1][s],g[ct][s^ad]+a[i].SE);
}ll ans=bin(62);fo(ct,0,z) if(f[ct][bin(z)-1]<f[0][1]) chmin(ans,ct*f[ct][bin(z)-1]);write(ans>=bin(62)?-1:ans);
}

CF1103E Radix sum

题意:给出$n \le 1e5$个数$\in [0,1e5)$,$\forall i \in [0,n-1],输出放回地取n次数得到的十进制不进位和=i的方案数$。模数$2^{58}$

请先思考后再展开

题意看起来是个k进制FWT,但是模数等条件并没有直接满足

首先是要除以$10^5$,因为5有逆元不用管,因为答案一定是个整数,给倍数放大$2^5$,最后模意义结果一定是$2^5$的倍数,具体实现时可以直接用ull($inv(5)=14757395258967641293ull$)

然后是$w_K=g^{\frac{mod-1}{K}}$这个式子不能用,要另寻出路。考虑扩域,用$A(x)=\sum_{i=0}^{9} a_ix^i \pmod {x^{10}-1}存储,ans=A(w_{10})$

并没有保证每种数只有唯一表示

但对于单位根多项式数域,0的表示感受一下应该是各系数相等,那么每个数的不同表示就是加若干个0

答案一定整数,那么我们FWT求出来的结果,可以轻松消成只有常数项的形式

具体实现时,$w_{10}^1=-w_{10}^6=-w_{5}^3$,在$\pmod {x^{5}-1}$意义下做,这样常数小不少

严谨的代数证明例如foreverlastingMr.Spade,做法可能稍微有不同,本质上是一样的

复杂度是$O(k^{n+1}n*5^2)$

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
ull t[10];struct Num
{
ull a[5];Num(){mem(a,0);}
ull& operator [] (int x){return a[x];}
void operator += (Num b){ fo(i,0,4) a[i]+=b[i]; }
void operator *= (ull b){ fo(i,0,4) a[i]*=b; }
Num operator * (Num b){ mem(t,0);fo(i,0,4) if(a[i]) fo(j,0,4) if(b[j]) t[i+j]+=a[i]*b[j];Num c;fo(i,0,4) c[i]=t[i]+t[i+5];return c; }
friend Num operator ^ (Num x,ull e){ Num ans;ans[0]=1;while(e){ if(e&1)ans=ans*x;x=x*x;e>>=1; } return ans; }
};
namespace kFWT
{
const int K=10,M=100000;Num B[M];
Num omega[K*K];void pre(){ omega[0][0]=1;omega[1][3]=-1;fo(i,2,K*K-1) omega[i]=omega[i-1]*omega[1]; }
void FWT(Num A[],int op=0)
{
for(int w=1;w<M;w*=K)
{
for(int up=0;up<M;up+=w*K)//枚举高位和低位
for(int i=0,ii=up;i<K;i++,ii+=w) for(int j=0,jj=up;j<K;j++,jj+=w)
{ Num om=omega[op?K-i*j%K:i*j%K];for(int dw=0;dw<w;dw++) B[ii+dw]+=om*A[jj+dw]; }
fo(x,0,M-1) A[x]=B[x],B[x]*=0;
}
}
};Num A[N];
void main()
{
int n=qread();fo(i,1,n) A[qread()][0]++;kFWT::pre();kFWT::FWT(A);
fo(i,0,kFWT::M-1) A[i]=A[i]^n;kFWT::FWT(A,1);
fo(x,0,n-1)
{
ull num=A[x][0]-A[x][1];fo(i,1,3) assert(A[x][i]==A[x][i+1]);
num*=6723469279985657373ull;//(inv5)^5
assert(num%bin(5)==0);write1(num/bin(5)%bin(58));
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/79c6055f.html
转载请注明出处,谢谢!