冥古之潮【牛客tracker 每日一题】

冥古之潮时间限制2秒 空间限制512M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述万物因时潮涌锚点又在何方白垩色的王子给了你一张由n nn个点和m mm条无向边构成的联通图结点编号从1 11至n nn保证不存在重边和自环每条边的长度均为1 11同时他又给了你一点x xx。白垩色的王子告诉你图上存在k kk个锚点。记第i ii个锚点所在点的编号为a i a_iai​​记点a i a_iai​​ 到点x xx的最短距离为d i s i dis_idisi​​。他又告诉你这k kk个锚点的位置满足d i s 1 d i s 2 ⋯ d i s k dis_1dis_2⋯dis_kdis1​dis2​⋯disk​​且对于任意一个锚点i ii都有d i s i ≠ 0 dis_i≠0disi​0。同时这个图还满足记图中一点i ii到点x xx的距离为D i s i Dis_iDisi​​保证m a x ⁡ i 1 n D i s i ≤ 5000 max_{⁡i1}^n Dis_i≤5000max⁡i1n​Disi​≤5000。现在白垩色的王子想知道这k kk个锚点的位置有多少种可能。具体地我们记这k kk个锚点的位置组成了一个集合S { a 1 , a 2 , … , a k } S\{a_1,a_2,…,a_k\}S{a1​,a2​,…,ak​}对于两个集合如果他们有任意一个元素不一样我们就认为这两个集合是不一样的。也就是说你只需要输出合法的不同集合数即可。一共有q qq组询问每组询问给出一个k kk你需要求出锚点数量为k kk时的可能位置方案数。由于答案可能过大你只需要输出它对10 9 7 10^971097取模的结果。输入描述第一行输入四个整数n , m , q , x ( 1 ≤ n , m ≤ 10 6 1 ≤ q ≤ 5000 , 1 ≤ x ≤ n ) n,m,q,x(1≤n,m≤10^61≤q≤5000,1≤x≤n)n,m,q,x(1≤n,m≤1061≤q≤5000,1≤x≤n)意义如题面所示。接下来m mm行每行包含两个整数u , v ( 1 ≤ u , v ≤ n ) u,v(1≤u,v≤n)u,v(1≤u,v≤n)表示在u , v u,vu,v之间存在一条无向边。接下来q qq行每行输入一个整数k ( 1 ≤ k ≤ 5000 ) k(1≤k≤5000)k(1≤k≤5000)表示锚点的数量。输出描述输出q qq行第i ii行输出一个整数表示对于第i ii组询问给出的k kk锚点位置的合法方案数结果对10 9 7 10^971097取模。示例1输入3 3 2 1 1 2 2 3 3 1 1 2输出2 0说明k 1 k1k1时锚点可放在点2 22或3 33k 2 k2k2时无法放置。示例2输入9 10 3 1 1 2 2 7 7 5 5 3 3 6 5 6 1 3 9 8 1 4 4 8 2 3 100输出19 12 0解题思路本题核心是BFS单源最短路径分组背包动态规划求解合法锚点集合方案数。从指定节点x出发进行B F S BFSBFS遍历计算所有节点到x的最短距离统计每个距离对应的节点数量cnt[d]题目保证最大距离≤ 5000 ≤5000≤5000。合法锚点要求距离严格递增等价于从每个距离层中最多选择1 11个节点转化为经典分组背包问题。定义dp[k]为选择k个锚点的方案数采用逆序遍历的一维D P DPDP完成状态转移。最后直接读取q次询问输出对应dp[k]的结果即可。算法高效适配n,m≤1e6、最大距离5000 50005000的规模满足时间限制。总结核心逻辑将严格递增选锚点的问题转化为按距离分层、每层最多选1 11个节点的分组背包问题。关键操作B F S BFSBFS统计各距离的节点数量01 0101背包D P DPDP计算选k个节点的总方案数。效率保障B F S BFSBFS线性处理大图背包D P DPDP复杂度为O ( 5000 2 ) O(5000²)O(50002)完美适配题目数据规模与查询要求。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e610;constll p1e97;constll INF1e18;constll M5e310;ll d[N],cnt[M];vectorllv[N];ll dp[M];intmain(){ll n,m,Q,X,x,y;cinnmQX;while(m--){cinxy;v[x].push_back(y);v[y].push_back(x);}queuellq;memset(d,-1,sizeof(d));d[X]0;q.push(X);m0;while(!q.empty()){xq.front();q.pop();cnt[d[x]];mmax(m,d[x]);for(ll y:v[x]){if(d[y]-1){q.push(y);d[y]d[x]1;}}}dp[0]1;for(ll i1;im;i)for(ll jm;j1;j--){dp[j](dp[j]dp[j-1]*cnt[i])%p;}while(Q--){cinx;coutdp[x]endl;}return0;}