fork download
copy 
  1.  
  2.  
  3.     #include<bits/stdc++.h>
  4.     using namespace std;
  5.     #define ll long long int
  6.     #define pi pair<ll,ll>
  7.     #define pii pair<pi,ll>
  8.     #define f first
  9.     #define s second
  10.     #define rep(i,n) for(int i=0;i<n;i++)
  11.     #define pb push_back
  12.     const int mod = 1e9+7;
  13.     int N,M;
  14.     void recH(int R,int C,int logM,vector<vector<int > >&H,vector<int >&dp) {
  15.            int cur = R*(M+1)+C;
  16.         for(int j=0;j<=logM;j++) {
  17.             if(j==0) {
  18.                 if(C&(1<<j)) H[cur][j] = dp[cur]+dp[R*(M+1)+(C^(1<<j))];
  19.                 else H[cur][j] = dp[cur];
  20.                 if(H[cur][j]>=mod) H[cur][j]-=mod;
  21.                 continue;
  22.             }
  23.             if(C&(1<<j)) {
  24.                 H[cur][j] = H[R*(M+1)+(C^(1<<j))][j-1] + H[cur][j-1];
  25.                 if(H[cur][j]>=mod) H[cur][j]-=mod;
  26.             }
  27.             else{
  28.                 H[cur][j] = H[cur][j-1];
  29.             }
  30.         }
  31.     }
  32.     void recV(int R,int C,int logN,vector<vector<int > >&V,vector<int >&dp) {
  33.         int cur = R*(M+1)+C;
  34.         for(int j=0;j<=logN;j++) {
  35.             if(j==0) {
  36.                 if(R&(1<<j)) V[cur][j] = dp[cur]+dp[(R^(1<<j))*(M+1)+  C];
  37.                 else V[cur][j] = dp[cur];
  38.                 if(V[cur][j]>=mod) V[cur][j]-=mod;
  39.                 continue;
  40.             }
  41.             if(R&(1<<j)) {
  42.                 V[cur][j] = V[(R^(1<<j))*(M+1)+C][j-1] + V[cur][j-1];
  43.                 if(V[cur][j]>=mod) V[cur][j]-=mod;
  44.             }
  45.             else{
  46.                 V[cur][j] = V[cur][j-1];
  47.             }
  48.         }
  49.     }
  50.     int main() {
  51.         cin >> N >> M;
  52.         bool flag = 0;
  53.         if(N>M) {
  54.         	swap(N,M);
  55.         	flag = 1;
  56.         }
  57.         int logN = log2(N);
  58.         int logM = log2(M);
  59.         int Q;
  60.         cin >> Q;
  61.         int x,y;
  62.         vector<vector<int> >V((N+1)*(M+1),vector<int>(logN+1,-1));
  63.         vector<vector<int> >H((N+1)*(M+1),vector<int>(logM+1,-1));
  64.         vector<int>dp((N+1)*(M+1),0);
  65.         while(Q--) {
  66.             cin >> x >> y;
  67.             if(flag) {
  68.             	swap(x,y);
  69.             }
  70.             dp[x*(M+1)+y] = -1;
  71.         }
  72.         dp[0] = 1;
  73.         recH(0,0,logM,H,dp);
  74.         recV(0,0,logN,V,dp);
  75.         rep(i,N+1) {
  76.             rep(j,M+1) {
  77.                 if(i==0 and j==0) continue;
  78.                 if(dp[i*(M+1)+j]==-1) {
  79.                     dp[i*(M+1)+j] = 0;
  80.                     recH(i,j,logM,H,dp);
  81.                     recV(i,j,logN,V,dp);
  82.                     continue;
  83.                 }
  84.                 int cur = i*(M+1)+j;
  85.                 recH(i,j,logM,H,dp);
  86.                 recV(i,j,logN,V,dp);
  87.                 dp[cur] = H[cur][logM]+V[cur][logN];
  88.                 if(dp[cur]>=mod) dp[cur]-=mod;
  89.                 recH(i,j,logM,H,dp);
  90.                 recV(i,j,logN,V,dp);
  91.             }
  92.         }
  93.         cout << dp[N*(M+1)+M]%mod;
  94.     }
  95.  
  96.  
Success #stdin #stdout 1.56s 539648KB
comments (?)
stdin
copy 
2047 2047 0
stdout
copy 
302499034
https://ideone.com/1NrXbK
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!