方城网站制作,苏州网站推广服务,国外做化学申报的网站,it外包公司排行榜比赛链接
反思
A
花了很长时间#xff0c;幸亏没怎么调就对了#xff0c;以后还是应该先看其他题的 括号匹配题的套路感觉没有掌握透#xff0c;感觉无非就是单调栈#xff0c;哈希#xff0c;折线图
B
感觉比 T 1 T1 T1 简单
C
正解还是很妙的#xff0c;但 68…比赛链接
反思
A
花了很长时间幸亏没怎么调就对了以后还是应该先看其他题的 括号匹配题的套路感觉没有掌握透感觉无非就是单调栈哈希折线图
B
感觉比 T 1 T1 T1 简单
C
正解还是很妙的但 68 p t s 68pts 68pts 的线段树优化建图很好拿但不太好写
D
感觉并不是那么难用 d p dp dp 化简多项式还是第一次见到
题解
A
考虑每个右括号只会匹配一个左括号于是我们可以进行类似 d p dp dp 的操作我们记录每段区间的 d p dp dp 值可以发现每段区间只会有一个位置的 d p dp dp 值 1 1 1其他都 1 1 1所以直接用单调栈维护即可 有些细节需要仔细想一下也说不清 时间复杂度 O ( n ) O(n) O(n)
#include bits/stdc.h
using namespace std;
typedef unsigned long long ull;
const int N10000100;
int n,x,y,z,m[2];
int c[N],lenth[N],f[N],top;
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 main(){freopen(brackets.in,r,stdin);freopen(brackets.out,w,stdout);nread(),xread(),yread(),zread(),m[0]read(),m[1]read(),c[0]read(),c[1]read();for(int i2;in;i) c[i](1ll*c[i-1]*x1ll*c[i-2]*yz)%m[i1]1;ull ans0,tmp0;for(int i0;in;i){if(~i1) top,lenth[top]c[i],f[top]tmp;else{tmp0;while(toplenth[top]c[i]){c[i]-lenth[top];anslenth[top]f[top];if(!c[i]) tmpf[top]1;top--;}if(topc[i]) lenth[top]-c[i],ansc[i],tmp1;}}printf(%llu\n,ans);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
B
用好 a i a_i ai 互不相同的性质发现只需要记录 f i , S f_{i,S} fi,S 表示到 i i i前一个与 a i a_i ai 的异或值为 S S S 的方案数 然后转移用前缀和优化可以到 O ( n 2 m ) O(n2^m) O(n2m) 但这样会考虑不到 i i i 前一个不合法的情况因为集合不相交所以直接减掉即可 时间复杂度 O ( n 2 m ) O(n2^m) O(n2m)
#include bits/stdc.h
using namespace std;
const int N4100,MAXS4100;
const int P998244353;
int n,m,s,a[N],rev[MAXS],f[N][MAXS],g[N],tot[N],sum[N][MAXS];
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;
}
inline void inc(int x,int y){ xy;if(xP) x-P;}
int main(){freopen(school.in,r,stdin);freopen(school.out,w,stdout);nread(),mread(),sread();for(int i1;in;i) a[i]read(),rev[a[i]]i;for(int i1;in;i){tot[i]tot[i-1];for(int S0;S1m;S) sum[i][S]sum[i-1][S];for(int S0;S1m;S){int jrev[S^a[i]];if(!j||ji) continue;f[i][S]((1ll*tot[j-1]-sum[j-1][s^S]-g[j])%PP)%P;inc(g[i],sum[j-1][s^S]);inc(tot[i],f[i][S]j),inc(sum[i][S],f[i][S]j);}}int ans(nn*(n-1)/21ll*n*(n-1)*(n-2)/6%P)%P;for(int i1;in;i) for(int S0;S1m;S) inc(ans,f[i][S]);printf(%d\n,ans);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
C
线段树优化建图的做法是显然的 考虑正解 我们假设我们有一张图每个点都是指向 1 1 1 个区间多个也没事且边权为 1 1 1我们是否可以不建出图 O ( n ) O(n) O(n) 求最短路 是可以的。我们只要用并查集维护这个点后面第一个未被访问到的点即可然后在 b f s bfs bfs 的过程中便可以合并并查集然后做到 O ( n ) O(n) O(n) 的复杂度并查集不算
但我们如何建出一个点指向区间的图呢 考虑做一个映射我们令 j j j 为 i d % n id\%n id%n把每个点归到类中去那么类 j j j 可以到 [ j − R , j − L ] [j-R,j-L] [j−R,j−L] 的每一个类这样就可以用上述方法 O ( n ) O(n) O(n) 计算了 感觉还是很妙的
#include bits/stdc.h
using namespace std;
const int N1000100,inf1e9;
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 dis[N1],ans[N];
int que[N],hh,tt;
int stk[N],hd,tl;
int fa[N];
int ne[N],h[N];
int get_father(int x){ return xfa[x]?x:fa[x]get_father(fa[x]);}
void insert(int l,int r,int Dist){for(int iget_father(l);ir;iget_father(i)){for(int uh[i];~u;une[u]) if(dis[u]inf) dis[u]Dist,que[tt]u;fa[i]get_father(i1);}
}
void work(){int nread(),dread(),Lread(),Rread(),qread();for(int i0;in;i) h[i]-1;for(int i0;in;i){int pos1ll*i*d%n;ne[i]h[pos],h[pos]i;}for(int i0;in;i) fa[i]i;int DR-L;for(int i0;in;i) dis[i]inf;hh0,tt-1;dis[0]0,que[tt]0;while(hhtt){int uque[hh];int t(u-Rn)%n;if(tDn) insert(t,tD,dis[u]1);else insert(t,n-1,dis[u]1),insert(0,D-(n-t),dis[u]1);}for(int i0;in;i) dis[in]dis[i];for(int i0;in;i) ans[i]inf;hd0,tl-1;for(int i2*n-1;i0;i--){if(iL2*n){while(hdtldis[iL]dis[stk[tl]]) tl--;stk[tl]iL;}while(hdtlstk[hd]iR) hd;if(hdtlin) ans[i]dis[stk[hd]];}while(q--){int xread();if(ans[x]n5) puts(-1);else printf(%d\n,ans[x]);}
}
int main(){freopen(calculator.in,r,stdin);freopen(calculator.out,w,stdout);int Tread();while(T--) work(); fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
D
考虑到约数和函数具有积性因为 ∏ a i m \prod a_im ∏aim所以 ∏ σ ( a i ) σ ( m ) \prod\sigma(a_i)\sigma(m) ∏σ(ai)σ(m) 所以我们可以快速算出部分 1 1 1 对于部分 2 2 2我们可以把它理解成多项式然后把它拆开成若干个乘积 于是我们可以 d p dp dp 求解 令 f i , a , b , c f_{i,a,b,c} fi,a,b,c 表示到第 i i i 个质数前面选了 a a a 个 f 0 f0 f0 b b b 个 f 1 f1 f1 c c c 个 f 2 f2 f2 的方案和 这个是好转移的有以下三种情况
不选这个质数新建一个 f 0 f0 f0 或 f 1 f1 f1 或 f 2 f2 f2放在原先的 f 0 f0 f0 或 f 1 f1 f1 或 f 2 f2 f2 中
这都是可以快速转移的 最后求答案的时候只要把为 1 1 1 的贡献计算进去即可 时间复杂度 O ( k 4 ) O(k^4) O(k4)
#include bits/stdc.h
#define int long long
using namespace std;
const int K110,P998244353;
int p[K],f[2][K][K][K];
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;
}
inline void inc(int x,int y){ x(xy)%P;}
int qmi(int a,int b){a%P;int res1;for(;b;b1){if(b1) resres*a%P;aa*a%P;}return res;
}
signed main(){freopen(product.in,r,stdin);freopen(product.out,w,stdout);int naread(),nbread(),f0read(),f1read(),f2read();int kread();for(int i1;ik;i) p[i]read();f[0][0][0][0]1;for(int i0;ik;i){memset(f[~i1],0,sizeof(f[~i1]));int tmin(nb,i);for(int a0;at;a) for(int b0;bt-a;b) for(int c0;ct-a-b;c){int coefna%P*(p[i1]1)%P,rs(nb-a-b-c)%P*f[i1][a][b][c]%P*coef%P;inc(f[~i1][a][b][c],f[i1][a][b][c]);//不放入任何的集合inc(f[~i1][a1][b][c],rs*f0);//放入ainc(f[~i1][a][b1][c],rs*f1%P*p[i1]);//放入binc(f[~i1][a][b][c1],rs*f2%P*p[i1]%P*p[i1]);//放入cinc(f[~i1][a][b][c],(a1ll*b*p[i1]1ll*c*p[i1]%P*p[i1])%P*coef%P*f[i1][a][b][c]);//放入之前的集合} }int tmin(nb,k);int ans0;for(int a0;at;a) for(int b0;bt-a;b) for(int c0;ct-a-b;c)inc(ans,f[k1][a][b][c]*qmi(f0f1f2,(nb-a-b-c)%(P-1))); printf(%d\n,ans);fprintf(stderr,%d ms\n,int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
/*
f[i][a][b][c]:在前i个质数中有a个选了f0b个选了f1c个选了f2的权值和
*/
