牛客练习赛【64】非官方题解

前面的碎碎念：
因为比赛那天晚上朋友喊我去剧本杀，所以直接把比赛鸽了，直到今天才想起来把题解补上...

题解部分：

A-怪盗-1412
按照111...111444...444111...111222...222这样来分配数字个数能最大化1412子序列个数，其中两部分1的个数应该尽可能相近，所以答案就是n/2(n-n/2)mk。
时间复杂度：O(1)。
代码部分：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long T,a,b,c;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        printf("%lld\n",a/2*(a-a/2)*b*c);
    }
    return 0;
}

B-Dis2
遍历所有结点，对于i号结点，找到与其直接相连的其他结点，那些结点的度数-1就是对i号结点答案的贡献，因此全部加起来输出即可。
时间复杂度：O(n+m)。
代码部分：

#include<bits/stdc++.h>
using namespace std;

vector<int>R[200005];
int main()
{
    int i,j,k,n,ans;
    scanf("%d",&n);
    for(i=0;i<n-1;i++)scanf("%d%d",&j,&k),R[j].push_back(k),R[k].push_back(j);
    for(i=1;i<=n;i++)
    {
        for(j=ans=0;j<R[i].size();j++)
        {
            k=R[i][j];
            if(k==i)continue;
            ans+=R[k].size()-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

C-序列卷积之和
这题我是直接在纸上写写找出了规律，正经的数学推导如下：

因此前缀和预处理一下，从左到右扫一遍算每个数字的贡献就行了。
时间复杂度：O(n)。
代码部分：

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
long long a[200005],S[200005]={0};
int main()
{
    int i,n,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]),S[i]=(S[i-1]+a[i]*(n-i+1))%mod;
    for(i=1;i<=n;i++)ans=(ans+a[i]*(S[n]-S[i-1]+mod)%mod*i%mod)%mod;
    printf("%d\n",ans);
    return 0;
}

D-宝石装箱
一道DP+容斥定理的题，题解的思路比较清晰，因此我也采用他的方案。
我们设f(x)为选x个盒子放宝石的方案数，设g(x)为选x个盒子放不合法宝石的方案数，根据容斥定理，那么答案就是：f(n)g(0)-f(n-1)g(1)+f(n-2)g(2)+...+(-1)^nf(0)g(n)。其中f(x)=x!，接下来就讲讲如何求解g(x)。
很显然g(0)=1，我们设ai为第i个盒子能放ai个不合法宝石，那么有递推方程g(x)=g(x)+g(x-1)ai，这本质上其实就是一个背包问题。因此我们利用一个二重循环，即可求出g(x)，再根据上面我们的方案公式，即可求解出最后的答案。
时间复杂度：O(n^2)。
代码部分：

#include<bits/stdc++.h>
using namespace std;

const int mod=998244353;
int main()
{
    int i,j,n,a[8005]={0};
    long long DP[8005]={0},b[8005],ans=0;
    scanf("%d",&n);
    for(b[0]=i=1;i<=n;i++)scanf("%d",&j),a[j]++,b[i]=b[i-1]*i%mod;
    for(DP[0]=i=1;i<=n;i++)
        for(j=i;j>=1;j--)DP[j]=(DP[j]+DP[j-1]*a[i])%mod;
    for(i=0,j=1;i<=n;i++,j*=-1)ans=(ans+j*DP[i]*b[n-i]%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}