BestCoder Round #72

由于第一次打，只能在div2打。（这么好的机会还没AK真是丢人）

T1 Clarke and chemistry

枚举题不解释（我不会告诉你我上来WA了四发的）

T2 Clarke and points

经典题目，计算一下x+y，x-y的最大值和最小值算一下即可。

T3 Clarke and MST

按位贪心，从高到低位尽量放1，用并查集判判是否可行。

---------------------------------------------------------------------

因为我太弱了div2只写完这几道（代码找不到了）。

T4 Clarke and math

这是一个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=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=100010;
const int mod=1000000007;
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,1,n) for(int j=i;j<=n;j+=i) (tmp[j]+=A.A[i]*B.A[j/i])%=mod;
    rep(i,1,n) A.A[i]=tmp[i],tmp[i]=0;
}
void pow(Seq& A,int m) {
    Seq T;T=A;m--;
    while(m) {
        if(m&1) mul(A,T);
        mul(T,T);m>>=1;
    }
}
void solve() {
    n=read(),k=read();
    rep(i,1,n) A.A[i]=1;
    rep(i,1,n) ans.A[i]=read();
    pow(A,k);mul(ans,A);
    rep(i,1,n) printf("%lld%c",ans.A[i],i==n?'
':' ');
}
int main() {
    dwn(T,read(),1) solve();
    return 0;
}

View Code

T5 Clarke and tree

一般涉及到点度数的题目就要用到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=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=55;
const int mod=1000000007;
typedef long long ll;
ll C[maxn][maxn],f[maxn][maxn][maxn];
int n,d[maxn];
void solve() {
    memset(f,0,sizeof(f));
    n=read();
    rep(i,1,n) d[i]=read();
    f[0][0][0]=1;
    rep(i,1,n) rep(j,0,i) rep(k,0,n-2) {
        f[i][j][k]=f[i-1][j][k];
        if(j) rep(k2,max(0,k+1-d[i]),k) (f[i][j][k]+=f[i-1][j-1][k2]*C[k][k-k2])%=mod;
    }
    rep(i,1,n) printf("%I64d%c",f[n][i][max(i-2,0)],i==n?'
':' ');
}
int main() {
    C[0][0]=1;
    rep(i,1,50) {
        C[i][0]=C[i][i]=1;
        rep(j,1,i-1) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    dwn(T,read(),1) solve();
    return 0;
}

View Code