A
题意：
一个长度为n+m+k包含n个数字1,m个数字2和k个数字4的数组，最多可能有多少个子序列1412？
签到题
答案必为 n/2 * (n-n/2) * m * k 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,t;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        ll ans=0;
        if(n%2==0)
        {
            n/=2;
            ans=n*n*m*k;
        }
        else
        {
            n/=2;
            ans=n*(n+1)*m*k;
        }
        cout<<ans<<endl;
    }
    return 0;
}

B
题意：
给出一颗n个点n−1条边的树，点的编号为1,2,...,n−1,n，对于每个点i(1<=i<=n)，输出与点i距离为2的点的个数。
两个点的距离定义为两个点最短路径上的边的条数。
签到题
点的度代表与点距离为1的点数 那么全部与点距离为2的点数为与点i相连的点的度-1加起来

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int const N=2e5+5;
int n,tot,du[N],head[N],nex[N<<1],to[N<<1];///链式前向星
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
        du[u]++;du[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        for(int j=head[i];j;j=nex[j])///遍历i起点的每一条边
        {
            int v=to[j];///连接的点
            ans+=du[v]-1;
        }
        printf("%d\n",ans);
    }
}

C
菜鸡不懂什么卷积 所以看了半天题解后 写下这最容易理解的一种
先写出o(n4)的暴力 在逐步化解 就可以求出来了

  for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
            for(int i=l;i<=r;i++)
                for(int j=i;j<=r;j++)
                      ans+=(a[i]*a[j])%mod,ans%=mod; 
                      ///  a[i]*(a[i]+a[i+1]+...a[r])    设b[i]为 a[i]的前缀和
                      ///  a[i]*(b[r]-b[i-1])   消除第一重循环
                      ///  (a[l]+a[l+1]+...+a[r])*b[r] - (a[l]*b[l-1]+a[l+1]*b[l]+..+a[r]*b[r-1]) 设c[i]为a[i]*b[i-1]的前缀和
                      ///  (b[r]-b[l-1])*b[r]-(c[r]-c[l-1])  消除第二重循环
                      ///  (b[l]*b[l]+b[l+1]*b[l+1]+..+b[n]*b[n])-(b[l]+b[l+1]+..+b[n])*b[l-1] - (c[l]+c[l+1]+..+c[n]) + (n-l+1)*c[l-1]
                      ///   设 d[i]为b[i]*b[i]的前缀和   e[i]为b[i]的前缀和  f[i]为c[i]的前缀和
                      ///   (d[n]-d[l-1])-(e[n]-e[l-1])*b[l-1]-(f[n]-f[l-1])+(n-l+1)*c[l-1]  消除第三重循环

于是有

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
ll a[maxn],b[maxn],c[maxn],d[maxn],e[maxn],f[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=b[i-1]+a[i];///a[i]
        c[i]=c[i-1]+a[i]*b[i-1];///a[i]*b[i-1]
        d[i]=d[i-1]+b[i]*b[i];///b[i]*b[i]
        e[i]=e[i-1]+b[i];///b[i]
        f[i]=f[i-1]+c[i];///c[i]
        b[i]%=mod,c[i]%=mod,d[i]%=mod,e[i]%=mod,f[i]%=mod;
    }
    ll ans=0;
    for(int l=1;l<=n;l++){
            ans+=d[n]-d[l-1]-(b[l-1]*(e[n]-e[l-1]))%mod+mod-(f[n]-f[l-1]+mod)+(n-l+1)*c[l-1];
            ans=(ans+mod)%mod;
    }
    cout<<ans<<endl;
}

D
题意:
n颗宝石装进{n}n个箱子使得每个箱子中都有一颗宝石。第i颗宝石不能装入第a i个箱子。
求合法的装箱方案对998244353取模。
两种装箱方案不同当且仅当两种方案中存在一颗编号相同的宝石装在不同编号的箱子中。
首先我们要知道正面解这题是比较困难的 于是我们直接求全部方案在减去不合法的方案即合法方案
设g(x)为取x个箱子装不合法宝石的方案数 f(x)为x个箱子自由装宝石的方案数
由容斥原理我们知道 至少有i个宝石为非法的方案数为 g(x) * f(n-x)
由容斥原理答案为
图片说明
g(x)怎么求 g(x)为取x个箱子装不合法宝石的方案数 那么每当增加一个箱子时 能装不合法宝石的选择多了一种 不合法宝石的选择也多了一种 即
dp[j+1]=dp[j+1]+dp[j]*a[i] 

#include<bits/stdc++.h>
using namespace std;
const int N=8005;
const int mod=998244353;
typedef long long ll;
ll f[N],dp[N];
int n,a[N],x;
int main()
{
    f[0]=1;
    for(int i=1;i<N;i++) f[i]=f[i-1]*i%mod;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        a[x]++;
    }
    dp[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j>=0;j--)
            dp[j+1]=(dp[j+1]+dp[j]*a[i])%mod;///dp[i]表示有几个放错宝石的箱子 每增加一个箱子
                                             ///都要 dp[i]=dp[i]+dp[i-1]*a[i] 表示第i个箱子有几次放错方案
    ll ans=0;
    for(int i=0,k=1;i<=n;i++,k*=-1)
        ans=(ans+k*dp[i]*f[n-i]%mod)%mod;///容斥原理
    ans=(ans+mod)%mod;
    cout<<ans<<endl;
}