提出 #57550200

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long
#define ld long double
#define nl "\n"
#define rep(i,a,b) for(int i=a;i<b;i++)
#define reprev(i,a,b) for(int i=b-1;i>=a;i--)
#define all(c) c.begin(),c.end()
#define sz(c) (int)c.size()
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vvi vector<vi>
#define vin(a,n) vi a(n); rep(k_,0,n) {cin>>a[k_];}
#define pb push_back
#define mod 1000000007
#define mod2 998244353
#define inf 1e18
#define pi 3.1415926535897932384626
#define tr(container, it) \
for(auto it = container.begin(); it != container.end(); it++)

// DEBUG FUNCTIONS BEGIN
#ifdef LOCAL
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

template <class T> void _print(T t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p)
{cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
template <class T> void _print(vector <T> v)
{cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v)
{cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v)
{cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v)
{cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(vector < vector<T> > v)
{cerr << "[ " << endl; for (vector<T> i : v) {_print(i); cerr << endl;} cerr<< "]";}
void _print(vector <string> v)
{cerr << "[ " << endl; for (string i : v) {_print(i); cerr << endl;} cerr<< "]";}
// DEBUG FUNCTIONS END

void vout(vector<int> a)
{
    for(int x : a) 
        cout << x << " ";
    cout << nl;
}

int ceill(int a, int b)
{
    return (a+b-1)/b;
}

int32_t main()
{
    #ifdef LOCAL
        freopen("error.txt", "w", stderr);
    #endif
    IOS
    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++)
    {
        int n,k; cin>>n>>k;
        vi a(n+1); rep(i,1,n+1) cin>>a[i];

        vi pref(n+1); rep(i,1,n+1) pref[i] = pref[i-1] + a[i];

        vi dp(n+1); vi dpsum(n+1); dp[0] = 1; dpsum[0] = 1;
        map<int,int> prefdp; prefdp[0] = 1;
        rep(i,1,n+1)
        {
            dp[i] = dpsum[i-1];
            if(prefdp.count(pref[i] - k))
                dp[i] = (dp[i] - prefdp[pref[i] - k] + mod2) % mod2;
            dpsum[i] =( dp[i] + dpsum[i-1]) % mod2;
            (prefdp[pref[i]] += dp[i]) %= mod2;
        }
        debug(dp); debug(prefdp);
        cout<<dp[n]<<nl;
    }
    return 0;
}

提出情報

ジャッジ結果