Codechef April Challenge 2020 简要题解_综合

这次的题目难度比较高，有一做的价值，不过照例没有challenge的题解。

Strange Number

略

Squared Subsequences

略

Ready Bitwise

略

Perfect Power Divisors

写下式子发现显然是个容斥，令 $F (i)$ 表示 $∑i=2?Nk?(i??Nik?)\sum_{i=2}^{\lfloor \sqrt[k] N \rfloor}(i\cdot \lfloor \frac{N}{i^k} \rfloor)$ ，则答案为 $N?∑i=2?log?2N?F(i)?μ(i)N-\sum_{i=2}^{\lfloor \log_{2}N \rfloor} F(i)\cdot \mu(i)$ 。
考虑计算 $F (i)$ ，对于 $i > 2$ 暴力枚举 $i$ 计算即可做到 $O(N3)\mathcal O(\sqrt[3] N)$ 的复杂度，只需考虑 $i = 2$ 的情况。注意到 $?Ni2?\lfloor \frac{N}{i^2} \rfloor$ 取值只有 $O(N3)\mathcal O(\sqrt[3] N)$ 段，于是直接数论分块即可，每段内部是个等差数列求和。
单组数据时间复杂度 $O(N3)\mathcal O(\sqrt[3] N)$ 。

#include <bits/stdc++.h>
#define MOD 1000000007
#define inv6 166666668
#define last last2using namespace std;typedef long long ll; ll fast_pow(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans*=x;x*=x;k>>=1;}return ans;
}ll nor_pow(ll x,int k) {
    ll ans=1;for(int i=1;i<=k;i++) {
    if (2e18/ans<x) return 2e18;ans*=x;}return ans;
}int prime[61],mu[61];
bool check[61];void pre() {
    int tot=0;for(int i=2;i<=60;i++) {
    if (!check[i]) {
    prime[++tot]=i;mu[i]=MOD-1;}for(int j=1;j<=tot&&i*prime[j]<=60;j++) {
    check[i*prime[j]]=1;if (i%prime[j]==0) break;mu[i*prime[j]]=(MOD-mu[i])%MOD;}}
}inline ll nsqrt(ll n) {
    ll t=sqrt(n);while (t*t>n) t--;while ((t+1)*(t+1)<=n) t++;return t; 
} inline ll nsqrt(ll n,int k) {
    ll t=pow(n,1.0/k);while (nor_pow(t,k)>n) t--;while (nor_pow(t+1,k)<=n) t++;return t;
}inline ll S(ll n) {
    n%=MOD;return n*(n+1)%MOD*(2*n+1)%MOD*inv6%MOD;
}int main() {
    pre();int cases;scanf("%d",&cases);for(;cases;cases--) {
    ll n;scanf("%lld",&n);int ans=0;ll up=nsqrt(n);for(ll i=2,last=1;i<=up;i=last+1) {
    last=nsqrt(n/(n/(i*i)));ans=(ans+(S(last)-S(i-1)+MOD)*(n/(i*i)%MOD))%MOD;}for(int i=3;i<=60;i++)if (mu[i]) {
    int s=0;ll up=nsqrt(n,i);for(ll j=2;j<=up;j++) {
    ll t=fast_pow(j,i);s=(s+(n/t)%MOD*t)%MOD;}ans=(ans+(ll)s*(MOD-mu[i]))%MOD;}printf("%lld\n",(ans+n)%MOD);}return 0;
}
/* 1 1000000000000000000 */

Factor Tree

考虑乘积约数个数的式子，注意到每次加入或删除一个数只会修改 $O(w(V))\mathcal O(w(V))$ 个质数的次数（ $w (V)$ 表示 $V$ 以内单个数最多的不同质因子个数），预处理逆元可以在 $O(w(V))\mathcal O(w(V))$ 的时间内完成修改。
那么做法就很显然了，直接用树上莫队离线处理询问即可。我写的是dfs序上分块的版本，需要稍微加一些常数优化才能通过。
单组数据时间复杂度 $O((N+Q)Qw(V)+V)\mathcal O((N+Q) \sqrt Q w(V) +V)$ 。

#include <bits/stdc++.h>
#define MOD 1000000007
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;int prime[100005];
int mind[1000005],mins[1000005],mi[1000005];
bool check[1000005];
vector <pr> vt[1000005];int inv[2000005];void pre() {
    int tot=0;for(int i=2;i<=1e6;i++) {
    if (!check[i]) {
    prime[++tot]=i;mind[i]=mi[i]=i;mins[i]=1;}for(int j=1;j<=tot&&i*prime[j]<=1e6;j++) {
    check[i*prime[j]]=1;mind[i*prime[j]]=prime[j];if (i%prime[j]==0) {
    mins[i*prime[j]]=mins[i]+1;mi[i*prime[j]]=mi[i]*prime[j];break;}mins[i*prime[j]]=1;mi[i*prime[j]]=prime[j];}}for(int i=1;i<=1e6;i++) {
    int x=i;while (x>1) {
    vt[i].push_back(pr(mind[x],mins[x]));x/=mi[x];}}inv[1]=1;for(int i=2;i<=2e6;i++) inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
}vector <int> e[100005];
int fa[100005][20],dep[100005];
int num[200005],dfn[100005],ed[100005],dfs_cnt;void dfs(int x) {
    dfn[x]=++dfs_cnt;num[dfs_cnt]=x;for(int i=0;i<e[x].size();i++)if (e[x][i]!=fa[x][0]) {
    int u=e[x][i];fa[u][0]=x;dep[u]=dep[x]+1;for(int j=1;j<20;j++) fa[u][j]=fa[fa[u][j-1]][j-1];dfs(u);}ed[x]=++dfs_cnt;num[dfs_cnt]=x;
}int lca(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);int d=dep[x]-dep[y];for(int i=0;i<20;i++)if ((d>>i)&1) x=fa[x][i];if (x==y) return x;for(int i=19;i>=0;i--)if (fa[x][i]!=fa[y][i]) {
    x=fa[x][i];y=fa[y][i];}return fa[x][0];
}bool in[100005];
int val[100005],cnt[1000005];
ll s;void change(int x) {
    int v=val[x];if (!in[x]) {
    for(int i=0;i<vt[v].size();i++) {
    int u=vt[v][i].FR;s=s*inv[cnt[u]]%MOD;cnt[u]+=vt[v][i].SE;s=s*cnt[u]%MOD;}}else {
    for(int i=0;i<vt[v].size();i++) {
    int u=vt[v][i].FR;s=s*inv[cnt[u]]%MOD;cnt[u]-=vt[v][i].SE;s=s*cnt[u]%MOD;}}in[x]^=1;
}int S;struct Query {
    int l,r,id,bl;Query() {
    }Query(int a,int b,int c):l(a),r(b),id(c) {
    bl=(l-1)/S+1;}bool operator < (const Query & b) const {
    return (bl!=b.bl)?bl<b.bl:((bl&1)?r<b.r:r>b.r);}
};Query q[100005];
int ans[100005];void solve(int n) {
    memset(in,0,sizeof(in));for(int i=1;i<=1e6;i++) cnt[i]=1;sort(q+1,q+n+1);int L=1,R=0;s=1;for(int i=1;i<=n;i++) {
    while (L>q[i].l) change(num[--L]);while (R<q[i].r) change(num[++R]);while (L<q[i].l) change(num[L++]);while (R>q[i].r) change(num[R--]);int p=lca(num[q[i].l],num[q[i].r]);if (!in[p]) {
    change(p);ans[q[i].id]=s;change(p);}else ans[q[i].id]=s;}
}int main() {
    pre();int cases;scanf("%d",&cases);for(;cases;cases--) {
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) e[i].clear();for(int i=1;i<n;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);}dfs_cnt=0;dfs(1);for(int i=1;i<=n;i++) scanf("%d",&val[i]);int m;S=(int)sqrt(4.0*dfs_cnt);scanf("%d",&m);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);if (dfn[x]>dfn[y]) swap(x,y);if (ed[x]<dfn[y]) q[i]=Query(ed[x],dfn[y],i);else q[i]=Query(dfn[x],dfn[y],i);}solve(m);for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}return 0;
}

Line Line Line Graph

做这题前先膜了一下ZJOI 2018线图的题解。

K=1

此时显然是一个一般图最大匹配，直接抄一个一般图最大匹配的板子就好了。
时间复杂度 $O(NMα(N))\mathcal O(NM\alpha(N))$ 。

K>1

对每个连通块分开考虑。
考虑 $K = 2$ 的情况，注意到二阶线图的点是原图中的两条共一个端点的边，这样两个点之间有边当且仅当共了一条边。
于是对于连通图 $G$ ， $L^2(G)$ 最大独立集的大小上界是 $?M2?=?∣L(G)∣2?\lfloor \frac{M}{2} \rfloor=\lfloor \frac{|L(G)|}{2} \rfloor$ 。事实上，可以证明我们可以达到这个上界。具体来说，我们相当于要给边尽可能多的配对，使得同一对里的两条边共同一个端点。一个构造是考虑一棵dfs树。我们自底向上考虑，令一条返祖边在祖先处被考虑，尽可能将一个子树内部的边配对，保证至多剩下一条子树根节点向子树内部连的边。考虑现在已经尽可能配完了儿子子树内部的边，那么若某个儿子子树内剩下一条边，就将它跟对应的树边配对，这样操作完后子树内剩下的树边和非树边都以当前点作为端点，直接配对即可（剩下奇数条的时候就留下一条）。
这样，可以发现对于连通图 $G$ ， $L^K(G)$ （ $K > 1$ ）的最大独立集大小即为 $?∣LK?1(G)∣2?\lfloor \frac{|L^{K-1}(G)|}{2} \rfloor$ ，问题转化为对 $K≤6K\leq 6$ 求出 $L^K(G)|$ 。
令 $d_i$ 表示 $G$ 中点 $i$ 的度数，那么有：
$∣ L (G) ∣ = M$ 。
$∣L2(G)∣=∑i(di2)|L^2(G)|=\sum_{i}\binom {d_i}{2}$ 。
$∣L3(G)∣=∑(i,j)∈E(di+dj?22)|L^3(G)|=\sum_{(i,j)\in E}\binom {d_i+d_j-2} {2}$ 。
这些都容易在线性时间内计算。
注意到 $L^4(G)=L^3(L(G))$ ，于是有 $∣L4(G)∣=∑(i,j)∈E,(i,k)∈E(2di+dj+dk?62)|L^4(G)|=\sum_{(i,j)\in E,(i,k)\in E}\binom {2d_i+d_j+d_k-6}{2}$ （ $j < k$ ）。拆开式子后预处理出 $fi=∑(i,j)∈Edjf_i=\sum_{(i,j)\in E}d_j$ 和 $gi=∑(i,j)∈Edj2g_i=\sum_{(i,j)\in E}d_j^2$ 即可线性计算。
现在考虑计算 $L^6(G)|$ 。有 $L^6(G)=L^4(L^2(G))$ ，于是如果我们建出 $L^2(G)$ ，套用 $L^4(G)$ 的公式即可计算。不过 $L^2(G)$ 的边数是 $O(M3)\mathcal O(M^3)$ 的，不好直接求出，但是可以发现我们只需要用到 $L^2(G)$ 中每个点的 $f$ 和 $g$ ，这些信息可以通过枚举 $L^2(G)$ 中共的边来快速求出。
时间复杂度 $O(M2)\mathcal O(M^2)$ 。

#include <bits/stdc++.h>
#define MOD 998244353
#define FR first
#define SE secondusing namespace std;typedef pair<int,int> pr;
typedef long long ll;
typedef __int128 lll;namespace Solve_1 {
    namespace SETS {
    int fa[2005];void init(int n) {
    for(int i=1;i<=n;i++) fa[i]=i;
}int find_father(int x) {
    return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
}bool isroot(int x) {
    return find_father(x)==x;
}void merge(int x,int y) {
    x=find_father(x);y=find_father(y);if (x==y) return;fa[x]=y;
}}int link[2005],pre[2005];
int vis[2005],dfn[2005],cnt;
queue <int> q;int lca(int x,int y) {
    x=SETS::find_father(x);y=SETS::find_father(y);cnt++;while (dfn[x]!=cnt) {
    dfn[x]=cnt;x=SETS::find_father(pre[link[x]]);if (y) swap(x,y);}return x;
}void blossom(int x,int y,int p) {
    while (SETS::find_father(x)!=p) {
    pre[x]=y;y=link[x];if (vis[y]==1) {
    vis[y]=0;q.push(y);}if (SETS::isroot(x)) SETS::merge(x,p);if (SETS::isroot(y)) SETS::merge(y,p);x=pre[y];}
}void arg(int x) {
    for(int last=0;x;x=last) {
    last=link[pre[x]];link[x]=pre[x];link[pre[x]]=x;}
}vector <int> e[2005];bool bfs(int s,int n) {
    while (!q.empty()) q.pop();memset(pre,0,sizeof(pre));memset(vis,255,sizeof(vis));SETS::init(n);q.push(s);vis[s]=0;while (!q.empty()) {
    int x=q.front();q.pop();for(int i=0;i<e[x].size();i++)if (SETS::find_father(x)!=SETS::find_father(e[x][i])&&vis[e[x][i]]!=1) {
    int u=e[x][i];if (vis[u]==-1) {
    vis[u]=1;pre[u]=x;if (!link[u]) {
    arg(u);return 1;}vis[link[u]]=0;q.push(link[u]);}else {
    int p=lca(x,u);blossom(x,u,p);blossom(u,x,p);}}}return 0;
}void solve(int n,int m) {
    for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);}int ans=0;for(int i=1;i<=n;i++) if (!link[i]) ans+=bfs(i,n);printf("%d\n",ans);
}}namespace Solve_2to5 {
    vector <int> e[2005];
int col[2005];void dfs(int x) {
    for(int i=0;i<e[x].size();i++)if (!col[e[x][i]]) {
    int u=e[x][i];col[u]=col[x];dfs(u);}
}ll sum1[2005],sum2[2005],deg[2005];
ll ans[2005];void solve2(int n) {
    for(int i=1;i<=n;i++) ans[col[i]]+=deg[i];for(int i=1;i<=n;i++) ans[i]>>=1;
}void solve3(int n) {
    for(int i=1;i<=n;i++) ans[col[i]]+=(deg[i]*(deg[i]-1)>>1);
}void solve4(int n) {
    for(int i=1;i<=n;i++)for(int j=0;j<e[i].size();j++) {
    int u=e[i][j]; ll t=deg[i]+deg[u]-2;ans[col[i]]+=(t*(t-1)>>1);}for(int i=1;i<=n;i++) ans[i]>>=1;
}void solve5(int n) {
    for(int i=1;i<=n;i++)for(int j=0;j<e[i].size();j++) {
    int u=e[i][j];sum1[u]+=deg[i];sum2[u]+=deg[i]*deg[i];}for(int i=1;i<=n;i++) {
    ans[col[i]]+=(deg[i]*(deg[i]-1)*(deg[i]-3)*(deg[i]-4)>>1);ans[col[i]]+=(deg[i]-1)*(deg[i]-3)*sum1[i];ans[col[i]]+=((deg[i]-1)*(sum2[i]-sum1[i])>>1);ans[col[i]]+=(deg[i]*(deg[i]-1)*(deg[i]-3)*(deg[i]-3)>>1);ans[col[i]]+=(deg[i]-1)*(deg[i]-3)*sum1[i];ans[col[i]]+=((sum1[i]*sum1[i]-sum2[i])>>1);}
}void solve(int n,int m,int k) {
    for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);deg[x]++;deg[y]++;}int sz=0;for(int i=1;i<=n;i++)if (!col[i]) {
    col[i]=++sz;dfs(i);}if (k==2) solve2(n);else if (k==3) solve3(n);else if (k==4) solve4(n);else if (k==5) solve5(n);ll s=0;for(int i=1;i<=sz;i++) s+=(ans[i]>>1);printf("%lld\n",s%MOD);
}}namespace Solve_6 {
    vector <int> e[2005],vt[2005];
int col[2005];void dfs(int x) {
    for(int i=0;i<e[x].size();i++)if (!col[e[x][i]]) {
    int u=e[x][i];col[u]=col[x];dfs(u);}
}ll sum1[2005],sum2[2005],deg[2005];
ll ans[2005];void solve(int n,int m) {
    for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);vt[x].push_back(i);vt[y].push_back(i);}for(int i=1;i<=n;i++)for(int j=0;j<vt[i].size();j++)for(int k=j+1;k<vt[i].size();k++) {
    int u=vt[i][j],v=vt[i][k];e[u].push_back(v);e[v].push_back(u);deg[u]++;deg[v]++;}int sz=0;for(int i=1;i<=m;i++)if (!col[i]) {
    col[i]=++sz;dfs(i);}for(int i=1;i<=m;i++)for(int j=0;j<e[i].size();j++) {
    int u=e[i][j];sum1[u]+=deg[i];sum2[u]+=deg[i]*deg[i];}for(int i=1;i<=m;i++) {
    ans[col[i]]+=(deg[i]*(deg[i]-1)*(deg[i]-3)*(deg[i]-4)>>1);ans[col[i]]+=(deg[i]-1)*(deg[i]-3)*sum1[i];ans[col[i]]+=((deg[i]-1)*(sum2[i]-sum1[i])>>1);ans[col[i]]+=(deg[i]*(deg[i]-1)*(deg[i]-3)*(deg[i]-3)>>1);ans[col[i]]+=(deg[i]-1)*(deg[i]-3)*sum1[i];ans[col[i]]+=((sum1[i]*sum1[i]-sum2[i])>>1);}ll s=0;for(int i=1;i<=sz;i++) s+=(ans[i]>>1);printf("%lld\n",s%MOD);
}} namespace Solve_7 {
    vector <pr> e[2005];
vector <int> vt[2005];
int col1[2005],col2[2000005];void dfs(int x) {
    for(int i=0;i<e[x].size();i++)if (!col1[e[x][i].FR]) {
    int u=e[x][i].FR;col1[u]=col1[x];dfs(u);}
}ll sum1[2000005],sum2[2000005],deg[2000005];
lll ans[2005];void solve(int n,int m) {
    for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(pr(y,i));e[y].push_back(pr(x,i));}int sz=0;for(int i=1;i<=n;i++)if (!col1[i]) {
    col1[i]=++sz;dfs(i);}int cnt=0;for(int i=1;i<=n;i++)for(int j=0;j<e[i].size();j++)for(int k=j+1;k<e[i].size();k++) {
    int u=e[i][j].SE,v=e[i][k].SE;cnt++;vt[u].push_back(cnt);vt[v].push_back(cnt);deg[cnt]=2*e[i].size()+e[e[i][j].FR].size()+e[e[i][k].FR].size()-6;col2[cnt]=col1[i];}for(int i=1;i<=m;i++) {
    ll s1=0,s2=0;for(int j=0;j<vt[i].size();j++) {
    int u=vt[i][j];s1+=deg[u];s2+=deg[u]*deg[u];}for(int j=0;j<vt[i].size();j++) {
    int u=vt[i][j];sum1[u]+=s1-deg[u];sum2[u]+=s2-deg[u]*deg[u];}}for(int i=1;i<=cnt;i++) {
    ans[col2[i]]+=(deg[i]*(deg[i]-1)*(deg[i]-3)*(deg[i]-4)>>1);ans[col2[i]]+=(deg[i]-1)*(deg[i]-3)*sum1[i];ans[col2[i]]+=((deg[i]-1)*(sum2[i]-sum1[i])>>1);ans[col2[i]]+=(deg[i]*(deg[i]-1)*(deg[i]-3)*(deg[i]-3)>>1);ans[col2[i]]+=(deg[i]-1)*(deg[i]-3)*sum1[i];ans[col2[i]]+=((sum1[i]*sum1[i]-sum2[i])>>1);}lll s=0;for(int i=1;i<=sz;i++) s+=(ans[i]>>1);printf("%lld\n",(ll)(s%MOD));
}} int main() {
    int n,m,k;scanf("%d%d%d",&n,&m,&k);if (k==1) Solve_1::solve(n,m);else if (k>=2&&k<=5) Solve_2to5::solve(n,m,k);else if (k==6) Solve_6::solve(n,m);else if (k==7) Solve_7::solve(n,m);return 0;
}

A Leisurely Journey

设 $F_i(x)$ 表示到达点 $i$ 的方案数关于时间的生成函数，显然有 $F1(x)=11?L1xF_1(x)=\frac{1}{1-L_1x}$ ， $Fi(x)=x?∑(j,i)∈EFj(x)1?LixF_i(x)=\frac{x\cdot\sum_{(j,i)\in E}F_j(x)}{1-L_ix}$ （ $i > 1$ ）。那么可以发现 $F_N(x)$ 可以写成 $P(x)Q(x)\frac{P(x)}{Q(x)}$ 的形式，其中 $d e g (P (x)) < N$ ， $Q(x)=∏i=1N(1?Lix)Q(x)=\prod_{i=1}^{N}(1-L_ix)$ 。至于求出 $P (x)$ ，可以考虑先DP出 $F_N(x)$ 的前 $N$ 项系数，乘上 $Q (x)$ 即可，DP时间复杂度为 $O(NM)\mathcal O(NM)$ 。
现在每个询问即为给定 $k$ ，求出 $x^k]F_N(x)$ 。如果直接用多项式取模加速常系数线性递推的经典算法，不仅单个询问复杂度为 $O(Nlog?Nlog?k)O(N\log N\log k)$ ，且因为模数不是NTT模数，需要任意模数FFT，因此常数非常大，不能通过。
可以发现现在给定了 $Q (x)$ 的因子分解，可以尝试得到复杂度更优秀的算法。
考虑给 $L_i$ 排序，令去重后得到长度为 $d$ 的数列 $p$ ，其中 $p_i$ 在 $L$ 中出现了 $r_i$ 次。根据有理生成函数的一般展开定理，我们可以将 $F_N(x)$ 表示为 $∑i=1d∑j=1riai,j(1?pix)j\sum_{i=1}^{d}\sum_{j=1}^{r_i}\frac{a_{i,j}}{(1-p_ix)^j}$ ，那么 $[xk]FN(x)=∑i=1d∑j=1riai,j?(k+j?1j?1)?pik[x^k]F_N(x)=\sum_{i=1}^{d}\sum_{j=1}^{r_i}a_{i,j}\cdot \binom{k+j-1}{j-1}\cdot {p_i}^k$ 。这样只需要快速幂就可以在 $O(Nlog?k)\mathcal O(N\log k)$ 的时间复杂度内处理单个询问。
现在难点在于得到这个分解，也即得到每个常数 $a_{i,j}$ 。令 $Ri(x)=∏j≠i(1?pjx)rjR_i(x)=\prod_{j\neq i}(1-p_jx)^{r_j}$ ，注意到通分后有 $P(x)=∑i=1d∑j=1ri(ai,j?Ri(x)?(1?pix)ri?j)P(x)=\sum_{i=1}^{d}\sum_{j=1}^{r_i}(a_{i,j}\cdot R_i(x)\cdot (1-p_ix)^{r_i-j})$ 。那么有 $P(1pi)=ai,ri?∏j≠i(1?pjpi)rjP(\frac{1}{p_i})=a_{i,r_i}\cdot \prod_{j\neq i}(1-\frac{p_j}{p_i})^{r_j}$ ，于是容易得到 $a_{i,r_i}$ 。得到 $a_{i,r_i}$ 后从 $P (x)$ 中减去对应项并整体除去一个 $1-p_ix)$ 即可将 $r_i$ 减去 $1$ ，继续计算即可。这样分解时间复杂度为 $O(N2)\mathcal O(N^2)$ 。
这里Entropy Increaser给出了一个复杂度更优秀的分解做法，也记录一下。我们令 $Gi(x)=P(x)mod(1?pix)ri=((∑j=1riai,j?(1?pix)ri?j)?Ri(x))mod(1?pix)riG_i(x)=P(x) \bmod (1-p_ix)^{r_i}=((\sum_{j=1}^{r_i}a_{i,j}\cdot (1-p_ix)^{r_i-j})\cdot R_i(x))\bmod (1-p_ix)^{r_i}$ ，计算每个 $G_i(x)$ 可以用类似多点求值的分治过程。注意到如果我们将 $G_i(x)$ 和 $R_i(x)$ 的基变换到 $1-p_ix)^k$ 下，也即令 $G'_i(1-p_ix)=G_i(x)$ ， $Ri′(1?pix)=Ri(x)mod(1?pix)riR'_i(1-p_ix)=R_i(x) \bmod (1-p_ix)^{r_i}$ ，求出 $G'_i(x)$ 和 $R'_i(x)$ 的系数表示，这个可以二项式展开一下用卷积实现。那么 $ai,j=[xri?j](Gi′(x)?Ri′(x)?1)a_{i,j}=[x^{r_i-j}](G'_i(x)\cdot R'_i(x)^{-1})$ ，直接多项式求逆即可。这样分解时间复杂度为 $O(Nlog?2N)\mathcal O(N\log ^2 N)$ 。
总时间复杂度为 $O(NM+N2+QNlog?V)\mathcal O(NM+N^2+QN\log V)$ 或 $O(NM+Nlog?2N+QNlog?V)\mathcal O(NM+N\log^2N+QN\log V)$ 。

#include <bits/stdc++.h>
#define MOD 1000000007
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;ll pow_mod(ll x,ll k) {
    k%=(MOD-1);ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}ll facd[4005],facv[4005];void pre(int n) {
    facd[0]=1;for(int i=1;i<=n;i++) facd[i]=facd[i-1]*i%MOD;facv[n]=pow_mod(facd[n],MOD-2);for(int i=n-1;i>=0;i--) facv[i]=facv[i+1]*(i+1)%MOD;
}vector <int> e[4005];
int num[4005];int f[4005];
ll sum[4005],g[4005];void dp(int n,int m) {
    f[1]=1;g[0]=(n==1);for(int i=1;i<n;i++) {
    memset(sum,0,sizeof(sum));for(int j=1;j<=n;j++) {
    for(int k=0;k<e[j].size();k++) sum[e[j][k]]+=f[j];f[j]=(sum[j]+(ll)f[j]*num[j])%MOD;}g[i]=f[n];} 
}pr val[4005];
vector <int> d[4005];
ll p[4005];int getpoly(int n) {
    sort(num+1,num+n+1);int s=0,sz=0;for(int i=1;i<=n;i++) {
    s++;if (i==n||num[i]!=num[i+1]) {
    val[++sz]=pr(num[i],s);s=0;}}p[0]=1;for(int i=1;i<=sz;i++) {
    int u=MOD-val[i].FR,v=val[i].SE;for(int j=0;j<v;j++)for(int k=n;k>0;k--) {
    g[k]=(g[k]+g[k-1]*u)%MOD;p[k]=(p[k]+p[k-1]*u)%MOD;}}g[n]=0;int r=n;for(int i=1;i<=sz;i++) {
    int u=val[i].FR,v=val[i].SE;ll inv=pow_mod(u,MOD-2);for(int j=0;j<v;j++) {
    int up=r-j;for(int k=up;k>0;k--) {
    p[k]=p[k]*(MOD-inv)%MOD;p[k-1]=(p[k-1]-p[k]+MOD)%MOD;}for(int k=0;k<up;k++) p[k]=p[k+1];p[up]=0;}r-=v;ll s1=0;for(int j=r;j>=0;j--) s1=(s1*inv+p[j])%MOD;s1=pow_mod(s1,MOD-2);d[i].resize(v);for(int j=v-1;j>=0;j--) {
    ll s2=0;int up=r+j;for(int k=up;k>=0;k--) s2=(s2*inv+g[k])%MOD;ll t=s2*s1%MOD;d[i][j]=t;for(int k=0;k<=r;k++) g[k]=(g[k]-t*p[k]%MOD+MOD)%MOD;for(int k=up;k>0;k--) {
    g[k]=g[k]*(MOD-inv)%MOD;g[k-1]=(g[k-1]-g[k]+MOD)%MOD;}for(int k=0;k<up;k++) g[k]=g[k+1];g[up]=0;}}return sz;
}int query(int n,ll k) {
    int ans=0;for(int i=1;i<=n;i++) {
    int u=val[i].FR,v=val[i].SE;ll t=pow_mod(u,k),s=1;for(int j=0;j<v;j++) {
    ans=(ans+t*d[i][j]%MOD*s%MOD*facv[j])%MOD;s=(k+j+1)%MOD*s%MOD;}}return ans;
}int main() {
    int n,m,k;scanf("%d%d%d",&n,&m,&k);pre(n);for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);}dp(n,m);int sz=getpoly(n);for(int i=1;i<=k;i++) {
    ll x;scanf("%lld",&x);printf("%d\n",query(sz,x));}return 0;
}