Submission #1319801

---

Source Code Expand

#include <stdio.h>
#include <string.h>

const int mod = 1000000007;

int dp[100];

int N[] = {3, 7, 15, 34};

const int A2[3] = {
3, mod-1, mod-1
};

const int S2[3] = {
1, 3, 8
};

const int A3[7] ={
9, mod-21, 3, 24, mod-8, mod-4, 4
};

const int S3[7] = {
1, 8, 51, 295, 1632, 8830, 47239
};


const int A4[15] = {
25, mod-210, 634, 156, mod-3876, 3742, 6154, mod-10159, 559, 9408, mod-4416, mod-960, 1600, 256, 256
};

const int S4[15] = {
1, 20, 295, 3828, 46557, 546286, 6279393, 71316632, 804230945, 31118873, 161197188, 456023339, 706488180, 772962252, 858943632
};

const int S5[99] = {
49,
1632,
46557,
1225194,
30754544,
749866185,
950397139,
660440007,
967524660,
645623327,
574347952,
327244790,
490308283,
710557607,
793104791,
251294010,
59342205,
58790320,
701336566,
31927225,
428079243,
46952899,
435403329,
893753875,
735531513,
912155055,
471483506,
8742205,
204686212,
107097468,
250840307,
355165092,
463334269,
708615048,
245627810,
103335651,
352231049,
489497854,
55861909,
759443114,
984095935,
606967958,
724993500,
496714555,
469409654,
687091711,
868326516,
644323133,
267475600,
510554881,
792743174,
801945119,
709807743,
654533379,
763766040,
760715418,
848385716,
146602642,
991802590,
864715081,
752285769,
631168303,
353778540,
633905010,
489347065,
201493629,
270038302,
513878188,
671853990,
543674198,
60054086,
474013999,
41466523,
651368556,
867723928,
636757293,
368352185,
286088069,
25920214,
47593986,
182468417,
958598130,
194493202,
610329207,
446596397,
525800384,
15779910,
270997567,
658749287,
163270230,
237204239,
27544742,
174877297,
136710917,
371042336,
303074303,
583558349,
576347184,
413668984,
};

const int S6[99] = {
119,
8830,
546286,
30754544,
636193221,
949041348,
804877445,
255893772,
10692182,
945472729,
833656513,
595656003,
555680409,
660201663,
873188040,
238814631,
361665626,
606167869,
909671832,
749280461,
711696639,
137205986,
124406784,
672935428,
999486731,
100034010,
562659255,
565317077,
205694018,
841176241,
944902847,
382051192,
725376114,
617071382,
858415617,
436015376,
203513902,
635073515,
418156904,
244373091,
592599111,
641076879,
156003629,
602881654,
966977236,
959155778,
417218270,
269917785,
51679714,
923825412,
697787383,
304012548,
239994740,
133315429,
67287857,
120565787,
225800159,
101353808,
393967856,
263504064,
802522012,
1932729,
388242300,
558934643,
429474400,
446379853,
838002526,
533994805,
169776308,
689946166,
46087050,
121339248,
417660037,
456879893,
739400853,
223622872,
379493529,
174048592,
612071928,
86811675,
695559569,
488521735,
892014580,
237585247,
614437896,
694975504,
754291373,
692845512,
748829491,
167841529,
355597716,
421347204,
266606025,
99168078,
328665317,
571419414,
988580581,
359509521,
184466177,
};

int main(){
  int h, w, i, j;

  scanf("%d%d", &h, &w);

  if(h == 6){
    printf("%d\n", S6[w-2]);
    return 0;
  }
  else if(h ==5) {
    printf("%d\n", S5[w-2]);
    return 0;
  }
  else if(h ==2) {
    if(w <= N[0]){
      printf("%d\n", S2[w-1]);
      return 0;
    }
    else {
      memcpy(dp, S2, sizeof(S2));
      for(i=N[0];i<=w-1;i++){
        for(j=0;j<N[0];j++){
          dp[i] = (dp[i] + (long long) A2[j] * dp[i-1-j]) % mod;
        }
      }
    }
  }
  else if(h ==3) {
    if(w <= N[1]){
      printf("%d\n", S3[w-1]);
      return 0;
    }
    else {
      memcpy(dp, S3, sizeof(S3));
      for(i=N[1];i<=w-1;i++){
        for(j=0;j<N[1];j++){
          dp[i] = (dp[i] + (long long) A3[j] * dp[i-1-j]) % mod;
        }
      }
    }
  }
  else if(h ==4) {
    if(w <= N[2]){
      printf("%d\n", S4[w-1]);
      return 0;
    }
    else {
      memcpy(dp, S4, sizeof(S4));
      for(i=N[2];i<=w-1;i++){
        for(j=0;j<N[2];j++){
          dp[i] = (dp[i] + (long long) A4[j] * dp[i-1-j]) % mod;
        }
      }
    }
  }


  printf("%d\n", dp[w-1]);
  return 0;
}

Submission Info

Judge Result