今天又是考试，然而早晨7:30考到中午12:30，没时间吃饭了。
然而并不会做题啊啊啊。
T1:
系数显然是组合数啊......
然后，模数不是质数？这不是拓展lucas裸题吗？
等等，拓展lucas，我只写过一遍诶......
看我大力出奇迹:
就是把模数先分解成p1^k1*p2^k2...的形式，然后我们在mod px^kx的情况下进行计算，最后再用互质的CRT合并即可。
mod px^kx的情况下怎么算？我们能把与px互质的阶乘计算出来，再单独计算阶乘中有px的多少次方。
然后互质的直接在mod px^kx下求逆元即可，非互质的直接次数加减。
然而考场上被卡常只有90......
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define debug cout 6 typedef long long int lli; 7 using namespace std; 8 const int maxn=4e5+1e2; 9 10 lli in[maxn],ans; 11 lli c[maxn],modc[maxn]; 12 lli fac[maxn],tim[maxn]; 13 lli dvs[maxn],tms[maxn],pows[maxn]; 14 int n,mod,now,psnow,cnt; 15 16 inline lli fastpow(lli base,lli tim,lli mod) { 17 lli ret = 1; 18 while(tim) { 19 if( tim & 1 ) ret = ret * base % mod; 20 if( tim >>= 1 ) base = base * base % mod; 21 } 22 return ret; 23 } 24 inline lli exgcd(lli a,lli b,lli& x,lli& y) { 25 if( !b ) return x = 1 , y = 0 , a; 26 lli ret = exgcd(b,a%b,y,x); 27 y -= a / b * x; 28 return ret; 29 } 30 inline lli inv(lli t,lli mod) { 31 static lli x,y; 32 exgcd(t,mod,x,y); 33 return ( x % mod + mod ) % mod; 34 } 35 inline void getcoprime(int x,int& retc,int& rett) { 36 retc = x , rett = 0; 37 while( ! ( retc % now ) ) retc /= now , ++rett; 38 } 39 inline void preseq() { 40 fac[0] = 1 , tim[0] = 0; 41 for(int i=1,c,t;i<=n;i++) { 42 getcoprime(i,c,t); 43 fac[i] = fac[i-1] * c % psnow , tim[i] = tim[i-1] + t; 44 } 45 } 46 inline void getdvs(int x) { 47 for(int i=2;(lli)i*i<=x;i++) 48 if( ! ( x % i ) ) { 49 dvs[++cnt] = i , pows[cnt] = 1; 50 while( ! ( x % i ) ) ++tms[cnt] , pows[cnt] *= i , x /= i; 51 } 52 if( x != 1 ) dvs[++cnt] = x , pows[cnt] = x , tms[cnt] = 1; 53 } 54 inline void cnow(int x,int& retc,int& rett) { 55 retc = fac[n-1] * inv(fac[x],psnow) % psnow * inv(fac[n-1-x],psnow) % psnow; 56 rett = tim[n-1] - tim[x] - tim[n-1-x]; 57 } 58 inline void merge(int x,int fac,int tim) { 59 lli cur = (lli) fac * fastpow(now,tim,mod) % mod; 60 c[x] = ( c[x] + cur * ( mod / psnow ) % mod * inv( mod / psnow , psnow ) % mod ) % mod; 61 } 62 63 64 int main() { 65 scanf("%d%d",&n,&mod); 66 for(int i=1;i<=n;i++) scanf("%lld",in+i); 67 getdvs(mod); 68 for(int i=1;i<=cnt;i++) { 69 now = dvs[i] , psnow = pows[i] , preseq(); 70 for(int j=0,c,t;j<n;j++) cnow(j,c,t) , merge(j,c,t); 71 } 72 for(int i=1;i<=n;i++) ( ans += in[i] * c[i-1] % mod ) %= mod; 73 printf("%lld ",ans); 74 return 0; 75 }
T2:
考虑暴力怎么写，我们能两遍dfs求出每个人到达每个点的时间。
然后我们可以求两个人在多少个点上相遇。
如果再且仅在一个点上相遇，显然不可能在边上相遇了。
如果相遇的点大于一个，则这两个人显然一起走了一条边。
这样就把在点上相遇的情况解决了。
考虑两个人经过每一条边的时间区间，如果两个人的时间区间在这条边上有交集，在可能在这条边上相遇。
然后考虑两个人的方向，如果行走方向相反的话，一定相遇；如果方向相同的话，当且仅当两个人之间的距离小于边长才会在这条边上相遇。
于是你成功get到了40分。
考虑怎么优化暴力。
我们钦定一个根，然后处理出每个点到根的距离dis。
因为树上路径唯一，所以我们可以把两个人到达每个点的时间化为一个关于dis的函数：timei=k*disi+b。
我们用树链剖分+线段树维护这个函数。
考虑树上每一条链，我们可以O(log)地求出两个人在这条链上停留的时间区间。
然后我们可以通过这条链的两个函数计算出两个人是否在点上相遇，是否在边上同向相遇，是否在边上逆向相遇。
想想就细节很多啊......
我的写法是先求出两个人在多少个点上相遇，判定是否有解。
然后计算两个人能否在边上相遇，显然这时候两个人不可能在点上相遇了，会多一些条件。
提醒几点细节:
虚边可能更新答案(在虚边上相遇)，LCA的函数斜率不要设置为+-1，要设置为0，否则判定相遇方向时存在问题。
线段树上需要另外维护一下区间最长边来解决同方向相遇的情况，查询区间lr相同是没有边的，不可能在这种区间相遇。
考场上写挂了只有30，不如暴力......
改了不知道多久后改对了(这10kb代码是什么鬼)。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 #include<cstdlib> 7 #define debug cout 8 typedef long long int lli; 9 using namespace std; 10 const int maxn=1e5+1e2; 11 12 int s[maxn],t[maxn<<1],nxt[maxn<<1]; 13 lli dis[maxn],l[maxn<<1]; 14 int dep[maxn],fa[maxn],siz[maxn],top[maxn],son[maxn],id[maxn],rec[maxn],usl[maxn],usr[maxn]; 15 set<int> cs[maxn]; 16 17 struct SegmentTree { 18 struct Equation { // k * dep + b == tme . 19 lli k,b; 20 inline lli calc(const lli &x) const { 21 return k * x + b; 22 } 23 }es[maxn<<2]; 24 int l[maxn<<2],r[maxn<<2],lson[maxn<<2],rson[maxn<<2],used[maxn<<2],dat[maxn<<2],cnt; 25 inline void build(int pos,int ll,int rr) { 26 l[pos] = ll , r[pos] = rr; 27 if( ll == rr ) return; 28 const int mid = ( ll + rr ) >> 1; 29 build(lson[pos]=++cnt,ll,mid) , build(rson[pos]=++cnt,mid+1,rr); 30 } 31 inline void fill(int pos,const Equation &e) { 32 used[pos] = 1 , es[pos] = e; 33 } 34 inline void reset(int pos) { 35 used[pos] = 0; 36 } 37 inline void update(int pos,int ll,int rr,const Equation &e) { 38 if( rr < l[pos] || r[pos] < ll ) return; 39 if( ll <= l[pos] && r[pos] <= rr ) return fill(pos,e); 40 update(lson[pos],ll,rr,e) , update(rson[pos],ll,rr,e); 41 } 42 inline void reset(int pos,int ll,int rr) { 43 if( rr < l[pos] || r[pos] < ll ) return; 44 if( ll <= l[pos] && r[pos] <= rr ) return reset(pos); 45 reset(lson[pos],ll,rr) , reset(rson[pos],ll,rr); 46 } 47 inline Equation query(int pos,int tar) { 48 if( used[pos] ) return es[pos]; 49 // may cause infinity rec-call . 50 const int mid = ( l[pos] + r[pos] ) >> 1; 51 if( tar <= mid ) return query(lson[pos],tar); 52 else return query(rson[pos],tar); 53 } 54 inline void update_mx(int pos,const int &tar,const int &x) { 55 if( l[pos] == r[pos] ) return void(dat[pos]=x); 56 const int mid = ( l[pos] + r[pos] ) >> 1; 57 if( tar <= mid ) update_mx(lson[pos],tar,x); 58 else update_mx(rson[pos],tar,x); 59 dat[pos] = max( dat[lson[pos]] , dat[rson[pos]] ); 60 } 61 inline int query_mx(int pos,int ll,int rr) { 62 if( rr < l[pos] || r[pos] < ll ) return -1; 63 if( ll <= l[pos] && r[pos] <= rr ) return dat[pos]; 64 return max( query_mx(lson[pos],ll,rr) , query_mx(rson[pos],ll,rr) ); 65 } 66 }sgt; 67 typedef SegmentTree::Equation Equation; 68 69 inline void addedge(int from,int to,int len) { 70 static int cnt = 0; 71 t[++cnt] = to , l[cnt] = len , nxt[cnt] = s[from] , s[from] = cnt; 72 } 73 inline void pre(int pos) { 74 siz[pos] = 1; 75 for(int at=s[pos];at;at=nxt[at]) 76 if( t[at] != fa[pos] ) { 77 fa[t[at]] = pos , dep[t[at]] = dep[pos] + 1 , dis[t[at]] = dis[pos] + l[at] , 78 pre(t[at]) , siz[pos] += siz[t[at]]; 79 if( siz[t[at]] > siz[son[pos]] ) son[pos] = t[at]; 80 } 81 } 82 inline void dfs(int pos) { 83 static int iid; 84 top[pos] = pos == son[fa[pos]] ? top[fa[pos]] : pos , rec[id[pos]=++iid] = pos , cs[top[pos]].insert(dis[pos]); 85 sgt.update_mx(1,id[pos],dis[pos]-dis[fa[pos]]); 86 if( son[pos] ) dfs(son[pos]); 87 for(int at=s[pos];at;at=nxt[at]) if( t[at] != fa[pos] && t[at] != son[pos] ) dfs(t[at]); 88 } 89 inline int lca(int x,int y) { 90 while( top[x] != top[y] ) { 91 if( dep[top[x]] < dep[top[y]] ) swap(x,y); 92 x = fa[top[x]]; 93 } 94 return dep[x] < dep[y] ? x : y; 95 } 96 inline void chain(int x,int lc,const Equation &e) { 97 while( top[x] != top[lc] ) { 98 sgt.update(1,id[top[x]],id[x],e) , 99 usl[top[x]] = id[top[x]] , usr[top[x]] = max(usr[top[x]],id[x]) , x = fa[top[x]]; 100 } 101 sgt.update(1,id[lc],id[x],e) , usl[top[x]] = id[lc] , usr[top[x]] = max(usr[top[x]],id[x]); 102 } 103 inline void reschain(int x,int lc) { 104 while( top[x] != top[lc] ) { 105 sgt.reset(1,id[top[x]],id[x]) , 106 usl[top[x]] = usr[top[x]] = 0 , x = fa[top[x]]; 107 } 108 sgt.reset(1,id[lc],id[x]) , usl[top[x]] = usr[top[x]] = 0; 109 } 110 inline void filla(int u,int v,lli t) { // from u , to v , start time is t . 111 int l = lca(u,v); 112 if( l == u ) { // fully down . 113 Equation e = (Equation){1,t-dis[u]}; 114 chain(v,u,e); 115 } else if( l == v ) { 116 Equation e = (Equation){-1,t+dis[u]}; 117 chain(u,v,e); 118 } else { 119 const lli tlca = t + dis[u] - dis[l]; 120 Equation eu = (Equation){-1,t+dis[u]} , ev = (Equation){1,tlca-dis[l]}; 121 chain(u,l,eu) , chain(v,l,ev) , sgt.update(1,id[l],id[l],(Equation){0,tlca}); 122 } 123 } 124 inline void reseta(int u,int v) { // from u , to v , start time is t . 125 int l = lca(u,v); 126 if( l == u ) reschain(v,u); 127 else if( l == v ) reschain(u,v); 128 else reschain(u,l) , reschain(v,l); 129 } 130 inline bool cross(lli x,lli y,lli xx,lli yy) { 131 return x <= yy && xx <= y; 132 } 133 inline int coresme(int t,int l,int r,const Equation &e) { 134 if( l <= r ) { // have same points . 135 lli al = sgt.query(1,l).calc(dis[rec[l]]) , ar = sgt.query(1,r).calc(dis[rec[r]]); 136 lli bl = e.calc(dis[rec[l]]) , br = e.calc(dis[rec[r]]); 137 if( al == bl && ar == br ) { // sameway . 138 return r - l + 1; 139 } else if( l != r && cross(min(al,ar),max(al,ar),min(bl,br),max(bl,br)) ) { 140 Equation ea = sgt.query(1,l) , eaa = sgt.query(1,r); 141 if( !ea.k ) ea = eaa; // ea is lca . 142 if( ea.k != e.k ) { // may have solution . 143 lli lft = ea.k - e.k , rit = e.b - ea.b; 144 if( ! ( rit % lft ) ) { 145 lli sol = rit / lft; 146 if( cs[t].find(sol) != cs[t].end() ) return 1; 147 } 148 } 149 } 150 } 151 return 0; 152 } 153 inline int getsme(int x,int lc,const Equation &e,bool qlca) { 154 int ret = 0; 155 while( top[x] != top[lc] ) { 156 const int t = top[x]; 157 if( usl[t] && usr[t] ) { // same chain visited . 158 int l = max( usl[t] , id[top[x]] ) , r = min( usr[t] , id[x] ); 159 ret += coresme(t,l,r,e); 160 } 161 x = fa[top[x]]; 162 } 163 const int t = top[x]; 164 if( usl[t] && usr[t] ) { // same chain visited . 165 int l = max( usl[t] , id[lc] + qlca ) , r = min( usr[t] , id[x] ); 166 ret += coresme(t,l,r,e); 167 } 168 return ret; 169 } 170 inline bool corevis(int t,int l,int r,const Equation &e) { 171 if( l < r ) { // have same points . 172 lli al = sgt.query(1,l).calc(dis[rec[l]]) , ar = sgt.query(1,r).calc(dis[rec[r]]); 173 lli bl = e.calc(dis[rec[l]]) , br = e.calc(dis[rec[r]]); 174 if( cross(min(al,ar),max(al,ar),min(bl,br),max(bl,br)) ) { 175 Equation ea = sgt.query(1,l) , eaa = sgt.query(1,r); 176 if( !ea.k ) ea = eaa; 177 if( ea.k == e.k ) { 178 if( l == r ) return 0; 179 const lli deltab = abs(ea.b-e.b) , mxlen = sgt.query_mx(1,l+1,r); 180 return deltab < mxlen; 181 } else return 1; 182 } 183 } 184 return 0; 185 } 186 inline bool used(int x) { 187 int t = top[x]; 188 return usl[t] && usr[t] && usl[t] <= id[x] && id[x] <= usr[t]; 189 } 190 inline int vevis(int x,const Equation &e) { 191 if( used(x) && used(fa[x]) ) { 192 Equation ea = sgt.query(1,id[x]); 193 lli al = ea.calc(dis[fa[x]]) , ar = ea.calc(dis[x]); 194 lli bl = e.calc(dis[fa[x]]) , br = e.calc(dis[x]); 195 if( cross(min(al,ar),max(al,ar),min(bl,br),max(bl,br)) ) { 196 if( ea.k == e.k ) { 197 const lli deltab = abs(ea.b-e.b) , mxlen = dis[x] - dis[fa[x]]; 198 return deltab < mxlen; 199 } else return 1; 200 } 201 } 202 return 0; 203 } 204 inline bool getvis(int x,int lc,const Equation &e) { 205 while( top[x] != top[lc] ) { 206 const int t = top[x]; 207 if( usl[t] && usr[t] ) { // same chain visited . 208 int l = max( usl[t] , id[top[x]] ) , r = min( usr[t] , id[x] ); 209 if( corevis(t,l,r,e) ) return 1; 210 } 211 if( vevis(top[x],e) ) return 1; 212 x = fa[top[x]]; // how to deal with this edge ? 213 } 214 const int t = top[x]; 215 if( usl[t] && usr[t] ) { // same chain visited . 216 int l = max( usl[t] , id[lc] ) , r = min( usr[t] , id[x] ); 217 if( corevis(t,l,r,e) ) return 1; 218 } 219 return 0; 220 } 221 inline bool queryb(int u,int v,lli t) { 222 int l = lca(u,v) , sme = 0; 223 if( l == u ) { // fully down . 224 Equation e = (Equation){1,t-dis[u]}; 225 sme = getsme(v,u,e,0); 226 if( sme ) return sme > 1; 227 return getvis(v,u,e); 228 } else if( l == v ) { 229 Equation e = (Equation){-1,t+dis[u]}; 230 sme = getsme(u,v,e,0); 231 if( sme ) return sme > 1; 232 return getvis(u,v,e); 233 } else { 234 const lli tlca = t + dis[u] - dis[l]; 235 Equation eu = (Equation){-1,t+dis[u]} , ev = (Equation){1,tlca-dis[l]}; 236 sme = getsme(u,l,eu,0) + getsme(v,l,ev,1); 237 if( sme ) return sme > 1; 238 return getvis(u,l,eu) || getvis(v,l,ev); 239 } 240 } 241 242 int main() { 243 static int n,m; 244 scanf("%d%d",&n,&m); 245 for(int i=1,a,b,l;i<n;i++) scanf("%d%d%d",&a,&b,&l) , addedge(a,b,l) , addedge(b,a,l); 246 sgt.build(sgt.cnt=1,1,n) , pre(1) , dfs(1); 247 for(int i=1,u,v,t,uu,vv,tt;i<=m;i++) { 248 scanf("%d%d%d%d%d%d",&u,&v,&t,&uu,&vv,&tt) , filla(u,v,t); 249 puts(queryb(uu,vv,tt)?"YES":"NO") , reseta(u,v); 250 } 251 return 0; 252 }
T3:
题答题弃坑啦!
わたしがここにいる
我就在这里
証(あかし)を見(み)せて
见证了看到的一切
閉(と)ざされた仄(くら)き孤洞(こどう)の世界(せかい)で
被封闭了的孤寂的世界
冥闇(やみ)の何処(どこ)かに希望(きぼう)はあるの?
冥冥之中可曾还有希望？
背中合(せなかあ)わせの幻(ゆめ)でもいいから
所以即使是背后的幻想
ふれたいよ…
触手可及