这场比赛还是比较水的
A,B,C跳过
D题dij把点权和边权都转换为边权即可
E题DP
可以用\(map\)存一下等差数列的差
先说\(O(n^4)\),\(f_{len,i,j,t}\)分别表示长度,现在在\(i\),上一个在\(j\)
显然动态转移方程就有了\(f_{len,i,j,k}=\sum_{k=1}^{k=j-1} f_{len-1,j,k,t}\)
点击查看代码
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 85,mod=998244353;
ll n,m,a[N],ans[N];
map <ll,ll> f[N][N][N];
main()
{
speed();
cin>>n;
ll mi=1e9,mx=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];mi=min(mi,a[i]);
mx=max(mx,a[i]);
}
for(int i=1;i<=n;i++)
{
// f[1][i][i][0]=1;
for(int j=1;j<=i-1;j++)
{
f[2][i][j][(ll)(a[i]-a[j])]=1;
}
}
for(int le=3;le<=n;le++)
{
// ll ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i-1;j++)
{
ll t=a[i]-a[j];
for(int k=1;k<=j-1;k++)
if(a[j]-a[k]==t)
f[le][i][j][t]=(f[le-1][j][k][t]+f[le][i][j][t])%mod;
ans[le]=(ans[le]+f[le][i][j][t])%mod;
// cout<<le<<" "<<f[le][i][j][t]<<endl;
}
}
// cout<<le<<" "<<ans<<endl;
}
for(int k=1;k<=n;k++)
{
if(k==1)cout<<n<<" ";
else if(k==2)cout<<1ll*n*(n-1)/2<<" ";
else
{
// ll ans=0;
// for(int i=mi;i<=mx;i++)
cout<<ans[k]<<" ";
}
}
return 0;
}
然后就水过了，其实我们还可以压缩提下状态，\(map\)结构体
把前三维全部压成一维，代码如下(借的\(qinyun\)对的)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
#define CLOSE() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define GG puts("============================")
#define Ct(x); if(x)puts("Yes");else puts("No");
#define CT(x); if(x)puts("YES");else puts("NO");
#define ct(x); if(x)puts("yes");else puts("no");
#define pii pair<int,int>
#define fi first
#define se second
#define re register
#define int ll
#define pt(x) putchar(x)
#define M(x,y) memset(x,y,sizeof x)
inline ll read()
{
re ll ans=0;bool f=0;re char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())ans=(ans<<1)+(ans<<3)+(ch^48);
return f?~ans+1:ans;
}
void print(ll n)
{
if(n<0)putchar('-'),n=-n;
if(n>9)print(n/10);
putchar(n%10+48);
}
void _print(ll n)
{
print(n);
pt(' ');
}
void __print(ll n)
{
print(n);
pt('\n');
}
struct node
{
int i,d,len;
bool operator < (const node a) const
{
if(i!=a.i)return i<a.i;
if(d!=a.d)return d<a.d;
return len<a.len;
}
};
const int mod=998244353;
map<node,int>mp;
int a[100],t[100],ans[100];
signed main()
{
int n=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=n;++i)
{
for(int j=1;j<i;++j)
for(int l=1;l<=n;++l)
{
if(l==1)++mp[(node){i,a[i]-a[j],l}],t[l+1]=(t[l+1]+1)%mod;
else mp[(node){i,a[i]-a[j],l}]=(mp[(node){i,a[i]-a[j],l}]+mp[node{j,a[i]-a[j],l-1}])%mod,t[l+1]=(t[l+1]+mp[node{j,a[i]-a[j],l-1}])%mod;
// if(l==2)cout<<i<<' '<<j<<' '<<t[3]<<" "<<mp[node{j,a[i]-a[j],l-1}]<<endl;
// cout<<i<<" "<<j<<' '<<mp[{3,0,1}]<<endl;
}
}
_print(n);
for(int i=2;i<=n;++i)
_print(t[i]);
return 0;
}
/*
10
1 1 1 1 1 1 1 1 1 1
4
1 1 1 1
*/
F题 鸽了
G题
AC自动机板子