本文主要是介绍ABC 362 E - Count Arithmetic Subsequences,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题链接:E - Count Arithmetic Subsequences
题意:给出长度为n的数组,要求找出所有的等差数列,并且按照长度递增输出。
思路:dp,因为是要找出等差数列,并且这题的数据量极小,所以可以考虑设计dp数组,dp[i][j][k][v],i代表当前寻找的等差数列倒数第二项,j代表最后一项,k代表还需要寻找的长度,v代表当前判断的数,dp[i][j][k][v]代表以i为第一项,j为第二项,还要寻找k个数的等差数列数量。可以发现这样长度为1的等差数列不能判断,那么就直接特判输出就行了。
//冷静,冷静,冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
ll p[N];
ll f[81][81][81][81];
vector<ll> d;
ll n;
ll dfs(ll cs,ll now,ll len,ll x)
{if(len<=0)return 1;if(x>n)return 0;if(f[cs][now][len][x]!=-1)return f[cs][now][len][x];ll sum=0;if(p[x]-p[now]==p[now]-p[cs]){sum=sum+dfs(now,x,len-1,x+1);}sum%=mod;sum+=dfs(cs,now,len,x+1);sum%=mod;f[cs][now][len][x]=sum;return sum;
}
void Jiuyuan()
{cin>>n;for(int i=1;i<=n;i++){cin>>p[i];}memset(f,-1,sizeof(f));cout<<n<<' ';for(int len=2;len<=n;len++){ll ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){ans=ans+dfs(i,j,len-2,j+1);ans%=mod;}}cout<<ans<<' ';}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
// cin>>T;while(T--){Jiuyuan();}return 0;
}
这篇关于ABC 362 E - Count Arithmetic Subsequences的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!