凡客官方网站,企业网站模板免费下载企业网站模板,怎样创建微网站,快速微信网站开发训练链接
CF645F
题目链接
点击打开链接
题目解法
一眼莫反 推式子的步骤就不写了#xff0c;反正也比较套路 这里只给出最后的式子为#xff1a; A n s ∑ i 1 V ϕ ( i ) ∗ ( ∑ i ∣ j c n t j k ) Ans\sum\limits_{i1}^{V}\phi(i)*\binom{\sum\limits_{i\mid j}c…训练链接
CF645F
题目链接
点击打开链接
题目解法
一眼莫反 推式子的步骤就不写了反正也比较套路 这里只给出最后的式子为 A n s ∑ i 1 V ϕ ( i ) ∗ ( ∑ i ∣ j c n t j k ) Ans\sum\limits_{i1}^{V}\phi(i)*\binom{\sum\limits_{i\mid j}cnt_j}{k} Ansi1∑Vϕ(i)∗(ki∣j∑cntj)其中 c n t j cnt_j cntj 为数字 j j j 的出现次数 修改操作的话根据式子不难得出只要修改 x x x 的因子即可 时间复杂度 O ( q n ) O(q\sqrt n) O(qn )
#include bits/stdc.h
using namespace std;
const int V1000000,N200100,P1e97;
int n,k,q,a[N];
int inv[V100],fac[V100];
int mu[V100],pr[V100],tot,v[V100];
int smu[V100],mi[V100],sum[V100],cnt[V100];
vectorint fact[V100];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int qmi(int a,int b){int res1;for(;b;b1){if(b1) res1ll*res*a%P;a1ll*a*a%P;}return res;
}
int C(int a,int b){if(ab) return 0;return 1ll*fac[a]*inv[b]%P*inv[a-b]%P;
}
int main(){mu[1]1;for(int i2;iV;i){if(!v[i]) v[i]i,pr[tot]i,mu[i]-1;for(int j1;jtotpr[j]V/i;j){v[i*pr[j]]pr[j];if(v[i]pr[j]) break;mu[i*pr[j]]-mu[i];}}fac[0]1;for(int i1;iV;i) fac[i]1ll*fac[i-1]*i%P;inv[V]qmi(fac[V],P-2);for(int iV-1;i0;i--) inv[i]1ll*inv[i1]*(i1)%P;nread(),kread(),qread();for(int i1;inq;i) mi[i]C(i,k);for(int i1;in;i) a[i]read(),cnt[a[i]];for(int i1;iV;i) for(int ji;jV;ji) sum[i]cnt[j],smu[j]((smu[j]mu[i]*(j/i))%PP)%P,fact[j].push_back(i);int ans0;for(int i1;iV;i) ans((ans1ll*smu[i]*mi[sum[i]])%PP)%P;for(int i1;iq;i){int xread();for(int d:fact[x]){ans((ans-1ll*smu[d]*mi[sum[d]])%PP)%P;sum[d];ans((ans1ll*smu[d]*mi[sum[d]])%PP)%P;}printf(%d\n,ans);}fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}CF1034C
题目链接
点击打开链接
题目解法
翻译有误 显然我们的问题是要求出这棵树分成 k k k 个部分是否可行如果可行令 f k 1 f_k1 fk1 那么只要做一遍 d p dp dp即可式子为 f i ∑ i ∣ j f j f_i\sum\limits_{i|j}f_j fii∣j∑fj注意 i , j i,j i,j 一定要是可行的
考虑如何求 f k f_k fk 我们先求一遍子树和令权值总和为 S S S那么需要割的边即为满足 S k ∣ s i \frac{S}{k}|s_i kS∣si 的子树和 我们需要判断需要割的边的个数是否 k k k 考虑如何快速求解上面的问题 s i a S k s_ia\frac{S}{k} siakS 则 k a S s i ka\frac{S}{s_i} kasiS 所以说如果 k k k 是 S ( S , s i ) \frac{S}{(S,s_i)} (S,si)S 的倍数那么 i i i 就会对 k k k 产生贡献直接扫一遍 S ( S , s i ) \frac{S}{(S,s_i)} (S,si)S 在 n n n 以内的倍数即可 时间复杂度 O ( n ln n ) O(n\ln n) O(nlnn)
#include bits/stdc.h
#define int long long
using namespace std;
const int N1000100,P1e97;
int n,v[N],fa[N],s[N],f[N];
int cnt[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
signed main(){nread();for(int i1;in;i) v[i]read();for(int i2;in;i) fa[i]read();for(int in;i1;i--) s[i]v[i],s[fa[i]]s[i];int tots[1];for(int i1;in;i){int gtot/__gcd(tot,s[i]);for(int jg;jn;jg) cnt[j];}for(int i1;in;i) if(icnt[i]) f[i]1;for(int in;i2;i--){if(!f[i]) continue;for(int jii;jn;ji) f[i](f[i]f[j])%P;}int ans1;for(int i2;in;i) ans(ansf[i])%P;printf(%lld\n,ans);fprintf(stderr,%d ms\n,int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}CF1603D
题目链接
点击打开链接
题目解法
首先可以发现当 k ≤ l o g 2 n k\le log_2^n k≤log2n 时答案一定为 n n n因为可以按照二进制的位数分组然后每组的 c c c 都为 1 1 1 现在只需要考虑 k ≤ 16 k\le 16 k≤16 的情况 我们令 f i , j f_{i,j} fi,j 为到 j j j 分成 i i i 段的最小值 看题解发现 f i , j f_{i,j} fi,j 对于每一层的 i i i 满足决策单调性所以可以直接分治解决 现在的问题是快速算出 c ( l , r ) c(l,r) c(l,r) 推式子 . . . ... ... 自己在草稿纸上推可以得出 c ( l , r ) ∑ i l r ∑ j 1 ⌊ r i ⌋ ϕ ( j ) c(l,r)\sum\limits_{il}^r\sum\limits_{j1}^{\lfloor\frac{r}{i}\rfloor}\phi(j) c(l,r)il∑rj1∑⌊ir⌋ϕ(j) 发现这很分块 具体来说的话可以算出 ϕ \phi ϕ 的前缀和然后分类讨论和累加 感觉是道挺妙的题但不太好讲自己去看题解吧讲的挺详细的 时间复杂度 O ( 16 n l o g n ) O(16nlogn) O(16nlogn)
#include bits/stdc.h
#define int long long
using namespace std;
const int K20,MAXB330,N100100,inf1e18;
int cur,phi[N],s[N],f[K][N];
int B320,g[N][MAXB],h[N][MAXB];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int calc_bl(int l,int r){int res0;for(int il;ir;i) ress[r/i];return res;
}
int calc(int l,int r){if(rB) return g[r][r]-g[r][l-1];else{int res0;if(lB) resg[r][B]-g[r][l-1];lmax(l,B1);int Ll,Rr/(r/l);resh[r][r/l-1](R-L1)*s[r/l];return res;}
}
void solve(int l,int r,int ql,int qr){if(lr) return;int mid(lr)1;int resinf,pos;for(int iql;imin(mid-1,qr);i)if(f[cur-1][i]!inff[cur-1][i]calc(i1,mid)res)resf[cur-1][i]calc(i1,mid),posi;f[cur][mid]res;solve(l,mid-1,ql,pos),solve(mid1,r,pos,qr);
}
void work(){int nread(),kread();if(k16||n(1k)) printf(%d\n,n);else printf(%lld\n,f[k][n]);
}
signed main(){for(int i1;iN;i){phi[i]i;int ti;for(int j2;j*jt;j) if(t%j0){while(t%j0) t/j;phi[i]phi[i]/j*(j-1);}if(t1) phi[i]phi[i]/t*(t-1);}for(int i1;iN;i) s[i]s[i-1]phi[i];for(int i1;iN;i) for(int j1;jB;j) g[i][j]g[i][j-1]s[i/j];for(int i1;iN;i) for(int j1;jB;j){int ri/j,li/(j1)1;h[i][j](r-l1)*s[j];}for(int i1;iN;i) for(int j1;jB;j) h[i][j]h[i][j-1];memset(f,0x3f,sizeof(f));f[0][0]0;for(int i1;i16;i) curi,solve(1,N-1,0,N-1);int Tread();while(T--) work();fprintf(stderr,%d ms\n,int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
CF1770F
题目链接
点击打开链接 感觉是一道很妙的题反正我是完全没思路
考虑题目中的和限制与或限制有很好的对称性那么不难发现 a 1 a_1 a1 的位置可以换到其他任何位置上那么当 n n n 为偶数的时候答案即为 0 0 0当 n n n 为奇数的时候答案为所有情况下 a 1 a_1 a1 的异或和因为异或可以抵消且 a 1 a_1 a1 可以换到任何一个位置那么当 n n n 为奇数时一定只会剩下一个位置未被抵消
首先一个朴素的想法是对 a 1 a_1 a1 分位计算那么现在我们需要求当 2 i ⊆ a 1 2^i\subseteq a_1 2i⊆a1 的满足条件的方案数的奇偶性 对于 或 操作具有比较好的性质只有可能从 0 0 0 变为 1 1 1所以我们考虑容斥求解 令 f y ′ ( y ′ ⊆ y ) f_{y}(y\subseteq y) fy′(y′⊆y) 为 ∀ a i ⊆ y ′ \forall a_i\subseteq y ∀ai⊆y′ 且 ∑ a i x \sum a_ix ∑aix 的方案数 所以方案数即为 ∑ y ′ ⊆ y ( − 1 ) ∣ y ∣ − ∣ y ′ ∣ f y ′ \sum\limits_{y\subseteq y}(-1)^{|y|-|y|}f_{y} y′⊆y∑(−1)∣y∣−∣y′∣fy′ 因为我们只关心奇偶性所以方案数可化简为 ∑ y ′ ⊆ y f y ′ \sum\limits_{y\subseteq y}f_{y} y′⊆y∑fy′ 需要满足 a i ⊆ y ′ a_i\subseteq y ai⊆y′ 的条件不好办所以我们考虑组合数逆用可得 a i ⊆ y ′ ⟺ ( y ′ a i ) ( m o d 2 ) a_i\subseteq y\iff \binom{y}{a_i}(\mod 2) ai⊆y′⟺(aiy′)(mod2) 把 f y ′ f_{y} fy′ 拆分开来即为 ∑ ∑ a i x − 2 i ( y − 2 i a 1 ) ( y a 2 ) . . . ( y a n ) \sum\limits_{\sum a_ix-2^i}\binom{y-2^i}{a_1}\binom{y}{a_2}...\binom{y}{a_n} ∑aix−2i∑(a1y−2i)(a2y)...(any) 用范德蒙德卷积化简可得 ( n y − 2 i x − 2 i ) ( m o d 2 ) [ ( x − 2 i ) ⊆ ( n y − 2 i ) ] \binom{ny-2^i}{x-2^i}(\mod 2)\\[(x-2^i)\subseteq(ny-2^i)] (x−2iny−2i)(mod2)[(x−2i)⊆(ny−2i)] 直接计算即可 时间复杂度 O ( y l o g y ) O(ylogy) O(ylogy)
#include bits/stdc.h
#define int long long
using namespace std;
int n,x,y;
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
signed main(){nread(),xread(),yread();if(n1){int ans0;for(int i0;i20;i)if(yi1)for(int yyy;;yy(yy-1)y){if(yyi1){int pn*yy-(1i),qx-(1i);if(p0q0(pq)q) ans^1i;}if(!yy) break;}printf(%lld\n,ans);}else puts(0);fprintf(stderr,%d ms\n,int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
CF1656H
题目链接
点击打开链接
题目解法
还是一道很妙的题可能是我太菜了 我们一开始把所有数都选入集合中然后考虑删数使两个集合的 l c m lcm lcm 相等 这个直接暴力查找删除即可即找到 a i ∤ ∏ b j a_i\nmid \prod b_j ai∤∏bj b j b_j bj 是仍在答案集合中的 一个判断 a i ∤ ∏ b j a_i\nmid \prod b_j ai∤∏bj 的直观想法是质因数分解然后看次幂但是 a i , b i ≤ 4 ∗ 1 0 36 a_i,b_i\le 4*10^{36} ai,bi≤4∗1036明显不够做任何的质因数分解算法 p o l l a r d − r h o pollard-rho pollard−rho 也跑不了 所以考虑换一个角度思考问题 这里有一个很妙的判断方法是 gcd ( a gcd ( a , b 1 ) , a gcd ( a , b 2 ) , . . . , a gcd ( a , b k ) ) \gcd(\frac{a}{\gcd(a,b_1)},\frac{a}{\gcd(a,b_2)},...,\frac{a}{\gcd(a,b_k)}) gcd(gcd(a,b1)a,gcd(a,b2)a,...,gcd(a,bk)a) k k k 为仍在答案集合中的数的个数上面这个式子分类讨论然后自己分析一下不难理解 因为 gcd \gcd gcd 是可合并的且需要支持修改所以考虑用线段树维护 考虑每次删除数只会修改另一个序列中的当前位置所以线段树只会修改 O ( n 2 ) O(n^2) O(n2) 次删除数的话直接把 gcd \gcd gcd 赋为 0 0 0 即可因为 gcd ( x , 0 ) x \gcd(x,0)x gcd(x,0)x 时间复杂度为 O ( n 2 l o g n l o g V ) O(n^2lognlogV) O(n2lognlogV)
#include bits/stdc.h
using namespace std;
const int N1100;
typedef __int128_t LL;
LL a[N],b[N];
setint A,B;
inline LL read(){LL FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FFFF*10ch-48;return FF*RR;
}
LL gcd(LL x,LL y){ return !y?x:gcd(y,x%y);}
void print(LL x){if(!x) return;print(x/10);putchar(x%1048);
}
struct SegmentTree{LL seg[N2];void modify(int l,int r,int x,int pos,LL v){if(lr){ seg[x]v;return;}int mid(lr)1;if(midpos) modify(l,mid,x1,pos,v);else modify(mid1,r,x1^1,pos,v);seg[x]gcd(seg[x1],seg[x1^1]);}LL ask(){ return seg[1];}
}sg[N1];
void work(){int n,m;scanf(%d%d,n,m);for(int i1;in;i) a[i]read();for(int i1;im;i) b[i]read();for(int i1;in;i) for(int j1;jm;j) sg[i].modify(1,m,1,j,a[i]/gcd(a[i],b[j]));for(int i1;im;i) for(int j1;jn;j) sg[in].modify(1,n,1,j,b[i]/gcd(b[i],a[j]));int lenAn,lenBm;A.clear(),B.clear();for(int i1;in;i) A.insert(i);for(int i1;im;i) B.insert(i);while(!A.empty()!B.empty()){setint del;del.clear();for(auto it:A)if(sg[it].ask()1){del.insert(it);lenA--;for(auto itt:B) sg[nitt].modify(1,n,1,it,0);}for(auto it:del) A.erase(it);bool flg(del.size()0);del.clear();for(auto it:B)if(sg[nit].ask()1){del.insert(it);lenB--;for(auto itt:A) sg[itt].modify(1,m,1,it,0);} for(auto it:del) B.erase(it);flg|(del.size()0);del.clear();if(!flg) break;}if(A.empty()||B.empty()) puts(NO);else{puts(YES);print(lenA);putchar( );print(lenB);putchar(\n);for(auto it:A) print(a[it]),putchar( );puts();for(auto it:B) print(b[it]),putchar( );puts();}
}
int main(){int T;scanf(%d,T);while(T--) work();fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
CF986F
题目链接
点击打开链接
题目解法
挺有意思的一道题感觉十分多合一 首先考虑到只有 k k k 的质因子是有用的因为合数因子一定可以表示成多个质因子相加 那么现在的问题变成了询问 n n n 是否是 p 1 , . . . , p m p_1,...,p_m p1,...,pm 的线性组合且每一项的系数需要非负 线性组合且非负我们第一个想到的问题应该是 P3403 跳楼机所以这道题我们可以套用那道题的做法用同余最短路做 但我们发现 p i p_i pi 很大最小的 p i p_i pi 甚至都不能做最短路所以我们考虑分类讨论 m 1 m1 m1直接判断 n n n 是否是 p p p 的倍数即可 m 2 m2 m2问题是需要判断是否存在 d 1 x d 2 y n d_1xd_2yn d1xd2yn 的非负整数解 如果 ( d 1 , d 2 ) ∤ n (d_1,d_2)\nmid n (d1,d2)∤n则无解考虑 ( d 1 , d 2 ) ∣ n (d_1,d_2)\mid n (d1,d2)∣n 的情况 问题等价于 d 2 y ≡ n ( m o d d 1 ) d_2y\equiv n (\mod d_1) d2y≡n(modd1) 的最小整数解 y y y 是否满足 y d 2 ≤ n yd_2\le n yd2≤n y y y 的最小整数解显然为 n × d 2 − 1 n\times d_2^{-1} n×d2−1 直接求逆元即可 m ≥ 3 m\ge 3 m≥3这类情况我们直接套用同余最短路的做法因为 ∏ p i ≤ 1 0 15 \prod p_i\le 10^{15} ∏pi≤1015且 m ≥ 3 m\ge 3 m≥3所以最小的 p i ≤ 1 0 5 p_i\le 10^5 pi≤105可以直接做最短路
我是直接暴力质因数分解的当然要先筛出质数也可以过 因为是多合一做法所以时间复杂度需要一个一个单独算我就不算了反正可以过
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int LIM31700000;
const int MAXT10100;
const LL inf2e18;
struct QUERY{ LL n,k;int id;}q[MAXT];
LL n,k;
int pr[LIM5],cnt;
bool del[LIM5],ans[MAXT];
vectorLL v;
void sieve(){for(int i2;iLIM;i){if(!del[i]) pr[cnt]i;for(int j1;jcntiLIM/pr[j];j){del[pr[j]*i]1;if(i%pr[j]0) break;}}
}
void sep(LL x){for(int i1;icnt1ll*pr[i]*pr[i]x;i)if(x%pr[i]0){v.push_back(pr[i]);while(x%pr[i]0) x/pr[i];}if(x1) v.push_back(x);
}
LL Gcd(LL x,LL y){if(!y) return x;return Gcd(y,x%y);
}
const int MNPR100100;
typedef pairLL,int pli;
priority_queuepli,vectorpli,greaterpli que;
int h[MNPR],ne[MNPR*20],e[MNPR*20],idx;
LL dis[MNPR],w[MNPR*20];
bool vis[MNPR];
void add(int x,int y,LL z){ e[idx]y,w[idx]z,ne[idx]h[x],h[x]idx;}
void dij(){dis[0]0,que.push(make_pair(0,0));while(!que.empty()){int uque.top().second;que.pop();for(int ih[u];~i;ine[i]){int ve[i];if(dis[u]w[i]dis[v]) dis[v]dis[u]w[i],que.push(make_pair(dis[v],v));}}
}
int qmi(LL a,int b,int P){a%P;int res1;for(;b;b1){if(b1) res1ll*res*a%P;aa*a%P;}return res;
}
int main(){sieve();int T;scanf(%d,T);for(int i1;iT;i){LL n,k;scanf(%lld%lld,n,k);q[i]{n,k,i};}sort(q1,qT1,[](const QUERY x,const QUERY y){ return x.ky.k;});for(int i1,j;iT;ij1){ji;while(q[j1].kq[i].k) j;if(q[i].k1) continue;v.clear();sep(q[i].k);if(v.size()1){LL dv[0];for(int xi;xj;x) if(q[x].n%d0) ans[q[x].id]1;continue;}if(v.size()2){LL d1v[0],d2v[1];for(int xi;xj;x){LL tq[x].n%d1*qmi(d2,d1-2,d1)%d1;if(t*d2q[x].n) ans[q[x].id]1;}continue;}idx0;for(int x0;xv[0];x) h[x]-1,dis[x]inf;for(int x0;xv[0];x) for(int t1;tv.size();t) add(x,(xv[t])%v[0],v[t]);dij();for(int xi;xj;x) if(dis[q[x].n%v[0]]q[x].n) ans[q[x].id]1;}for(int i1;iT;i) puts(ans[i]?YES:NO);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
