Ankit_132

E

Jan 3rd, 2024 (edited)
1,086
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define MOD 1000000007
  6.  
  7. const int N = 1000005;
  8. ll int k[N], q[N];
  9.  
  10. ll int c(ll int a, ll int b, ll int m)
  11. {
  12.     ll int ans=1;while(b)
  13.     {if(b&1)ans=(ans*a)%m;b/=2;a=(a*a)%m;}
  14.     return ans;
  15. }
  16.  
  17. ll int l(ll int k)
  18. {return c(k, MOD-2, MOD);}
  19.  
  20. void g()
  21. {
  22.     k[0]=k[1]=1;
  23.     for(int i=2;i<N;i++){k[i]=k[i-1]*i;k[i]%=MOD; }
  24.     q[N-1]=l(k[N-1]);
  25.     for(int i=N-2;i>=0;i--){q[i]=q[i+1]*(i+1);q[i]%=MOD;}
  26. }
  27.  
  28. ll int nCr(ll int x, ll int y)
  29. {
  30.     if(y>x)return 0ll;ll int v=k[x];v*=q[y];
  31.     v%=MOD;v*=q[x-y];v%=MOD;return v;
  32. }
  33.  
  34. int main()
  35. {
  36.     int t;
  37.     cin>>t;
  38.    
  39.     g();
  40.    
  41.     while(t--)
  42.     {
  43.         int n, m;
  44.         cin>>n>>m;
  45.  
  46.         vector<string> s(n);
  47.         for (auto &x : s)   cin>>x;
  48.  
  49.         if(n == 1)
  50.         {
  51.             cout<<1<<"\n";
  52.             continue;
  53.         }
  54.  
  55.         vector<int> a(m), b(m);
  56.  
  57.         for(int i=0; i<m; i++)
  58.             a[i] = (s[n-1][i] == '1');
  59.  
  60.         if(accumulate(a.begin(), a.end(), 0) == 1)
  61.             fill(a.begin(), a.end(), 0);
  62.  
  63.         for(int i=n-2; i>0; i--)
  64.         {
  65.             b = a;
  66.             fill(a.begin(), a.end(), 0);
  67.  
  68.             for(int j=0; j<m; j++)
  69.                 a[j] = (s[i][j] == '1');
  70.  
  71.             int f = 0;
  72.             for(int j=0; j<m; j++)
  73.                 f += (a[j] && b[j]);
  74.  
  75.             if(f)
  76.             {
  77.                 for(int j=0; j<m; j++)
  78.                     a[j] |= b[j];
  79.             }
  80.  
  81.             if(accumulate(a.begin(), a.end(), 0)==1 ||
  82.                count(s[i].begin(), s[i].end(), '1')==1)
  83.                 fill(a.begin(), a.end(), 0);
  84.         }
  85.  
  86.         int cnt1=0, cnt0=0;
  87.  
  88.         for(int i=0; i<m; i++)
  89.         {
  90.             cnt0 += (s[0][i]=='0' && a[i]);
  91.             cnt1 += (s[0][i]=='1' && a[i]);
  92.         }
  93.  
  94.         cout<<nCr(cnt0+cnt1, cnt1)<<"\n";
  95.     }
  96. }
  97.  
Advertisement
Add Comment
Please, Sign In to add comment