### Normal_People's blog

By Normal_People, history, 3 weeks ago,

I solved this problem(with right logic)but i do not know how this implementation is working. I am trying to make a prefix sum in dp array but when you print it there is no prefix array in it.(IG it's because of mod function, but i do not know it's inner working).

#include <bits/stdc++.h>
using namespace std;
#define fr(i, n) for (int64_t i = 0; i < n; i++)
#define frn(i, a, n) for (int64_t i = a; i < n; i++)
#define testoutput FILE *file = fopen("test.out", "r"); if (file){fclose(file);freopen("test.out", "w", stdout); }
#define vet vector<int64_t>
#define vett vector<vector<int64_t> >
#define vst vector<string>
#define en cout << "\n";
#define all(v) v.begin(), v.end()
#define int int64_t
#define mp make_pair
#define F first
#define S second
const int mx = INT64_MAX;

// clang++ -std=c++20 check.cpp -o a
// clang++ -std=c++20 random.cpp -o r

const int MOD = (1e9 + 7);
inline int posmod(int k)
{
return ((k % MOD) + MOD) % MOD;
}

void solve()
{
int n,k;cin >> n >> k;
vet a(n+1);frn(i,1,n+1)cin >> a[i];
vett dp(n+1,vet(k+1,0));dp[0][0]=1;
frn(i,1,n+1){
fr(j,k+1){
int start = j-a[i];
if(start<=0)start=0;
else start = dp[i-1][start-1];
dp[i][j]=posmod(dp[i][j]+dp[i-1][j]-start);
if(j>0)dp[i][j] = posmod(dp[i][j]+dp[i][j-1]);
}
}
cout << dp[n][k];
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
testoutput
int64_t t = 1,caseno = 1;
// cin >> t;
while (t--)
{
// cout << "Case # " << caseno << ": "<<endl;
solve();
// cout << "\n";
// caseno++;
}
// cerr << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}

• +2

 » 3 weeks ago, # |   0 Auto comment: topic has been updated by Normal_People (previous revision, new revision, compare).
 » 3 weeks ago, # | ← Rev. 2 →   0 I submit your code without posmod and just write % MOD, then it's get WA
 » 3 weeks ago, # | ← Rev. 3 →   0 You need to mod after every operation in these type of questions. Not like you did. Are you for real can define int_64 as int? There would be no bug?
•  » » 3 weeks ago, # ^ |   0 I have never seen a bug with int_64 defined as int