写这篇题解很有挑战性啊,两黑一紫,黑题还是看着玄乎的题解和玄乎的 std 做的。不过还是整理一下的好。
还没做,今天做完再写
有一个 \(N(N\le 60)\) 个点的有向图(用邻接矩阵给你了)。给你 \(Q(Q\le 60)\) 次独立的询问,每次你可以从一个点 \(s\) 出发,到达另一个点 \(t\) 停下来,只要沿着边走,可以经过重复点和边,\(t\) 在最终之前也可以重复到达而不停;你手上有个遥控器,上面有 \(1\sim K\) 共 \(K\) 个 button,每到达一个点(包括 \(s,t\))你都要按下一个可用的 button \(b\),这会让 button \(1\sim b-1\) 都变成可用的,而 \(b\) 变成暂时不可用的;询问有多少种行动方案,使得最开始在 \(s\) 时按了 \(b_s\),最终在 \(t\) 时按了 \(b_t\)。
首先观察性质,假如把 buttons 按从左到右为位数从低到高的顺序看成一个二进制数(从 \(1\) 到 \(K\)),那么可以发现最高位是单调不降的。这将启发我们将最高位纳入 dp 状态。
我们设 \(f(l,i,j)\) 表示只按过位数 \(\le l\) 的 buttons,从 \(i\) 走到 \(j\) 的行动方案。
分类讨论。
怎么把询问中的限制 \(s:b_s,t:b_t\) 放进来?
首先我们想到可以枚举 \(s'\in \text{Neighbour}(s),t'\in\text{Neighbour}(t)\),但是这样没有办法晓得 \(l\) 那维的终状态是什么,pass 掉。
然后我们想到可以对于每一个询问,建立两个新点 \(S,T\),它们不可作为 \(k\)(中转点),因为它们是虚拟的;我们正常转移,唯一不同的地方在于,当 \(i=S,k=s,l=b_s\) 时,如果不特判 \(g(l-1,k)=1\),那 \(g(l-1,k)\) 就是 \(0\) 了,这可不行,所以要特判,\(j=T,k=t,l=b_t\) 时类似的。最后 \(f(K,S,T)\) 就是答案了。诶,这个方法不错!不过它是 \(O(QN^3K)\) 的,比较够呛!
我们来考虑这个做法的核心是什么,那就是把 \(s,t\) 融入了进来。更神奇的是,复杂度没有增加!如果将所有的 \(s_i,t_i\) 分别建立虚拟点 \(S_i,T_i\) 融入进来,按照上面类似的方法,复杂度就是 \(O(N(N+Q)^2K+Q)\) 了,由于 \(N,Q\) 同阶,所以相当于还在上面的做法的复杂度上削掉了一个 \(O(N)\)。
接下来的部分很重要,因为如果你直接开始写可能发现啥正确答案都得不到,因为不太知道 dp 边界。这个是最难 figure out 的部分。
\(l\) 从 \(1\) 到 \(K\) 枚举,\(f\) 不需初始化,但考虑 \(f(\cdot,k,\cdot)\) 和 \(f(\cdot,\cdot,k)\),它们会算错,原因在于 \(g(l-1,k)=h(l-1,k)=0\),所以加一句特判,\(=1\)。
然后你发现我们 AC 了!
#include <bits/stdc++.h> using namespace std; const int N=66,mod=1e9+7; int n,K,q,r,f[N][N*2][N*2],g[N*2],h[N*2],s[N],bs[N],t[N],bt[N],mp[N]; char str[N]; bool e[N][N]; int main(){ scanf("%d%d%d",&n,&K,&q); for(int i=1;i<=n;i++){ scanf("%s",str+1); for(int j=1;j<=n;j++)e[i][j]=str[j]-'0'; } for(int i=1;i<=q;i++)scanf("%d%d%d%d",&bs[i],&s[i],&bt[i],&t[i]); for(int l=1;l<=K;l++){ for(int k=1;k<=n;k++){ memset(g,0,sizeof g),memset(h,0,sizeof h); g[k]=h[k]=1; for(int i=1;i<=n+q;i++){ for(int u=1;u<=n;u++)if(e[u][k])(g[i]+=f[l-1][i][u])>=mod&&(g[i]-=mod); if(i>n&&k==s[i-n]&&l==bs[i-n])g[i]++; } for(int j=1;j<=n+q;j++){ for(int v=1;v<=n;v++)if(e[k][v])(h[j]+=f[l-1][v][j])>=mod&&(h[j]-=mod); if(j>n&&k==t[j-n]&&l==bt[j-n])h[j]++; } for(int i=1;i<=n+q;i++)for(int j=1;j<=n+q;j++)(f[l][i][j]+=1ll*g[i]*h[j]%mod)%=mod; } for(int i=1;i<=n+q;i++)for(int j=1;j<=n+q;j++)(f[l][i][j]+=f[l-1][i][j])%=mod; } for(int i=1;i<=q;i++)printf("%d\n",f[K][i+n][i+n]); }
从集合 \(S=[l_1,r_1]\cup[l_2,r_2]\cup\dots\cup[l_N,r_N](\forall 1\le i<N,r_i<l_{i+1};\forall 1\le i\le N,0\le l_i,r_i\le 10^9)\) 中选 \(3\) 个不同的数 \(a,b,c\),使得 \(a\oplus b,b\oplus c,a\oplus c\le K\),问有多少个合法的无序三元组 \((a,b,c)\)(即 \((a,b,c),(a,c,b),\dots\) 算一样的)。模 \(10^9+7\),\(N\le 2\times 10^4,K\le 10^9\)。
先把 K++
,\(\le K\) 变成 \(<K\)。这对后面有帮助。
再求一个 \(>K\) 的最小 \(P=2^o\)。
首先 \(a/P=b/P=c/P\) 是条件成立的必要条件。分类讨论。
没时间了,(主要是写不下去了),这里是 官方题解 和 洛谷翻译题解,都写得很好,当是自己写的吧,,,,
#include <bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mkp make_pair using namespace std; const int N=1e5+5,mod=1e9+7,I2=500000004,I6=166666668; int n,k,P,ans; vector<pii>ran; map<int,vector<pii> >mp; inline int calc(vector<pii>a){ int s=0; for(pii t:a)s+=t.se-t.fi+1; return s%mod; } inline int C(int n,int m){ if(m==2)return n*(n-1ll)%mod*I2%mod; return n*(n-1ll)%mod*(n-2)%mod*I6%mod; } void work(vector<pii>a,vector<pii>b,int P,int cur){ if(!a.size())return; if(!b.size()){ (ans+=1ll*calc(a)*C(cur,2)%mod)%=mod; return; } if(b.size()==1&&!b[0].fi&&b[0].se==P-1){ (ans+=1ll*calc(a)*C((cur+(k&(P-1)))%mod,2)%mod)%=mod; return; } vector<pii>A[2],B[2]; for(pii t:a){ int tl=max(t.fi-P/2,0),tr=min(t.se-P/2,P/2-1); if(tl<=tr)A[1].push_back(mkp(tl,tr)); tl=t.fi,tr=min(t.se,P/2-1); if(tl<=tr)A[0].push_back(mkp(tl,tr)); } for(pii t:b){ int tl=max(t.fi-P/2,0),tr=min(t.se-P/2,P/2-1); if(tl<=tr)B[1].push_back(mkp(tl,tr)); tl=t.fi,tr=min(t.se,P/2-1); if(tl<=tr)B[0].push_back(mkp(tl,tr)); } if(k&(P/2))work(A[0],B[1],P/2,(cur+calc(B[0]))%mod),work(A[1],B[0],P/2,(cur+calc(B[1]))%mod); else work(A[0],B[0],P/2,cur),work(A[1],B[1],P/2,cur); } int main(){ scanf("%d%d",&n,&k);k++;//【易错】先k++,再求P int o=log2(k)+1; P=1<<o; k-=P/2; for(int i=1,l,r;i<=n;i++){ scanf("%d%d",&l,&r); int Ll=!l?0:(l-1)/P+1,Lr=(r+1)/P; if(Ll>Lr)mp[Ll-1].push_back(mkp(l%P,r%P)); else { (ans+=(2ll*C(P/2,3)%mod+1ll*P*C(k,2)%mod)%mod*(Lr-Ll)%mod)%=mod; if(P*Ll>l)mp[Ll-1].push_back(mkp(l%P,P-1)); if(P*Lr<=r)mp[Lr].push_back(mkp(0,r%P)); } } vector<pii>a,b; for(auto ran:mp){ a.clear(),b.clear(); for(pii t:ran.se){ if(t.fi<P/2&&P/2<=t.se){ a.push_back(mkp(t.fi,P/2-1)); b.push_back(mkp(0,t.se%(P/2))); } else { if(t.fi<P/2)a.push_back(mkp(t.fi,t.se)); else b.push_back(mkp(t.fi%(P/2),t.se%(P/2))); } } work(a,b,P/2,0),work(b,a,P/2,0); (ans+=C(calc(a),3))%=mod,(ans+=C(calc(b),3))%=mod; } cout<<ans; }