牛客练习赛 64（待补E-exgcd）

A.怪盗-1412

$$\begin{array}{c}\underbrace{111\dots 1}\\ ?\frac{n}{2}?\end{array}\begin{array}{c}\underbrace{444\dots 4}\\ m\end{array}\begin{array}{c}\underbrace{111\dots 1}\\ ?\frac{n}{2}?\end{array}\begin{array}{c}\underbrace{222\dots 2}\\ k\end{array}$$
上述排列方式最优，由此根据组合数即可求解。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
    IO;int T=1;cin>>T;while(T--){
    ll n,m,k;cin>>n>>m>>k;cout<<n/2*((n+1)/2)*m*k<<'\n';}return 0;
}

Dis2

与某个点距离为2的点有三种①父亲的父亲②儿子的儿子③兄弟节点
跑dfs统计以下即可
sz[u]表示u节点儿子的数量

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010,M=2*N;
int h[N],e[M],ne[M],idx;
int ans[N],sz[N];
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int n;
void dfs(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i]){
    int j=e[i];if(j==fa) continue;if(fa) {
    ans[fa]++;ans[j]++;}sz[u]++;dfs(j,u);}for(int i=h[u];i!=-1;i=ne[i]){
    int j=e[i];if(j==fa) continue;ans[j]+=sz[u]-1;}
}
int main()
{
    IO;int T=1;//cin>>T;while(T--){
    memset(h,-1,sizeof h);cin>>n;for(int i=1;i<n;i++){
    int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1,0);for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';}return 0;
}

C.序列卷积之和

一步一步推式子，预处理各种前缀和。真的无脑暴力

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200010：
const ll mod=1e9+7;
ll a[N],b[N],c[N],d[N],e[N],f[N];
int n;
int main()
{
    IO;int T=1;//cin>>T;while(T--){
    cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) b[i]=(b[i-1]+a[i])%mod;for(int i=1;i<=n;i++) c[i]=(c[i-1]+a[i]*b[i-1]%mod)%mod;for(int i=1;i<=n;i++) d[i]=(d[i-1]+b[i]*b[i]%mod)%mod;for(int i=1;i<=n;i++) e[i]=(e[i-1]+b[i])%mod;for(int i=1;i<=n;i++) f[i]=(f[i-1]+c[i])%mod;ll res=0;for(int i=1;i<=n;i++)   res=(res+d[n]-d[i-1]-b[i-1]*(e[n]-e[i-1])%mod-f[n]+f[i-1]+(n-i+1)*c[i-1]%mod)%mod;cout<<(res+mod)%mod<<'\n';}return 0;
}

D.宝石装箱

学习自大佬题解

首先先说一下错排，虽然我没做过错排，看到这个题首先想到如果每个箱子只对应一个不能放的宝石，那么直接可以容斥原理解决了，不过此题没有那么简单。看了上述文章学到错排还可以用递推方式解决这里记录一下。
状态表示：$f_i$错排规模为$i$时的方案数
状态计算：对于规模为$i$的错排，考虑第$i$个小球，不妨让第$i$个小球放在了第$j(1\le j<i)$个箱子里（第$i$禁止放在第$i$个箱子里），那么考虑第$k$个小球是否放在了第$i$个箱子，如果放在了第$i$个箱子那么很容易发现现在规模是$i?2$的错排方案，如果没有放在第$i$个箱子里那么现在规模是$i?1$的错排方案，又因为$k$有$i?1$种选择那么可以得到递推式$f_i=(i?1)\times (f_{i?1}+f_{i?2})$
经过一顿操作计算可得$$f_n=n![\frac{1}{2!}?\frac{1}{3!}+?+(?1{)}^n\frac{1}{n!}]$$
不难看出上式和容斥原理得出的答案相同。

容斥原理后现在需要求得至少{1,2,3,…,n}\{1,2,3,\dots,n\}{ 1,2,3,…,n}个盒子不合法的情况，直接上上述大佬题解结论：
状态表示：$f_{(i,j)}$对于只考虑前$i$种盒子，$j$个盒子不合法的方案数
状态转移：考虑最后一步第$i$个盒子是否合法易得出$$f_{(i,j)}=f_{(i?1,j)}+f_{(i?1,j?1)}\times cn{t}_i$$$cn{t}_i$是第$i$个箱子不能放的小球数量

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=8010;
const ll mod=998244353;
ll f[2][N],fact[N];
int cnt[N],n;
int main()
{
    IO;int T=1;//cin>>T;while(T--){
    cin>>n;for(int i=1;i<=n;i++){
    int a;cin>>a;cnt[a]++;}fact[0]=1;for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;f[0][0]=f[1][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)f[i&1][j]=(f[i-1&1][j]+f[i-1&1][j-1]*cnt[i]%mod)%mod;ll res=fact[n];for(int i=1,k=-1;i<=n;i++,k*=-1) res=(res+k*fact[n-i]*f[n&1][i])%mod;cout<<(res+mod)%mod<<'\n';}return 0;
}

这个dp太妙了吧，递推太精髓了。

E.红色的樱花

待补
要加油哦~