NFLS-10.08-div2-DP与计数

Posted on By 张, 高畅 NFLS-10.08-div2-DP与计数无评论

T0

决定我命运的一天原本还有一天。
结果 CCF 你竟然推迟发布最终成绩了。
11.09 \rightarrow 11.20
属于是强制续命(?)

今天也是稍有的 NFLS 专题训练赛。
现在满脑子都是DP和求逆元。

T1

原题链接

做法

$m$ 个灯会将区间分为 $m+1$ 段。
答案是$\frac{(n-m)!}{\prod_{i=1}^t li!}\prod\limits{i=1}^t 2^{l_i-1}t=m+1，l_i$代表每段长度。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,mod=1e9+7;
typedef long long LL;
int n,m,pos[N];
LL res=1;
LL infact[N],power2[N];
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d",&pos[i]);
    sort(pos+1,pos+m+1);
    pos[0]=0;
    pos[m+1]=n+1;
    sort(pos+1, pos+m+1);
    infact[0]=power2[0]=1;
    for(LL i=1;i<=n;i++)
    {
        infact[i]=infact[i-1]*quick_power(i,mod-2)%mod;
        power2[i]=(power2[i-1]<<1)%mod;
    }
    for(LL i=1;i<=n-m;i++)res=res*i%mod;
    for(LL i=0;i<=m;i++)
    {
        LL len=pos[i+1]-pos[i]-1;
        if(len<=0)continue;
        if(1<=i&&i<m)res=res*power2[len-1]%mod;
        res=res*infact[len]%mod;
    }
    printf("%lld",res);
    return 0;
}

T2

原题链接

做法

只需要先找到0的个数，记为cnt
在1-cnt中，寻找0的个数。
对于cnt+1-n，每一位的贡献\frac{C^2_n}{(cnt-i+1)^2}

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005,mod=998244353;
int n,a[N];
LL f[N];
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void work()
{
    int cnt=0,start=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cnt+=(!a[i]);
    }
    for(int i=1;i<=cnt;i++)
    {
        if(!a[i])start++;
    }
    f[start]=0;
    for(int i=start+1;i<=cnt;i++)f[i]=(f[i-1]+(1LL*(1LL*n*(n-1)/2LL)%mod*quick_power(1LL*(cnt-i+1)*(cnt-i+1)%mod,mod-2)%mod))%mod;
    printf("%lld\n",f[cnt]);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

T3

原题链接

做法

很显然，菊花图就是满足它的一个方案。
接下来，如果我们想去掉 (1,a) 的边，连上 (a,b) 的边，就必须满足：
$S-w{1->a}+w{a->b} \ge S会有:w{1->a} \le w{a->b}换言之，从a出发，到其他点的距离一定要比到1要长。
设dp{i,j}表示已经在图中加入了i个点，这些点到1号点的距离最大值为j时，有多少种不同的构图方案。
会有:dp{i,j}=\sum{t=1}^{i-1}(\sum{x=0}^{j-1}dp{t,x})\cdot C^{i-t}{n-t}\cdot (k-j+1)^{{(i+t-3)(i-t)/2}}$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=255,mod=998244353;
LL n,k;
LL c[N][N],f[N][N],s[N][N];
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }   
    return res;
}
int main()
{
    for(LL i=0;i<N;i++)
    {
        for(LL j=0;j<=i;j++)
        {
            if(!j)c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
    scanf("%lld%lld",&n,&k);
    f[1][0]=1;
    for(LL i=0;i<=k;i++)s[1][i]=1;
    for(LL i=2;i<=n;i++)
    {
        for(LL j=1;j<=k;j++)
        {
            for(LL t=1;t<i;t++)f[i][j]=(f[i][j]+(1LL*s[t][j-1]%mod*c[n-t][i-t]%mod*quick_power(k-j+1,((i+t-3)*(i-t)/2)%mod)%mod))%mod;
            s[i][j]=(s[i][j-1]+f[i][j])%mod;
        }
    }
    LL res=0;
    for(LL i=1;i<=k;i++)res=(res+f[n][i])%mod;
    printf("%lld",res);
    return 0;
}

T4

原题链接

做法

答案\sum_{j=0}\limits^{n-1}m^{n-j} \cdot (2m-1)^j

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long LL;
LL n,m;
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
LL res=0;
int main()
{
    scanf("%lld%lld",&n,&m);
    res=quick_power(m,n);
    for(int i=0;i<n;i++)res=(res+(quick_power(m,n-i)*quick_power(2*m-1,i)%mod))%mod;
    printf("%lld",res);
    return 0;
}

T5

原题链接

做法

公式最简单的一题。
答案m^n+\sum_{i=0}\limits^{n-1}m^{n-i} \cdot {(2m-1)}^{i}

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long LL;
LL n,m;
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
LL res=0;
int main()
{
    scanf("%lld%lld",&n,&m);
    res=quick_power(m,n);
    for(int i=0;i<n;i++)res=(res+(quick_power(m,n-i)*quick_power(2*m-1,i)%mod))%mod;
    printf("%lld",res);
    return 0;
}

T6

原题链接

做法

每次以i为 root 去DFS并生成当前的 fa 数组，用倍增求出当前的 LCA 。
$f{i,j}=f{i,j-1}+f{i-1,j}*invinv为1e9+7的逆元。
每次的答案f{dj-d{lca},dk-d{lca}}，其中d_i表示i$ 节点的深度。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=205,mod=1e9+7;
const int inv=(mod+1)>>1;
typedef long long LL;
int n,m,res,d[N],fa[N][25],f[N][N];
vector<int>G[N];
int quick_power(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=1LL*res*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return res;
}
void dfs(int u,int father)
{
    d[u]=d[father]+1;
    fa[u][0]=father;
    for(int j=1;j<=20;j++)fa[u][j]=fa[fa[u][j-1]][j-1];
    for(int j:G[u])
    {
        if(j==father)continue;
        dfs(j,u);
    }
}
int LCA(int a,int b)
{
    if(d[a]<d[b])swap(a,b);
    for(int i=20;~i;i--)
    {
        if(d[fa[a][i]]>=d[b])a=fa[a][i];
    }
    if(a==b)return a;
    for(int i=20;~i;i--)
    {
        if(fa[a][i]!=fa[b][i])
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=1;i<=n;i++)f[0][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)f[i][j]=1LL*((LL)f[i-1][j]+(LL)f[i][j-1])*inv%mod;
    }
    for(int root=1;root<=n;root++)
    {
        dfs(root,0);
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<j;k++)
            {
                int lca=LCA(j,k);
                res=(res+f[d[j]-d[lca]][d[k]-d[lca]])%mod;
            }
        }
    }
    printf("%d",1LL*res*quick_power(n,mod-2)%mod);
    return 0;
}

T7

原题链接

做法

第二类Stiring数。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2005,mod=998244353;
typedef long long LL;
LL n,m,k,f[N][N];
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void work()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    LL res=0,inv=quick_power(m,mod-2);
    LL base=(m-(m/2))*quick_power(m,n-1)%mod*n%mod;
    for(LL i=1;i<=min(n,k);i++)
    {
        res=(res+(f[k][i]*base%mod))%mod;
        base=base*(m-(m/2))%mod*inv%mod*(n-i)%mod;
    }
    printf("%lld\n",res);
}
int main()
{
    f[1][1]=1;
    for(int i=2;i<N;i++)
    {
        for(int j=1;j<=i;j++)f[i][j]=(f[i-1][j-1]+(LL)j*f[i-1][j])%mod;
    }
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

T8,T9,T10

我不会了，请移步CQR/CYC/CYE的BLOG。

训练日志

发表回复