fork download
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  4. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  5. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  6. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  7.  
  8. #define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; }
  9. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  10. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  11.  
  12. #define sqr(x) ((x) * (x))
  13. #define ll long long
  14. #define SZ(X) ((int) ((X).size()))
  15. using namespace std;
  16.  
  17. const ll MOD = 1e9 + 7;
  18.  
  19. int sz;
  20. struct Matrix {
  21. ll x[22][22];
  22.  
  23. void print() {
  24. REP(i,sz) {
  25. REP(j,sz) cout << x[i][j] << ' '; cout << endl;
  26. }
  27. cout << endl;
  28. }
  29. } A, I;
  30.  
  31. struct Vector {
  32. ll x[22];
  33.  
  34. void print() {
  35. PR0(x, sz);
  36. }
  37. } f;
  38.  
  39. Vector update(const Vector& f, const Matrix& A) {
  40. Vector res;
  41. REP(i,sz) {
  42. res.x[i] = 0;
  43. REP(j,sz)
  44. res.x[i] = (res.x[i] + A.x[i][j] * f.x[j]) % MOD;
  45. }
  46. return res;
  47. }
  48.  
  49. Matrix operator * (const Matrix& a, const Matrix& b) {
  50. Matrix res;
  51. REP(i,sz) REP(j,sz) {
  52. res.x[i][j] = 0;
  53. REP(k,sz)
  54. res.x[i][j] = (res.x[i][j] + a.x[i][k] * b.x[k][j]) % MOD;
  55. }
  56. return res;
  57. }
  58.  
  59. Matrix power(const Matrix& a, int k) {
  60. if (k == 0) return I;
  61. if (k == 1) return a;
  62.  
  63. Matrix mid = power(a, k >> 1);
  64. mid = mid * mid;
  65.  
  66. if (k & 1) return mid * a;
  67. return mid;
  68. }
  69.  
  70. const int MN = 22;
  71. int m, n, q, id[MN][MN];
  72.  
  73. const int di[5] = {-1,1,0,0,0};
  74. const int dj[5] = {0,0,-1,1,0};
  75.  
  76. bool outside(int u, int v) {
  77. return u < 1 || v < 1 || u > m || v > n;
  78. }
  79.  
  80. void init() {
  81. int cur = 0;
  82. FOR(i,1,m) FOR(j,1,n) id[i][j] = cur++;
  83.  
  84. memset(I.x, 0, sizeof I.x);
  85. memset(A.x, 0, sizeof A.x);
  86.  
  87. sz = m * n;
  88. REP(i,sz) I.x[i][i] = 1;
  89.  
  90. FOR(i,1,m) FOR(j,1,n) {
  91. REP(dir,5) {
  92. int ii = i + di[dir], jj = j + dj[dir];
  93. if (outside(ii, jj)) continue;
  94.  
  95. A.x[ id[i][j] ][ id[ii][jj] ] = 1;
  96. }
  97. }
  98. }
  99.  
  100. int main() {
  101. ios :: sync_with_stdio(false);
  102. {
  103. n = 5; m = 4; q = 10000;
  104. init();
  105.  
  106. memset(f.x, 0, sizeof f.x);
  107. f.x[0] = 1;
  108.  
  109. int cur_time = 1;
  110.  
  111. for(int i = 0; i < q; i++) {
  112. int typ = 1;
  113. int x = 1, y = 1, t = i * 1000 + 10;
  114.  
  115. // update until time moment t-1
  116. Matrix up = power(A, t - 1 - cur_time);
  117. f = update(f, up);
  118.  
  119. if (typ == 2) {
  120. // cannot go to cell (x, y)
  121. REP(dir,5) {
  122. int xx = x + di[dir], yy = y + dj[dir];
  123. if (outside(xx, yy)) continue;
  124.  
  125. A.x[ id[x][y] ][ id[xx][yy] ] = 0;
  126. }
  127. }
  128. f = update(f, A);
  129.  
  130. if (typ == 1) {
  131. cout << (int) f.x[id[x][y]] << '\n';
  132. }
  133. cur_time = t;
  134.  
  135. if (typ == 3) {
  136. // can now go to cell (x, y)
  137. REP(dir,5) {
  138. int xx = x + di[dir], yy = y + dj[dir];
  139. if (outside(xx, yy)) continue;
  140.  
  141. A.x[ id[x][y] ][ id[xx][yy] ] = 1;
  142. }
  143. }
  144. }
  145. }
  146. }
Time limit exceeded #stdin #stdout 5s 3464KB
stdin
Standard input is empty
stdout
12496
8976859
386306705
135862693
44251892
484455151
175732192
149220801
258955624
229635584
932491424
308054889
533010059
794663131
907863699
580182779
406199933
462528118
693841504
453262859
277245530
181616718
434293124
13593556
415128132
845209516
717852388
522644618
742161699
780290437
210689637
904593049
666674843
434948309
933386625
384924274
565041778
394743553
507403898
750449241
539119808
519928982
406034819
535509306
321348549
381054576
822918998
966074740
414708648
952126713
978401132
84323350
661704214
616163973
815514258
596549569
521900658
732635004
530794801
780518978
199913807
285938145
281351779
992277591
994358675
457484994
152196116
668154083
445294882
273545946
613918235
609702582
383963911
46523970
520796576
399673631
155710650
756538367
457464554
339421665
128879840
325480743
735879134
986210338
462604079
101848822
418052852
500367835
776938590
617445186
324289012
619766802
657099911
337365983
145657627
301965328
653086566
89995153
985974438
457739363
333188189
612880082
82785972
90695636
229412605
548128234
374898678
502021441
737921939
981613623
818340077
786899786
612859603
361431624
936989128
756133045
890278674
566938798
477314437
163401190
472946228
793824680
247642642
646085193
696239457
954517267
274785610
285237369
923667502
728150703
438655127
41373936
184403626
151008819
919268058
469447837
186103399
426040432
788983409
891235889
714207268
549608152
565216950
617658012
884549678
61234514
451027210
616889141
677303372
119799083
656487417
107532610
118523857
472494707
252597135
549312853
597022906
336545388
643496483
491305868
339394071
879153813
330033042
506279404
651930371
524411878
828966034
428977922
590871657
328729672
158052421
714994762
152295201
22542171
708765915
363935224
734673049
870419900
204186521
262145315
852224573
237843569
551332234
168578886
696479812
11236875
629597979
969215534
619098033
61193775
965947933
568559951
336086343
178618785
415721745
961725512
213380557
896839121
335345762
238004585
349097054
495675135
809467277
685465162
747751560
49191726
117257037
4297749
789529852
198889930
298548872
365366190
244294042
11386292
246666960
387301952
868772072
758216712
194419652
289721079
278763207
970779897
548417374
832766007
379832172
143836939
189997735
425036200
801825160
173671374
771915817
108369824
40977246
301282614
958583721
551828234
626796632
756657628
32638062
911557664
160169490
660930997
703173377
76342866
65368295
389567468
288685531
548366719
672845489
805165367
864488806
13469207
959096826
871461861
269782333
136013919
877515306
23922171
950106465
819537717
351179060
810405823
66622163
378001079
598803399
123066382
155288756
78427945
470713932
438808647
884116941
281956532
104846077
390179546
268467109
414212273
451885441
348481908
707124893
81280234
259620865
128714016
514723081
671140548
151676720
93858210
644775211
780718763
671248557
676080831
458962056
722638363
276552835
824669928
254087580
705194261
64268288
720349594
466418404
88534543
67254193
948606371
917780451
39811747
663881029
895320305
896972170
81047138
536786065
334475324
228557738
375692122
908389030
733794083
788269059
822224867
683501514
630247856
110771518
158590650
198068137
882030703
418728297
422949076
962975839
568875620
13309442
549543232
313758926
297178490
56554826
124691387
10915000
240089730
687784614
399399814
728358545
706579780
859364728
411843085
877267378
805723207
572545875
392281298
602147338
990956837
875538254
412053470
333253363
893457523
611933238
536396694
970885884
919200847
522022302
710918049
361969448
402703058
307309657
686761524
129141013
144715275
528005061
220037462
8365207
217346819
576429725
524619656
255673341
206656957
452880652
504111029
599445864
408915775
867498961
70326217
210593594
863010362
365142974
152141377
710108865
853158747
734012630
373193520
653146135
774980219
735864662
642032904
502225002
19826124
791727736
237625175
129806154
366549479
27688021
656808519
398510737
687596705
44098062
952669672
258950967
410986366
365552028
608237703
973410222
336664200
907924910
871319186
106751654
213314150
368577101
517015507
25002136
468432801
959237388
720254035
689672329
921846034
7066995
285995176
573035584
154540846
703799667
739840627
589726260
284391902
498650034
842472454
651734494
317098154
560984439
599024910
606436235
240775368
602031193
609655689
248833870
298995450
240924339
142529021
835953278
199882980
844653521
90388866
490118825
275233829
332371102
358320738
476430650
945953892
444666
122796719
61140130
654499644
669078466
584304137
14123959
185562911
413237936
539296285
514381748
856484392
57131351
980674861
951089546
709224900
659253736
415746420
610132922
884927920
639077680
870767017
843046856
990198433
504557324
596288478
65342934
337339483
69699169
461586224
603873581
675953749
475407078
880035867
117704273
230957150
625521550
643921398
208196034
226393526
124176762
470824798
507281357
111112053
632562749
817889254
611945886
567454023
551418563
676780610
524710713
614900963
825504511
726376457
739753697
511201926
771548833
122295115
375227511
35897436
77201252
479559825
752772864
713614466
979369062
289589841
864118664
411988251
806310170
467620252
375121932
51334103
511767482
291264621
764904804
400417912
656505814
391021307
936389555
633445185
993950553
379529072
232495320
628150950
781752145
257146318
400218750
594958633
991914212
642751343
117475817
499828523
562692645
99517856
400969050
538378780
853982582
408804853
906124654
676172416
663305934
870840092
609275505
423692319
911497468
81475615
871293373
552222151
210253135
487977011
531061353
961670420
460877396
252455499
517374670
124705650
768357171
796628014
336004494
736588912
508122610
930449371
935272732
224547735
965210662
922219018
967420179
894088392
103542381
853294943
145121823
306289770
985340616
727948488
638051770
780091962
976454605
92410689
703774699
815089271
70484158
383296823
88182423
598438880
714460649
91424491
427080677
376024806
709308522
250243346
91017295
577160035
681965359
820452871
737639619
555861564
258545865
890115639
208331285
391360727
932822952
720489702
541605261
237205086
65418911
633306820
526153452
416743675
438290008
200894550
299357764
157832928
267540440
856008475
548208048
874657634
965300656
823118123
487780708
674929557
152864221
439784510
893988598
520841299
370677002
816742481
483063480
952647785
183630631
427558818
154891949
167055667
318304812
106034624
295354457
572020614
386343690
309433490
529324279
774751079
626496665
540811211
127211979
136969747
398479091
111196792
968139622
470411489
289007853
477391860
751547243
144376233
536363914
963076550
88755416
737795127
158529110
79375109
978068877
127203861
829892652
689710425
718873920
634525930
433040836
646067590
79672844
274451496
958654875
501283448
749401146
875387
610475017
47133634
742363252
250445943
846099523
952352662
913777935
461515614
620483106
72483667
749465529
257969300
880735698
24650088
719549488
747963653
756325547
411060265
720187727
812649166
299483683
590996189
251144039
19805006
168827810
160654256
448085940
873841143
368858690
515195618
985348685
991162754
91595486
344588898
736562603
103388197
578285630
297642911
424820295
700159938
2625108
874591582
689761868
745913146
416972322
671137629
811158386
930344216
600785930
773853791
463958489
115081921
225006792
24034579
788399133
707932560
634014728
421873221
432247894
913796555
200319993
825646305
87610401
601611638
130111923
722576804
600602997
642282112
738704995
582486483
308740297
450224012
979048944
302415990
341817787
750882464
977624874
624436688
502697125
843078498
23754965
46153300
342885702
354635085
702941447
208955958
541342890
581990501
532581247
959288860
505161010
352145389
621574303
607922730
802986562
795838560
25893828
738597767
818920519
935840959
199655344
991068138
618291380
791734597
897878395
294547220
123056545
32739302
160911020
135444995
957004231
688704898
258493972
543365954
745742207
882102357
761125241
393141330
868085372
653617378
18833572
33926069
818637837
574125565
701556379
475024572
803441754
124283994
154455750
123419209
962924314
244949806
858266472
81278896
973891250
987344949
762330953
48342891
931541655
366962697
498973077
466085236
377638802
720297403
445821842
605732244
732317490