Codechef July Challenge 2020 简要题解

这次题目相对比较难，后面几个题都是往常压轴题的难度。

Missing a Point

略

Chefina and Swaps

略

Doctor Chef

略

Chef and Dragon Dens

略

LCM Constraints

无限解当且仅当存在一个点没有边相连且存在一个合法方案，可以最后简单特判，下面不考虑这种情况，假定每个点都有边相连。
显然每个质因子可以分开考虑，对某个特定的质因子，相当于给定了$M$个$\max (A_{X_i},A_{Y_i})=R_i$的限制。
这里$R_i$可以不相同，看起来不太好做，不过注意到若存在$X_i=X_j$且$R_i<R_j$，则必然有$A_{X_i}\le R_i$且$A_{Y_j}=R_j$，将限制$j$换成$(Y_j,Y_j)$是等价的。这个过程可以用BFS完成，中间要不断判断是否有解，无解可以直接终止。
经过上面的处理后，就可以使得每个连通块的所有限制的$R$都相等，那么可以对每个连通块分开计算了。对于一个连通块，每个点$X$的状态只有$A_X=R$或$0\le A_X<R$两种，而$0\le A_X<R$的点需要形成一个独立集。
于是问题转化为对于一个大小为$k$的独立集，有$R^k$的贡献，问所有独立集的贡献和。这里可以采用一些高效的独立集搜索算法，不过这里的$N$不太大，使用一个折半状压DP即可。
具体的，将点集分为大小相近的集合$L$和$R$，则一个独立集$S=S_l\cup S_r$（$S_l?L,S_r?R$），需要满足$S_l$和$S_r$均为独立集，且$N(S_l)\cap S_r=?$（$N(S)$为与$S$相邻的点的集合）。考虑枚举所有$S_l$，则$S_r?R?N(S_r)$，预处理出所有的$S_r$并跑一个FMT即可。
单组数据时间复杂度为$\mathcal{O}(|p|(N?2^{\frac{N}{2}}+M))$。

#include <bits/stdc++.h>
#define MOD 1000000007
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;void fwt(int *p,int len) {
    for(int i=1;i<len;i<<=1)for(int j=0;j<len;j++)if (j&i) p[j]=(p[j]+p[j^i])%MOD;
}struct Edge {
    int s,t,v,next;Edge() {
    }Edge(int a,int b,int c,int d):s(a),t(b),v(c),next(d) {
    }bool operator < (const Edge & b) const {
    return v<b.v;}
};Edge e[20005];
int head[40],minn[40];
bool vis1[40],vis2[10005],vis3[40];
queue <int> q;Edge ee[5][10005];int num[40],id[40],cnt;
int sumv[1<<20];
ll val[40];void dfs(int x) {
    vis1[x]=1;num[++cnt]=x;id[x]=cnt;for(int i=head[x];i;i=e[i].next)if (!vis2[(i+1)>>1]&&!vis1[e[i].t]) dfs(e[i].t); 
}int solve(int n,int m,int d) {
    memset(head,0,sizeof(head));memset(minn,0x3f,sizeof(minn));memset(vis1,1,sizeof(vis1));memset(vis2,0,sizeof(vis2));memset(vis3,0,sizeof(vis3));sort(ee[d]+1,ee[d]+m+1);int tot=0;for(int i=1;i<=m;i++) {
    int x=ee[d][i].s,y=ee[d][i].t,v=ee[d][i].v;vis1[x]=vis1[y]=0;if (x==y) continue;e[++tot]=Edge(x,y,v,head[x]);head[x]=tot;e[++tot]=Edge(y,x,v,head[y]);head[y]=tot;minn[x]=min(minn[x],v);minn[y]=min(minn[y],v);}for(int i=1;i<=m;i++) {
    int x=ee[d][i].s,y=ee[d][i].t,v=ee[d][i].v;if (x!=y) continue;if (minn[x]<v) return -1;if (minn[x]>v) {
    if (vis3[x]) return -1;minn[x]=v;}vis3[x]=1;}for(int i=1;i<=n;i++) q.push(i);while (!q.empty()) {
    int x=q.front();q.pop();for(;;) {
    while (head[x]&&vis2[(head[x]+1)>>1]) x=e[head[x]].next;if (!head[x]||e[head[x]].v<=minn[x]) break;int y=e[head[x]].t,v=e[head[x]].v;if (minn[y]<v) return -1;if (minn[y]>v) {
    if (vis3[y]) return -1;minn[y]=v;}q.push(y);vis3[y]=1;vis2[(head[x]+1)>>1]=1;}}ll ans=1;for(int i=1;i<=n;i++)if (!vis1[i]) {
    int v=minn[i];cnt=0;dfs(i);int sz1=(cnt>>1),sz2=cnt-sz1;memset(sumv,0,sizeof(int)*(1<<sz1));memset(val,0,sizeof(val));for(int j=1;j<=cnt;j++) {
    int x=num[j];for(int k=head[x];k;k=e[k].next)if (!vis2[(k+1)>>1]) {
    int u=e[k].t;val[j-1]|=(1LL<<(id[u]-1));}}for(int j=0;j<(1<<sz1);j++) {
    bool ok=1;ll s=1;for(int k=0;k<sz1;k++)if ((j>>k)&1) {
    if ((val[k]&j)||vis3[num[k]+1]) {
    ok=0;break;}s=s*v%MOD;}if (!ok) continue;sumv[j]=s;}fwt(sumv,1<<sz1);ll sum=0;for(int j=0;j<(1<<sz2);j++) {
    bool ok=1;ll s=1;int st=0;for(int k=0;k<sz2;k++)if ((j>>k)&1) {
    if (((val[sz1+k]>>sz1)&j)||vis3[num[k+sz1+1]]) {
    ok=0;break;}s=s*v%MOD;st|=(val[sz1+k]&((1<<sz1)-1));}if (!ok) continue;sum=(sum+s*sumv[st^((1<<sz1)-1)])%MOD;}ans=ans*sum%MOD;}return ans;
}map <int,int> mp;
bool vis[5][10005];
pr a[10005];
int siz[5];int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    int sz=0;mp.clear();memset(vis,0,sizeof(vis));memset(siz,0,sizeof(siz));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {
    int x,y,z;scanf("%d%d%d",&x,&y,&z);a[i]=pr(x,y);for(int j=1;j<=z;j++) {
    int u,v;scanf("%d%d",&u,&v);if (!mp.count(u)) mp[u]=sz++;vis[mp[u]][i]=1;ee[mp[u]][++siz[mp[u]]]=Edge(x,y,v,0);}}for(int i=0;i<sz;i++)for(int j=1;j<=m;j++)if (!vis[i][j]) ee[i][++siz[i]]=Edge(a[j].FR,a[j].SE,0,0);ll ans=1;bool ok=1;for(int i=0;i<sz;i++) {
    ll s=solve(n,m,i);if (s==-1) {
    ok=0;break;}ans=ans*s%MOD;}if (!ok) {
    puts("0");continue;} memset(vis1,0,sizeof(vis1));for(int i=1;i<=m;i++)vis1[a[i].FR]=vis1[a[i].SE]=1;for(int i=1;i<=n;i++)if (!vis1[i]) {
    ok=0;break;}if (!ok) {
    puts("-1");continue;}printf("%lld\n",ans);}return 0;
}

Weird Product

令$S_i={\sum }_{j=1}^i{A}_j?X^{j?1}$，则$W(l,r{)}^2=?X^{?2(l?1)}?(S_{l?1}?S_r)?(S_r?S_{l?1})$。于是如果能快速计算${\prod }_{i=0}^n{\prod }_{j?=i}(S_i?S_j)$，就可以方便得出答案。
令$F(x)={\prod }_{i=0}^n(x?S_i)$，根据洛必达法则，上式即为${\prod }_{i=0}^n{F}^{\prime }(S_i)$。那么考虑分治乘出$F(x)$，求导即可得到$F^{\prime }(x)$，对$F^{\prime }(x)$在$x=S_i$处多点求值即可。
单组数据时间复杂度为$\mathcal{O}(N{\log }^{2}N)$。

#include <bits/stdc++.h>
#define MOD 998244353using namespace std;typedef long long ll;ll pow_mod(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}const int Maxn=1<<18;ll *w[18];void ntt_init() {
    for(int i=2,t=0;i<=Maxn;i<<=1,t++) {
    w[t]=new ll[i>>1];ll wn=pow_mod(3,(MOD-1)/i);w[t][0]=1;for(int j=1;j<(i>>1);j++) w[t][j]=w[t][j-1]*wn%MOD; }
}void rev(ll *p,int len) {
    int j=len>>1;for(int i=1;i<len-1;i++) {
    if (i<j) swap(p[i],p[j]);int k=len>>1;while (j>=k) {
    j-=k;k>>=1;}if (j<k) j+=k;}
} void ntt(ll *p,int len,int check) {
    rev(p,len);for(int i=2,t=0;i<=len;i<<=1,t++)for(int j=0;j<len;j+=i)for(int k=j;k<j+(i>>1);k++) {
    ll u=p[k];ll v=w[t][k-j]*p[k+(i>>1)];p[k]=(u+v)%MOD;p[k+(i>>1)]=(u-v)%MOD;}if (check==-1) {
    reverse(p+1,p+len);ll nev=pow_mod(len,MOD-2);for(int i=0;i<len;i++) p[i]=(p[i]+MOD)*nev%MOD;}
}void getinv(ll *p,ll *q,int len) {
    static ll t1[Maxn];if (len==1) {
    q[0]=1;return;}getinv(p,q,len>>1);memcpy(t1,p,sizeof(ll)*len);memset(t1+len,0,sizeof(ll)*len);ntt(q,len<<1,1);ntt(t1,len<<1,1);for(int i=0;i<(len<<1);i++) q[i]=q[i]*(2LL-q[i]*t1[i]%MOD)%MOD;ntt(q,len<<1,-1);memset(q+len,0,sizeof(ll)*len);
}void mul(vector<int> &a,vector<int> &b,vector<int> &c) {
    static ll t1[Maxn],t2[Maxn];int len=1;while (len<=a.size()+b.size()) len<<=1;for(int i=0;i<a.size();i++) t1[i]=a[i];for(int i=a.size();i<len;i++) t1[i]=0;for(int i=0;i<b.size();i++) t2[i]=b[i];for(int i=b.size();i<len;i++) t2[i]=0;ntt(t1,len,1);ntt(t2,len,1);for(int i=0;i<len;i++) t1[i]=t1[i]*t2[i]%MOD;ntt(t1,len,-1);c.resize(a.size()+b.size()-1);for(int i=0;i<c.size();i++) c[i]=t1[i];
}void mulT(vector<int> &a,vector<int> &b,vector<int> &c,int n) {
    static ll t1[Maxn],t2[Maxn];int len=1;while (len<=a.size()||len<=((max((int)b.size(),n)+1)<<1)) len<<=1;for(int i=0;i<a.size();i++) t1[i]=a[i];for(int i=a.size();i<len;i++) t1[i]=0;for(int i=0;i<b.size();i++) t2[b.size()-i-1]=b[i];for(int i=b.size();i<len;i++) t2[i]=0;ntt(t1,len,1);ntt(t2,len,1);for(int i=0;i<len;i++) t1[i]=t1[i]*t2[i]%MOD;ntt(t1,len,-1);c.resize(n);for(int i=0;i<n;i++) c[i]=t1[b.size()+i-1];
}vector <int> f[400000],g[400000];
ll num[100005],ans[100005];void dfs1(int l,int r,int o) {
    if (l==r) {
    f[o].resize(2);f[o][0]=1;f[o][1]=(MOD-num[l])%MOD;}else {
    int m=((l+r)>>1);dfs1(l,m,o*2);dfs1(m+1,r,o*2+1);mul(f[o*2],f[o*2+1],f[o]);}
}void dfs2(int l,int r,int o) {
    if (l==r) ans[l]=g[o][0];else {
    int m=((l+r)>>1);mulT(g[o],f[o*2+1],g[o*2],m-l+1);mulT(g[o],f[o*2],g[o*2+1],r-m);dfs2(l,m,o*2);dfs2(m+1,r,o*2+1);}
}void evaluation(int n) {
    static ll t1[Maxn],t2[Maxn];dfs1(1,n,1);int len=1;while (len<=n+1) len<<=1;memset(t1,0,sizeof(ll)*(len<<1));memset(t2,0,sizeof(ll)*(len<<1));for(int i=0;i<=n;i++) t1[i]=f[1][i];getinv(t1,t2,len);vector <int> full,inv;full.resize(n);inv.resize(n);for(int i=0;i<n;i++) {
    full[i]=(ll)(i+1)*f[1][n-i-1]%MOD;inv[i]=t2[i];}mulT(full,inv,g[1],n);dfs2(1,n,1);
}int main() {
    ntt_init();int cases;scanf("%d",&cases);for(;cases;cases--) {
    int n;ll m;scanf("%d%lld",&n,&m);ll sum=0,v=1;num[1]=0;for(int i=1;i<=n;i++) {
    int x;scanf("%d",&x);sum=(sum+x*v)%MOD;v=v*m%MOD;num[i+1]=sum;}evaluation(n+1);ll s=1;for(int i=1;i<=n+1;i++) s=s*ans[i]%MOD;ll inv=pow_mod(m,MOD-2);sum=0;for(int i=1;i<=n;i++) sum=(sum+2LL*i*(n-i))%(MOD-1);s=s*pow_mod(inv,sum)%MOD*((((ll)n*(n+1)>>1)&1)?MOD-1:1)%MOD;printf("%lld\n",s);}return 0;
} 
/* 1 3 2 1 2 3 */

Expected Repetitions

特殊处理$|r|=|s|$的情况，下面默认$|r|<|s|$。
考虑枚举左端点$l$和$|r|$，那么容易知道满足$|r|<|s|$的合法右端点个数为$LCP(S[l,N],S[l+|r|,N])$。
现在考虑用SAM建出原串的后缀树。对于一个后缀树上的节点$x$，它不同儿子子树中的任两个后缀都会对答案有贡献，且若选了后缀$S[p,N]$和$S[q,N]$（$p<q$），令代价前缀和数组为$sum$，则对答案贡献为$maxle{n}_x?(su{m}_q?su{m}_p)$。那么做法就比较显然了，考虑在后缀树上线段树合并，线段树上每个节点维护对应区间中当前后缀个数和这些后缀的$sum$的和，那么拆开贡献的计算式子，可以在线段树合并的同时维护。
单组数据时间复杂度为$\mathcal{O}(N\log N)$。

#include <bits/stdc++.h>
#define MOD 998244353
#define last last2using namespace std;typedef long long ll;ll pow_mod(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}ll sum;
int fir[500005];namespace SGT {
    const int Maxn=30000000;int ch[Maxn][2],siz[Maxn],sumv[Maxn],tot;inline int newnode() {
    tot++;ch[tot][0]=ch[tot][1]=0;siz[tot]=sumv[tot]=0;return tot;
}int update(int l,int r,int o,int p) {
    if (!o) o=newnode();siz[o]++;sumv[o]=(sumv[o]+fir[p])%MOD;if (l==r) return o;else {
    int m=((l+r)>>1);if (m>=p) ch[o][0]=update(l,m,ch[o][0],p);else ch[o][1]=update(m+1,r,ch[o][1],p);return o;}
}int merge(int x,int y) {
    if (!x) return y;if (!y) return x;sum=(sum+(ll)sumv[ch[x][1]]*siz[ch[y][0]])%MOD;sum=(sum+(ll)sumv[ch[y][1]]*siz[ch[x][0]])%MOD;sum=(sum-(ll)sumv[ch[x][0]]*siz[ch[y][1]]%MOD+MOD)%MOD;sum=(sum-(ll)sumv[ch[y][0]]*siz[ch[x][1]]%MOD+MOD)%MOD;siz[x]+=siz[y];sumv[x]=(sumv[x]+sumv[y])%MOD;ch[x][0]=merge(ch[x][0],ch[y][0]);ch[x][1]=merge(ch[x][1],ch[y][1]);return x;
}}namespace SAM {
    int ch[1000005][26];
int fa[1000005],mx[1000005],bel[1000005];
int tot,last;void init() {
    tot=last=1;memset(ch[1],0,sizeof(ch[1]));bel[1]=0;
}void add(char x,int id) {
    x-='a';int p=last,np=++tot;memset(ch[np],0,sizeof(ch[np]));mx[np]=mx[p]+1;bel[np]=id;for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=np;if (!p) fa[np]=1;else {
    int q=ch[p][x];if (mx[q]==mx[p]+1) fa[np]=q;else {
    int nq=++tot;memcpy(ch[nq],ch[q],sizeof(ch[nq]));bel[nq]=0;mx[nq]=mx[p]+1;fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq;}}last=np;
}vector <int> e[1000005];
int root[1000005];ll dfs(int x,int n) {
    ll s=0;root[x]=0;if (bel[x]) root[x]=SGT::update(1,n,root[x],bel[x]);for(int i=0;i<e[x].size();i++) {
    int u=e[x][i];s=(s+dfs(u,n))%MOD;sum=0;root[x]=SGT::merge(root[x],root[u]);s=(s+sum*mx[x])%MOD;}return s;
}void build(char *s,int n) {
    for(int i=n;i>0;i--) add(s[i],i);for(int i=1;i<=tot;i++) vector<int>().swap(e[i]);for(int i=2;i<=tot;i++) e[fa[i]].push_back(i);
}}char str[500005];
int val[26];int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    scanf("%s",str+1);int n=strlen(str+1);for(int i=0;i<26;i++) scanf("%d",&val[i]);for(int i=1;i<=n;i++) fir[i]=(fir[i-1]+val[str[i]-'a'])%MOD;SAM::init();SAM::build(str,n);SGT::tot=0;ll s=SAM::dfs(1,n);for(int i=1;i<=n;i++)s=(s+fir[i]*(2LL*i-n+MOD))%MOD;s=s*pow_mod(((ll)n*(n+1)>>1)%MOD,MOD-2)%MOD;printf("%lld\n",s);}return 0;
} 

Expected Spanning Trees

注意到生成树之间对答案贡献是无关的，可以分别考虑每棵生成树对答案的贡献并求和。进一步的，可以发现某棵生成树对答案的贡献只跟它在初始图中有多少边出现有关。
首先考虑求出恰有$i$条边出现在初始图中的生成树个数。这是一个经典问题，考虑对于所有无向边，若它在初始图中出现设为$x$，否则设为$1$，用矩阵树定理求得行列式$F(x)$，则$[x^i]F(x)$即为恰好有$i$条边出现在初始图中的生成树个数。注意到$F(x)$次数不超过$n?1$，那么求出$F(x)$的过程可以考虑代入$x=1?n$分别求行列式再插值。
得到了$F(x)$后考虑如何求出答案，这是一个线性递推的过程，可以用矩阵乘法描述。但是这里的$Q$很大，不过转移矩阵固定，若我们将答案乘上${\left(\genfrac{}{}{0ex}{}{N}{2}\right)}^T$，打表可以发现特征根分别为$\left(\genfrac{}{}{0ex}{}{N}{2}\right)?2i$（$0\le i<N$）。那么用类似Codechef April Challenge 2020的A Leisurely Journey的技巧即可单次询问做$\mathcal{O}(N)$次快速幂求出答案（可以用费马小定理降幂后$\mathcal{O}(N\sqrt{MOD})$预处理，单次$\mathcal{O}(N)$询问）。
事实上有一个更简单的方式能推出最后的做法。考虑恰有$i$条边出现在初始图中的生成树对答案贡献的的EGF，显然是$e^{\left(\genfrac{}{}{0ex}{}{N?1}{2}\right)x}?(\frac{e^x+e^{?x}}{2}{)}^i?(\frac{e^x?e^{?x}}{2}{)}^{N?1?i}$。那么最终答案的EGF展开后可以写成${\sum }_{i=0}^{N?1}{a}_i?e^{((\genfrac{}{}{0ex}{}{N}{2})?2i)x}$的形式，只需要$\mathcal{O}(N)$次快速幂即可求出单项系数，跟上面的做法是本质相同的。
时间复杂度为$\mathcal{O}(N^4+N(\sqrt{MOD}+Q))$。

#include <bits/stdc++.h>
#define MOD 1000000007using namespace std;typedef long long ll;ll pow_mod(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}ll a[105][105];ll gause(int n) {
    ll s=1;for(int i=2;i<=n;i++) {
    if (!a[i][i]) {
    for(int j=i+1;j<=n;j++)if (a[j][i]) {
    for(int k=i;k<=n;k++) swap(a[i][k],a[j][k]);s=MOD-s;break;}}if (!a[i][i]) return 0;ll inv=pow_mod(a[i][i],MOD-2);for(int j=i+1;j<=n;j++)if (a[j][i]) {
    ll v=a[j][i]*inv%MOD;for(int k=i;k<=n;k++)if (a[i][k]) a[j][k]=(a[j][k]-a[i][k]*v)%MOD; }}for(int i=2;i<=n;i++) s=s*(a[i][i]+MOD)%MOD;return s;
}bool e[105][105];
ll val[105];ll f[105][105],g[105];void lagrange(int n) {
    static ll t1[105],t2[105];t1[0]=1;for(int i=1;i<=n;i++) {
    memset(a,0,sizeof(a));for(int j=1;j<n;j++)for(int k=j+1;k<=n;k++)if (e[j][k]) {
    a[j][j]=(a[j][j]+i)%MOD;a[k][k]=(a[k][k]+i)%MOD;a[j][k]=(a[j][k]-i+MOD)%MOD;a[k][j]=(a[k][j]-i+MOD)%MOD;}else {
    a[j][j]=(a[j][j]+1)%MOD;a[k][k]=(a[k][k]+1)%MOD;a[j][k]=(a[j][k]-1+MOD)%MOD;a[k][j]=(a[k][j]-1+MOD)%MOD;}val[i]=gause(n);for(int j=i;j>=0;j--) {
    t1[j]=t1[j]*(MOD-i)%MOD;if (j) t1[j]=(t1[j]+t1[j-1])%MOD;}}for(int i=1;i<=n;i++) {
    memcpy(t2,t1,sizeof(t2));for(int j=n;j>0;j--) t2[j-1]=(t2[j-1]+t2[j]*i)%MOD;ll s=1;for(int j=1;j<=n;j++)if (i!=j) s=s*(i-j+MOD)%MOD;s=pow_mod(s,MOD-2)*val[i]%MOD;for(int j=0;j<n;j++) f[0][j]=(f[0][j]+s*t2[j+1])%MOD;}
} const int Maxn=40000;ll num[105],d[105];
ll mi[2][105][Maxn];void build(int n) {
    static ll t1[105];t1[0]=1;for(int i=0;i<n;i++) {
    num[i]=((n*(n-1)>>1)-2*i+MOD)%MOD;for(int j=i+1;j>0;j--) t1[j]=(t1[j]+t1[j-1]*(MOD-num[i]))%MOD;mi[0][i][0]=1;for(int j=1;j<Maxn;j++) mi[0][i][j]=mi[0][i][j-1]*num[i]%MOD;ll v=mi[0][i][Maxn-1]*num[i]%MOD;mi[1][i][0]=1;for(int j=1;j<Maxn;j++) mi[1][i][j]=mi[1][i][j-1]*v%MOD;}for(int i=1;i<n;i++)for(int j=0;j<n;j++) {
    f[i][j]=f[i-1][j]*((n-1)*(n-2)>>1)%MOD;if (j) f[i][j]=(f[i][j]+f[i-1][j-1]*(n-j))%MOD;if (j<n-1) f[i][j]=(f[i][j]+f[i-1][j+1]*(j+1))%MOD;}for(int j=0;j<n;j++)for(int k=0;k<=j;k++) g[j]=(g[j]+f[k][n-1]*t1[j-k])%MOD;for(int i=0;i<n;i++) if (num[i]) {
    ll s1=0,inv=pow_mod(num[i],MOD-2);for(int j=n-1;j>=0;j--) s1=(s1*inv+g[j])%MOD;ll s2=1;for(int j=0;j<n;j++)if (j!=i) s2=s2*(1LL-inv*num[j]%MOD+MOD)%MOD;d[i]=s1*pow_mod(s2,MOD-2)%MOD;}for(int i=0;i<n;i++)if (!num[i]) {
    d[i]=g[0];for(int j=0;j<n;j++)if (j!=i) d[i]=(d[i]-d[j]+MOD)%MOD;}
}ll calc(int n,ll k) {
    k%=(MOD-1);int p=k/Maxn,q=k%Maxn;ll s=0;for(int i=0;i<n;i++) s=(s+d[i]*mi[0][i][q]%MOD*mi[1][i][p])%MOD;s=s*pow_mod((n*(n-1)>>1),MOD-1-k)%MOD;return s;
}int main() {
    int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x][y]=e[y][x]=1;}lagrange(n);build(n);for(int i=1;i<=k;i++) {
    ll x;scanf("%lld",&x);printf("%lld\n",calc(n,x));}return 0;
} 

Easy Geo xD

答案显然是满足$ax+by\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}c)$的整数对$(x,y)$数目（$x_1\le x\le x_2,y_1\le y\le y_2$）。
这个式子同时有$a$和$b$两个系数，处理起来比较困难。我们尽可能尝试把其中一个系数变为$1$。让所有系数在$\mathrm{m}\mathrm{o}\mathrm{d}c$意义下考虑（特判掉$a$和$b$中有$0$的情况），接着所有系数同除$\gcd (a,b,c)$（可能无解）。此时$\gcd (a,c)$仍可能不是$1$，令$u=\gcd (a,c)$，则$\gcd (b,u)=1$，于是令$y=y^{\prime }u+v$（$0\le v<u$），可以解出唯一可能的$v$。用$y^{\prime }$替换$y$并适当移项后可令所有系数均为$u$的倍数，再同除$u$即可令$\gcd (a,c)=1$，此时同余方程两边同乘$\mathrm{m}\mathrm{o}\mathrm{d}c$意义下$a^{?1}$即可将$a$化为$1$。
这样就简化了不少，再简单移项后问题大致可以描述为求$px\equiv y(\mathrm{m}\mathrm{o}\mathrm{d}q)$（$l_1\le x\le r_1,l_2\le y\le r_2$）的整数对$(x,y)$数目。
注意到$y$的范围是一个区间，简单差分后可以变为求$\mathcal{O}(1)$次${\sum }_{i=l_1}^{r_1}[pi\mathrm{m}\mathrm{o}\mathrm{d}q\le y]$的值。可以发现$[pi\mathrm{m}\mathrm{o}\mathrm{d}q\le y]=?\frac{pi}{q}???\frac{pi?y?1}{q}?$，分别计算两项的和，可以将问题转化为$\mathcal{O}(1)$次计算${\sum }_{i=0}^n?\frac{ai+b}{c}?$的值，这是类欧几里得算法的经典问题，可以在$\mathcal{O}(\log n)$的复杂度内计算一次。
总时间复杂度为$\mathcal{O}(T\log V)$。

#include <bits/stdc++.h>
#define MOD 1000000007
#define inv2 500000004using namespace std;typedef long long ll;void exgcd(ll a,ll b,ll &x,ll &y) {
    if (!b) {
    x=1;y=0;}else {
    exgcd(b,a%b,y,x);y-=(a/b)*x;}
}ll getinv(ll n,ll m) {
    ll x,y;exgcd(n,m,x,y);return (x%m+m)%m;
}inline ll S2(ll n) {
    return n*(n+1)%MOD*inv2%MOD;
}ll calc(ll a,ll b,ll c,ll n) {
    if (a>=c||b>=c) return ((a/c)*S2(n)+(b/c)*(n+1)+calc(a%c,b%c,c,n))%MOD;if (!a||!n) return (b/c)*(n+1)%MOD;ll m=(a*n+b)/c;return (n*m-calc(c,c-b-1,a,m-1)+MOD)%MOD;
}ll query(ll l,ll r,ll x,ll p,ll q) {
    ll s1=(calc(p,q,q,r)-calc(p,q-x-1,q,r)+MOD)%MOD;ll s2=((l)?(calc(p,q,q,l-1)-calc(p,q-x-1,q,l-1)+MOD)%MOD:0);return (s1-s2+MOD)%MOD;
}ll solve(ll a,ll b,ll c,ll d,ll l1,ll r1,ll l2,ll r2) {
    a%=c;b%=c;d%=c;ll t=__gcd(__gcd(a,b),c);if (d%t!=0) return 0;a/=t;b/=t;c/=t;d/=t;if (a>b) {
    swap(a,b);swap(l1,l2);swap(r1,r2);} if (!b) return (!d)?(r1-l1+1)*(r2-l2+1)%MOD:0;if (!a) {
    ll t=d*getinv(b,c)%c;l2=(l2-t+c-1)/c;r2=((r2>=t)?(r2-t)/c:-1);return (l2<=r2)?(r1-l1+1)*(r2-l2+1)%MOD:0;}ll u=__gcd(a,c);ll p=d*getinv(b,u)%u;l2=(l2-p+u-1)/u;r2=((r2>=p)?(r2-p)/u:-1);if (l2>r2) return 0;d=(d-b*p%c+c)%c;a/=u;c/=u;d/=u;b%=c;ll v=getinv(a,c);b=b*v%c;d=d*v%c;d=(c-d%c)%c;b=(c-b%c)%c;l1+=d;r1+=d;ll s=(((r1/c)-(l1-1)/c)%MOD+MOD)*(r2-l2+1)%MOD;s=(s+query(l2,r2,r1%c,b,c))%MOD;s=(s-query(l2,r2,(l1-1)%c,b,c)+MOD)%MOD;return s;
}int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    ll l1,r1,l2,r2;scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);ll a,b,c,d;scanf("%lld%lld%lld%lld",&a,&b,&c,&d);printf("%lld\n",solve(a,b,c,d,l1,r1,l2,r2));}return 0;
}
/* 1 21 74 8 92 75 32 100 26 */