My solution is https://atcoder.jp/contests/dp/submissions/14182185

passed 16/28.

Can someone help??

You were missing one condition

```
vector <bool> dp(k+1);
for(int i=0;i<=k;i++)
{
for(int j=0;j<n;j++)
if(i>=arr[j] && !dp[i-arr[j]])
dp[i]=1;
}
if(dp[k])
cout<<"First\n";
else
cout<<"Second\n";
```

Sorry but I couldn’t find any extra condition in your code. Could you please mention?

Try

1 100000

1

What if your inner loop never stops

Thanks a lot!!

Your example did the job.

I initially thought , a[j]<=i would work and skipped that condition.

Can you help me in this?

Your size of dp[][] is less than the available constraints. Make it dp[3001][3001]

what’s wrong with me? I think I’m going crazy.

Sorry for disturbing for such a silly error.

And Thanks a lot!!

Chill bro, it happens sometime.

try the above mentioned input

I did and the problem has been solved.

Thanks!!

welc

Hey, Can you help me in this?

Not able to move even a single step forward.

Can u give me some hints , how to approach the problem?

No of subseq with gcd=1 is ans

Actually, I had already figured it out. but how to proceed further?

See for each value, it has two options (taken or not). Now for each arr[i] take two cases and when you have reached last count , see if gcd is 1 then return 1. I mean in case of recursion just pass pos and current gcd as its argument

Won’t this give TLE?

Edit: I did and got TLE.

(Might be a possibility that I didn’t get what you suggested. So here is my solution: https://www.codechef.com/viewsolution/34551576)

Man with memoization

## Code

```
#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
#define lld long long int
#define pb push_back
#define fo(i,a,b) for(int i=a;i<b;i++)
#define foe(i,a,b) for (int i=a;i<=b;i++)
lld n,dp[70][100000],arr[61];
lld gcd(lld a, lld b){
if (b==0) return a;
else
return gcd(b,a%b);
}
// x is defined to initiate curgcd
lld fun(lld ind,lld curgcd)
{
if (ind==n+1 && curgcd==1)
return 1;
if(ind==n+1&&curgcd!=1)
return 0;
if(dp[ind][curgcd]!=-1)
return dp[ind][curgcd];
return dp[ind][curgcd]=fun(ind+1,gcd(curgcd,arr[ind]))+fun(ind+1,curgcd);
}
void solve()
{
cin>>n;
foe(i,1,n)
cin>>arr[i];
memset(dp,-1,sizeof(dp));
lld ans = fun(1,arr[0]);
if(n==1&&arr[0]==1)
cout<<"1\n";
else
cout<<ans<<"\n";
}
signed main()
{
faster;
int t;cin>>t;
while(t--)
solve();
}
```

Ohh Sorry. I thought that It will calculate every state once even without memoization.

Got Ac after using memoization.

Thanks Btw