由于第一次打，只能在div2打。（这么好的机会还没AK真是丢人）
枚举题不解释（我不会告诉你我上来WA了四发的）
经典题目，计算一下x+y，x-y的最大值和最小值算一下即可。
按位贪心，从高到低位尽量放1，用并查集判判是否可行。
---------------------------------------------------------------------
因为我太弱了div2只写完这几道（代码找不到了）。
这是一个Dirichlet卷积，是满足结合律的，于是快速幂即可。（出题人明明可以把k出成10^9的却出成了10^5于是我没想到，差评）
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int mod=;
typedef long long ll;
struct Seq {
ll A[maxn];
}A,ans;
int n,k;
ll tmp[maxn];
void mul(Seq& A,Seq& B) {
rep(i,,n) for(int j=i;j<=n;j+=i) (tmp[j]+=A.A[i]*B.A[j/i])%=mod;
rep(i,,n) A.A[i]=tmp[i],tmp[i]=;
}
void pow(Seq& A,int m) {
Seq T;T=A;m--;
while(m) {
if(m&) mul(A,T);
mul(T,T);m>>=;
}
}
void solve() {
n=read(),k=read();
rep(i,,n) A.A[i]=;
rep(i,,n) ans.A[i]=read();
pow(A,k);mul(ans,A);
rep(i,,n) printf("%lld%c",ans.A[i],i==n?'\n':' ');
}
int main() {
dwn(T,read(),) solve();
return ;
}
一般涉及到点度数的题目就要用到prufer序列。
prufer序列的入门题目：BZOJ1005: [HNOI2008]明明的烦恼
因为每个prufer序列与一棵无根树是一一对应的，
所以这样一个问题：
有多少大小为K的无根树满足N个条件中的K个（即每个点的度数<=d[i]）
和这个问题：
有多少长度为K-2的序列满足N个条件中的K个（即每个数在序列中出现的次数<d[i]）
是等价的。
设f[i][j][k]表示考虑前i个限制，已经满足了j个限制的长度为k的序列有多少个。
1.不满足第i条限制： f[i][j][k]=f[i-1][j][k]
2.满足第i条性质： 则我们枚举插入数字i之前序列的长度k2，那么我们有k2 + 1个位置可以插入数字i，方案数为x1+x2+---+x(k2 + 1) = k - k2方程的解的个数*f[i-1][j-1][k2]，即C(k,k-k2)*f[i-1][j-1][k2]。
问题在O(N^4)的时间里完满解决。
（用生成函数和FFT可实现O(N^3logN)的效率）
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int mod=;
typedef long long ll;
ll C[maxn][maxn],f[maxn][maxn][maxn];
int n,d[maxn];
void solve() {
memset(f,,sizeof(f));
n=read();
rep(i,,n) d[i]=read();
f[][][]=;
rep(i,,n) rep(j,,i) rep(k,,n-) {
f[i][j][k]=f[i-][j][k];
if(j) rep(k2,max(,k+-d[i]),k) (f[i][j][k]+=f[i-][j-][k2]*C[k][k-k2])%=mod;
}
rep(i,,n) printf("%I64d%c",f[n][i][max(i-,)],i==n?'\n':' ');
}
int main() {
C[][]=;
rep(i,,) {
C[i][]=C[i][i]=;
rep(j,,i-) C[i][j]=(C[i-][j]+C[i-][j-])%mod;
}
dwn(T,read(),) solve();
return ;
}