WHY TLE in atcoder problem helppp

Правка en1, от mainnahihoo, 2025-07-20 00:19:22

problem atcoder problem int dp[(1<<20)]; // int cnt=0; int rec(int mask,string &s,int n){ // cout<<"call for "<<mask<<endl; if(mask==(1<<n)-1)return 1; if(dp[mask]!=-1)return dp[mask]; int x=0; for(int i=0;i<n;i++){ if(!(mask&(1<<i)) && s[mask|(1<<i)]=='0'){ x|=rec(mask|(1<<i),s,n); } } // cnt++; return dp[mask]=x; }

void solve() { // executing code from here int t; cin >> t; while (t--) { int n;cin >> n;string s;cin>>s; memset(dp,-1,sizeof(dp)); s='0'+s; if(rec(0,s,n))cy; else cn; } }

I am getting TLE why after dp time complexity should be 2^n*n not n!*n

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский mainnahihoo 2025-07-20 00:33:46 22
en1 Английский mainnahihoo 2025-07-20 00:19:22 720 Initial revision (published)