abc E 求调
  • 板块学术版
  • 楼主MicroSun/fendou
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/9/7 21:42
  • 上次更新2024/9/8 09:10:15
查看原帖
abc E 求调
514700
MicroSun/fendou楼主2024/9/7 21:42

rt,思路是设 fif_i 为把 1∼i1\sim i 分裂成符合题目要求的连续子序列的方法数,转移 fi=∑∑k=j+1iak≠Kfjf_i=\sum_{\sum_{k=j+1}^{i} a_k\ne K} f_j,容斥+前缀和即可。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define fst first
#define scd second
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,s,e) for(int i=s;i>=e;i--)

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

const int N=2e5+10,mod=998244353;

ll a[N];
void solve(){
	ll n,k;
	cin>>n>>k;
	rep(i,1,n) cin>>a[i];
	map<ll,ll> mp;
	mp[a[1]]=1;
	ll tt=a[1],sum=1;
	rep(i,2,n+1){
		tt+=a[i];
		ll tmp=((sum-mp[tt-k])%mod+mod)%mod;
		sum=((sum+tmp)%mod+mod)%mod;
		mp[tt]=((mp[tt]+tmp)%mod+mod)%mod;
		if(i==n+1) cout<<tmp;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
    return 0;
}
2024/9/7 21:42
加载中...