今天题目好丧病啊……
早上听闻人手不足,有一种浓浓的要滚粗的感觉。
最后发现排名还不错,做了五道居然有rank 15,真不容易。
切了四道感觉还是不错的。感谢大爷们把思博题都让我A。
补题啦~
1001. A Boring Question
求
![]()
这题可能需要一些高超的数学推导技巧。不过我们发现公式这样复杂,肯定有一些奥妙重重的规律。
我们小范围打表后可以发现,同一纵列是有明显的递推关系的。且第列的递推公式为
结合高中数学知识可以推出通项是
时间复杂度。
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 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int mo=(int)(1e9)+7; LL pow_mod(LL b,LL p,LL k) { LL res=1; for(;p;p>>=1) { if(p&1) res=res*b%k; b=b*b%k; } return res; } void solve() { int n,m; read(n);read(m); printf("%lld\n",(pow_mod(m,n+1,mo)+mo-1)*pow_mod(m-1,mo-2,mo)%mo); } int main() { int T; read(T); while(T--) solve(); return 0; } |
1002. A Simple Chess
有一枚棋子,初始在
,要走到
。
棋子在
时可以走到
或者
,不能出界。有
个坏点,棋子不能走到坏点上。
求
走到
的方案数,答案对
取模。保证
不是坏点。
![]()
这是一道经典问题。
一开始意识模糊了一下方程写错了。坑了一会儿才搞对。
先将点去重后按排序。设点1是
,
是点1走到点
的方案数,则
指点
走到点
的方案数。我们发现在每个点只有两种选择,我们先列个方程算出两种跳法各需要多少次,不妨设为
次和
次,则
就是
。
至于组合数,我们发现模数奥妙重重,肯定是Lucas啦。
时间复杂度。
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct point { LL x,y; point(LL a=0,LL b=0):x(a),y(b) {} } p[1005]; bool operator < (point a,point b) { if(a.x!=b.x) return a.x<b.x; return a.y<b.y; } bool operator == (point a,point b) { return a.x==b.x && a.y==b.y; } LL n,m; int r,tot; LL pow_mod(LL b,LL p,LL k) { LL res=1; for(;p;p>>=1) { if(p&1) res=res*b%k; b=b*b%k; } return res; } const int mo=110119; LL fac[mo],ivf[mo]; inline void addnode(LL x,LL y) { ++tot;p[tot].x=x;p[tot].y=y; } LL C(LL a,LL b) { LL na=a%mo,nb=b%mo; if(na<nb) return 0; LL tmp=(fac[na]*ivf[na-nb]%mo)*ivf[nb]%mo; if(a<mo && b<mo) return tmp; return C(a/mo,b/mo)*tmp%mo; } inline LL calc(int a,int b) { LL x=p[b].x-p[a].x,y=p[b].y-p[a].y; if((x+y)%3!=0) return 0; LL c=(x+y)/3;x-=c;y-=c; if(x<0 || y<0) return 0; return C(x+y,x); } inline bool check(int a,int b) { if(!(p[a].x<p[b].x && p[a].y<p[b].y)) return 0; return 1; } LL f[1005]; int kase=0; void solve() { tot=0;int fl=0; REP(i,1,r) { LL x,y; read(x);read(y); if(x==n && y==m) fl=1; addnode(x,y); } if(fl) { printf("Case #%d: 0\n",++kase); return; } addnode(n,m);addnode(1,1); sort(p+1,p+tot+1); tot=unique(p+1,p+tot+1)-p-1; f[1]=1; REP(i,2,tot) { f[i]=calc(1,i); REP(j,2,i-1) if(check(j,i)) { f[i]=(f[i]-(f[j]*calc(j,i)%mo)+mo)%mo; } } printf("Case #%d: %lld\n",++kase,f[tot]); } int main() { ivf[0]=fac[0]=1; REP(i,1,mo-1) { fac[i]=fac[i-1]*i%mo; ivf[i]=ivf[i-1]*pow_mod(i,mo-2,mo)%mo; } while(scanf("%lld%lld%d",&n,&m,&r)==3) solve(); return 0; } |
1003. A Simple Nim
给定
堆石子,第
堆有
个。
每次玩家有两种操作。第一种是选取一堆,取走其中若干个石子。第二种是将一堆石子分成三堆,每堆非空。
求是否先手必胜。
![]()
设某堆有个石子的
值是
。
结合定义,有
发现数据范围奥妙重重。于是我们小范围打个表,发现,其他
。求一发
和即可。
时间复杂度。
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 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ void solve() { int n,cnt=0; read(n); REP(i,1,n) { int a; read(a); if(a%8==0) a--; else if((a+1)%8==0) a++; cnt^=a; } if(cnt) printf("First player wins.\n"); else printf("Second player wins.\n"); } int main() { int T; read(T); while(T--) solve(); return 0; } |
1004. Magic Number
1005. Master Zhu
1006. Stabilization
1007. This world need more Zhu
给定
个点的带权树,第
个点权值为
。
给定
个询问,形如
:询问点
子树中出现过
次的权值之和与出现过
次的权值之和的最大公约数,保证
。
:询问路径
上出现过
次的权值之和与出现过
次的权值之和的最大公约数。
![]()
数据范围和仅有询问操作说明肯定是莫队。
我们发现子树操作可以转化为区间操作。于是我们发现两种操作分别对应树上莫队和序列莫队,分开来做就好了。
于是就找板子拼成了一份200+行的代码。出题人您有意思吗?
时间复杂度。
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to; }; const int maxn=(int)(2e5)+5; int fr[maxn]; int be[maxn]; int mp[maxn]; int dfn[maxn]; int edv[maxn]; int dep[maxn]; int vis[maxn]; LL res[maxn]; int fa[maxn][22]; int stk[maxn],top; edge e[maxn<<1]; LL sum[maxn]; int apr[maxn]; int val[maxn],tb[maxn]; int n,tote,cnt,siz,idx,hs_cnt=0; inline void addone(int u,int v) { ++tote; e[tote].next=fr[u];fr[u]=tote;e[tote].to=v; } inline void addedge(int u,int v) { addone(u,v);addone(v,u); } struct EventI { int id,l,r,pos,a,b; } A[maxn]; int posa; struct EventII { int id,u,v,a,b; } B[maxn]; int posb; bool operator < (EventI a,EventI b) { if(a.pos!=b.pos) return a.pos<b.pos; return a.r<b.r; } bool operator < (EventII a,EventII b) { if(be[a.u]!=be[b.u]) return be[a.u]<be[b.u]; return dfn[a.v]<dfn[b.v]; } inline int LCA(int u,int v) { if(dep[u]>dep[v]) swap(u,v); PER(i,20,0) if(dep[u]<=dep[fa[v][i]]) v=fa[v][i]; if(u==v) return u; PER(i,20,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } inline void verxor(int x) { sum[apr[val[x]]]-=tb[val[x]]; if(!vis[x]) apr[val[x]]++; else apr[val[x]]--; vis[x]^=1; sum[apr[val[x]]]+=tb[val[x]]; } inline void path(int u,int v) { if(dep[u]>dep[v]) swap(u,v); while(dep[u]<dep[v]) verxor(v),v=fa[v][0]; while(u!=v) verxor(u),verxor(v),u=fa[u][0],v=fa[v][0]; } LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } inline void EventISolve() { int l=1,r=0; REP(i,1,n) sum[i]=apr[i]=vis[i]=0; REP(i,1,n) sum[apr[val[i]]]+=tb[val[i]]; REP(i,1,posa) { while(r<A[i].r) verxor(mp[++r]); while(l>A[i].l) verxor(mp[--l]); while(r>A[i].r) verxor(mp[r--]); while(l<A[i].l) verxor(mp[l++]); res[A[i].id]=gcd(sum[A[i].a],sum[A[i].b]); } } void EventIISolve() { int l=1,r=1; REP(i,1,n) sum[i]=apr[i]=vis[i]=0; REP(i,1,n) sum[apr[val[i]]]+=tb[val[i]]; REP(i,1,posb) { path(l,B[i].u);l=B[i].u; path(r,B[i].v);r=B[i].v; int lca=LCA(B[i].u,B[i].v); verxor(lca); res[B[i].id]=gcd(sum[B[i].a],sum[B[i].b]); verxor(lca); } } void block(int x,int f,int d) { int bot=top; dfn[x]=++idx;mp[idx]=x; dep[x]=d+1;fa[x][0]=f; REP(i,1,20) fa[x][i]=fa[fa[x][i-1]][i-1]; RAL(i,x) if(e[i].to!=f) { block(e[i].to,x,d+1); if(top-bot>=siz) { ++cnt; while(top>bot) be[stk[top--]]=cnt; } } stk[++top]=x;edv[x]=idx; } inline int hash_v(int x) { return lower_bound(tb+1,tb+hs_cnt+1,x)-tb; } void init() { tote=cnt=idx=top=hs_cnt=0; posa=posb=0; siz=(int)pow(n,0.5); REP(i,1,n) fr[i]=-1; } int kase=0; void solve() { printf("Case #%d:\n",++kase); int q; read(n);read(q); init(); REP(i,1,n) read(val[i]),tb[++hs_cnt]=val[i]; sort(tb+1,tb+hs_cnt+1); hs_cnt=unique(tb+1,tb+hs_cnt+1)-tb-1; REP(i,1,n) val[i]=hash_v(val[i]); REP(i,1,n-1) { int u,v; read(u);read(v); addedge(u,v); } block(1,0,1); if(cnt==0) ++cnt; while(top) be[stk[top--]]=cnt; REP(i,1,q) { int opt,u,v,a,b; read(opt);read(u);read(v);read(a);read(b); if(dfn[u]>dfn[v]) swap(u,v); if(opt==1) { ++posa; A[posa].id=i;A[posa].l=dfn[u];A[posa].r=edv[u]; A[posa].pos=(dfn[u]-1)/siz+1;A[posa].a=a;A[posa].b=b; } if(opt==2) { ++posb; B[posb].id=i;B[posb].u=u;B[posb].v=v; B[posb].a=a;B[posb].b=b; } } sort(A+1,A+posa+1);EventISolve(); sort(B+1,B+posb+1);EventIISolve(); REP(i,1,q) printf("%lld\n",res[i]); } int main() { int T; read(T); while(T--) solve(); return 0; } |