妈的挂分挂麻了，怒挂 55+100 分，菜死了
T1 根号分类把，经典结论就是 $\sum a_i=n$ 的话 $a_i$ 至多有 $\sqrt n$ 种取值，且 $a_i\ge\sqrt n$ 的至多 $\sqrt n$ 项
#pragma GCC optimize("Ofast")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define st first
#define nd second
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return f?x:-x;
}
const int N=2e5+5,SQ=452,mo=998244353;
int cont[SQ][SQ],n,B,Bq=-1,m,q,ans[SQ][SQ],gt[N],re[N],out[N];
vector<int> vec[N],bef[N];
vector<pair<int,int>> ask[N];
pair<int,int> st[N];
void red(int &x){
if(x>=mo)x-=mo;
}
signed main(){
// freopen("A.in","r",stdin);
// freopen("r.out","w",stdout);
n=read();
for(int i=1;i<=n;++i){
int L=read();
st[i]={L,i};
m+=L;
while(L--){
bef[i].push_back(read());
}
}
sort(st+1,st+n+1);
for(int i=1;i<=n;++i){
gt[st[i].nd]=i;
re[i]=st[i].nd;
vec[i]=bef[re[i]];
}
B=ceil(sqrt(m));
for(int i=1;i<=n;++i){
if(vec[i].size()<B){
Bq=i;
}
else break;
}
for(int i=1;Bq+i<=n;++i){
for(int j=i;Bq+j<=n;++j){
for(int k=0;k<vec[Bq+j].size();++k){
/*n sqrt n*/ red(ans[i][j]+=vec[Bq+j][k]*vec[Bq+i][k%vec[Bq+i].size()]%mo);
}
}
}
q=read();
for(int i=1;i<=q;++i){
int x=read(),y=read();
x=gt[x],y=gt[y];
if(x<y)swap(x,y);
ask[x].push_back({y,i});
}
for(int i=1;i<=n;++i){
if(i<=Bq){
for(pair<int,int> j:ask[i]){
int rot=0;
for(int k=0;k<vec[i].size();++k){
red(rot+=vec[i][k]*vec[j.st][k%vec[j.st].size()]%mo);
}
out[j.nd]=rot;
}
}
else{
memset(cont,0,sizeof(cont));
for(int j=1;j<B;++j){
for(int k=0;k<vec[i].size();++k){
red(cont[j][k%j]+=vec[i][k]);
}
}
for(pair<int,int> j:ask[i]){
int rot=0;
if(j.st<=Bq){
for(int k=0;k<vec[j.st].size();++k){
red(rot+=vec[j.st][k]*cont[vec[j.st].size()][k]%mo);
}
}
else rot=ans[j.st-Bq][i-Bq];
out[j.nd]=rot;
}
}
}
for(int i=1;i<=q;++i){
printf("%lld\n",out[i]);
}
return 0;
}
T2 应该是什么计数dp，居然不会
T3 想了一会，就是在图上乱搞，先把树的部分扔掉，然后把度数大于 $2$ 的点弄出来，至多有 $2m-2n$ 个，然后特殊点直接要么是链，要么是自环，枚举一下集合划分就行了：
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return f?x:-x;
}
const int N=2e5+10,mo=1e9+7;
inline int qpow(int x,int t){
int ret=1;
for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
return ret;
}
int n,m,k,f[N],freenode,deg[N],inr[N],vis[N],g[N],h[N],seq[N],pcnt,re[30],gt[N],res[30],ans;
vector<int> G[N],path[30][30];
queue<int> q;
int kill_tree(){
int tot=0;
for(int i=1;i<=n;++i){
if(deg[i]==1)q.push(i);
}
while(q.size()){
int u=q.front();
++tot;
vis[u]=1;
q.pop();
for(int v:G[u])if(!vis[v]){
if(--deg[v]==1)q.push(v);
}
}
return tot;
}
void dfs1(int u,int fa,int rt,int dep,int tag){
if(gt[u]&&!tag){
path[gt[rt]][gt[u]].push_back(dep);
return;
}
for(int v:G[u])if(v!=fa)if(!vis[v]){
dfs1(v,u,rt,dep+1,0);
}
}
int solve(){
int ret=1,maxn=1;
for(int i=1;i<=pcnt;++i){
maxn=max(maxn,res[i]);
for(int j=i+1;j<=pcnt;++j){
for(int l:path[i][j]){
if(res[i]==res[j]){
ret=ret*f[l]%mo;
}
else{
ret=ret*g[l]%mo;
}
}
}
for(int l:path[i][i]){
if(!inr[l]){
ret=ret*f[l]%mo;
}
inr[l]^=1;
}
}
for(int i=k;i>k-maxn;--i)ret=ret*i%mo;
return ret;
}
void dfs2(int x,int last){
if(x>pcnt){
ans=(ans+solve())%mo;
return;
}
for(int i=1;i<=last+(x!=1);++i){
res[x]=i;
dfs2(x+1,max(last,i));
}
}
signed main(){
// freopen("C.in","r",stdin);
n=read(),m=read(),k=read();
f[1]=0,g[1]=1,h[1]=k-2;
for(int i=2;i<N;++i){
f[i]=(g[i-1]+h[i-1])%mo;
g[i]=(f[i-1]+h[i-1])%mo;
h[i]=((g[i-1]+f[i-1])*(k-2)%mo+h[i-1]*(k-3)%mo)%mo;
}
for(int i=1;i<=m;++i){
int x=read(),y=read();
++deg[x],++deg[y];
G[x].push_back(y);
G[y].push_back(x);
}
if(m+1==n){
printf("%lld\n",qpow(k-1,n-1)*k%mo);
}
else{
int kill=kill_tree();
for(int i=1;i<=n;++i){
if(vis[i])continue;
if(deg[i]==2)continue;
++pcnt;
re[pcnt]=i;
gt[i]=pcnt;
}
if(pcnt==0){
printf("%lld\n",k*f[n-kill]%mo*qpow(k-1,kill)%mo);
}
else{
for(int i=1;i<=pcnt;++i){
dfs1(re[i],0,re[i],0,1);
}
dfs2(1,1);
printf("%lld\n",ans*qpow(k-1,kill)%mo);
}
}
return 0;
}
chx