QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233241 | #7659. Highway Combinatorics | ValenciaTravis# | AC ✓ | 436ms | 73748kb | C++20 | 2.2kb | 2023-10-31 15:32:20 | 2023-10-31 15:32:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define ll long long
#define int long long
const ll mod = 1e9 + 7;
int n;
ll f[105];
vector<char> s;
vector<int> v, from;
unordered_map<int, int> mp;
ll qpow(ll a, ll b){
ll ret = 1;
while(b){
if(b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
void init(){
queue<pair<int, int>> q;
q.push({1, 0});
int cnt = 1;
mp[1] = 1;
v.push_back(1); from.push_back(0);
while(!q.empty() && cnt < 1e6){
auto [x, t] = q.front();
q.pop();
for(int i=2;i<100-t;i++){
int x1 = ((ll)x * f[i]) % mod;
int t1 = (t+i+1);
if(mp[x1]) continue;
mp[x1] = ++cnt;
v.push_back(x1), from.push_back(i);
if(t1 != 100) q.push({x1, t1});
}
}
// printf("cnt = %d\n", cnt);
}
void print(int x){
// printf("x = %d\n", x);
int tmp = x;
ll check = 1;
while(tmp != 1){
if(s.size()) s.push_back('#');
int id = mp[tmp] - 1;
for(int i=1;i<=from[id];i++) s.push_back('.');
check = check * f[from[id]] % mod;
tmp = (ll) tmp * qpow(f[from[id]], mod-2) % mod;
}
tmp = n * qpow(x, mod-2) % mod;
while(tmp != 1){
if(s.size()) s.push_back('#');
int id = mp[tmp] - 1;
// printf("tmp = %d, id = %d, from = %d\n", tmp, id, from[id]);
for(int i=1;i<=from[id];i++) s.push_back('.');
check = check * f[from[id]] % mod;
tmp = (ll) tmp * qpow(f[from[id]], mod-2) % mod;
}
// if(check != n) assert(0);
// if(s.size() > 200) assert(0);
for(auto c : s) putchar(c); putchar('\n');
for(auto c : s) putchar(c); putchar('\n');
}
signed main(){
f[0] = f[1] = 1;
for(int i=2;i<=100;i++) f[i] = (f[i-1] + f[i-2]) % mod;//, printf("%lld\n", f[i]);
cin>>n;
if(n == 0){
puts("##.\n.##");
return 0;
}else if(n == 1){
puts(".\n.");
return 0;
}
init();
for(auto x : v){
int tmp = (ll)n * qpow(x, mod-2) % mod;
int &X = mp[tmp];
if(X) return print(x), 0;
}
assert(0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 337ms
memory: 72896kb
input:
10
output:
....#.. ....#..
result:
ok res = 10
Test #2:
score: 0
Accepted
time: 326ms
memory: 73160kb
input:
27
output:
...#...#... ...#...#...
result:
ok res = 27
Test #3:
score: 0
Accepted
time: 393ms
memory: 73068kb
input:
1000000006
output:
.....................................#.................................#...............................#..............................#.........................#...#..#.. .....................................#.................................#...............................#............................
result:
ok res = 1000000006
Test #4:
score: 0
Accepted
time: 378ms
memory: 72820kb
input:
1000000000
output:
.....................................#.................................#..#...............................#..............................#.........................#.......#.. .....................................#.................................#..#...............................#.....................
result:
ok res = 1000000000
Test #5:
score: 0
Accepted
time: 0ms
memory: 3376kb
input:
0
output:
##. .##
result:
ok res = 0
Test #6:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
1
output:
. .
result:
ok res = 1
Test #7:
score: 0
Accepted
time: 369ms
memory: 73372kb
input:
7
output:
...............................................................#..............................#......................#...............#.......#.......#.. ...............................................................#..............................#......................#...............#.......#........
result:
ok res = 7
Test #8:
score: 0
Accepted
time: 367ms
memory: 72824kb
input:
144000001
output:
.................................................................#.........#...#........................#.......................#...................#.................#....#.. .................................................................#.........#...#........................#.......................
result:
ok res = 144000001
Test #9:
score: 0
Accepted
time: 361ms
memory: 73020kb
input:
46750697
output:
................................................................#..................................#................................................#......................#.................#.....#... ................................................................#..................................#...
result:
ok res = 46750697
Test #10:
score: 0
Accepted
time: 381ms
memory: 73076kb
input:
12345678
output:
..........................................#.................................#...........#.......................#......................#..............#..............#............. ..........................................#.................................#...........#.......................#..........
result:
ok res = 12345678
Test #11:
score: 0
Accepted
time: 393ms
memory: 72940kb
input:
102334155
output:
....................................... .......................................
result:
ok res = 102334155
Test #12:
score: 0
Accepted
time: 336ms
memory: 73500kb
input:
165580141
output:
........................................ ........................................
result:
ok res = 165580141
Test #13:
score: 0
Accepted
time: 363ms
memory: 73500kb
input:
8390086
output:
....................................................................... .......................................................................
result:
ok res = 8390086
Test #14:
score: 0
Accepted
time: 362ms
memory: 72848kb
input:
210345902
output:
......................................................................................... .........................................................................................
result:
ok res = 210345902
Test #15:
score: 0
Accepted
time: 340ms
memory: 72988kb
input:
755204270
output:
.......................................................................................... ..........................................................................................
result:
ok res = 755204270
Test #16:
score: 0
Accepted
time: 361ms
memory: 72820kb
input:
349361645
output:
.....................................................................#...#...............................#.....................#...................#..................#...#.. .....................................................................#...#...............................#.......................
result:
ok res = 349361645
Test #17:
score: 0
Accepted
time: 338ms
memory: 72952kb
input:
529309711
output:
.......................................................#....................#..#.............................#..........................#..............#..............#......#.. .......................................................#....................#..#.............................#................
result:
ok res = 529309711
Test #18:
score: 0
Accepted
time: 339ms
memory: 72984kb
input:
878671356
output:
........................................#.................................#..#..............................................#..............#...........#..........#...#.. ........................................#.................................#..#..............................................#........
result:
ok res = 878671356
Test #19:
score: 0
Accepted
time: 366ms
memory: 72820kb
input:
141851555
output:
...................................................................................................#................................................................................................... ...................................................................................................#...
result:
ok res = 141851555
Test #20:
score: 0
Accepted
time: 362ms
memory: 73416kb
input:
245606600
output:
..........................................................#.................................#.....................#.....................#...................#..................#....#.. ..........................................................#.................................#.....................#....
result:
ok res = 245606600
Test #21:
score: 0
Accepted
time: 316ms
memory: 72892kb
input:
387458156
output:
................................................#................................#..................................................#................#................#............ ................................................#................................#.........................................
result:
ok res = 387458156
Test #22:
score: 0
Accepted
time: 332ms
memory: 73304kb
input:
447800885
output:
....................................................#..........................#................................#............................#..............#...........#....#.. ....................................................#..........................#................................#.............
result:
ok res = 447800885
Test #23:
score: 0
Accepted
time: 312ms
memory: 72908kb
input:
981661739
output:
..........................................#...#................................................#......#......#.....#..... ..........................................#...#................................................#......#......#.....#.....
result:
ok res = 981661739
Test #24:
score: 0
Accepted
time: 329ms
memory: 72856kb
input:
999999929
output:
...............................................................#...........................#..........................#......#...... ...............................................................#...........................#..........................#......#......
result:
ok res = 999999929
Test #25:
score: 0
Accepted
time: 333ms
memory: 72920kb
input:
35345813
output:
.........................................#..............#.............................#........................#......................#.......#.......#.. .........................................#..............#.............................#........................#......................#.......#......
result:
ok res = 35345813
Test #26:
score: 0
Accepted
time: 436ms
memory: 72932kb
input:
33810803
output:
.....................................#....................................#............#....#..#..........................#......................#.................#.............#.....#.. .....................................#....................................#............#....#..#....................
result:
ok res = 33810803
Test #27:
score: 0
Accepted
time: 338ms
memory: 72916kb
input:
966289935
output:
..................................#.......................#..............................#...........................#...................#.........#....#.. ..................................#.......................#..............................#...........................#...................#.........
result:
ok res = 966289935
Test #28:
score: 0
Accepted
time: 383ms
memory: 72892kb
input:
29521716
output:
................................................................#....................#.........#..............................................#.....................#................#......#..... ................................................................#....................#.........#............
result:
ok res = 29521716
Test #29:
score: 0
Accepted
time: 369ms
memory: 72752kb
input:
64472472
output:
......................................................#................................#...#.......................................#.....................#...........#..........#........ ......................................................#................................#...#.........................
result:
ok res = 64472472
Test #30:
score: 0
Accepted
time: 363ms
memory: 72980kb
input:
158427805
output:
.....................................#........................#...........#............................#.........................#....................#............#......#.. .....................................#........................#...........#............................#.........................
result:
ok res = 158427805
Test #31:
score: 0
Accepted
time: 340ms
memory: 73280kb
input:
476648214
output:
........................................................#...........#......#....#.........................#.................#............#...........#........#.. ........................................................#...........#......#....#.........................#.................#............#...
result:
ok res = 476648214
Test #32:
score: 0
Accepted
time: 323ms
memory: 73124kb
input:
460753020
output:
.........................................................#...........#..............................#...........................#..........................#.......#.... .........................................................#...........#..............................#...........................#.....
result:
ok res = 460753020
Test #33:
score: 0
Accepted
time: 343ms
memory: 72856kb
input:
846275927
output:
...............................................#...................#....................................#......................#.................#............#........ ...............................................#...................#....................................#......................#.......
result:
ok res = 846275927
Test #34:
score: 0
Accepted
time: 308ms
memory: 72816kb
input:
436044186
output:
.............................................#.......#...#................................#.....................#.................#.........#.......#.. .............................................#.......#...#................................#.....................#.................#.........#..........
result:
ok res = 436044186
Test #35:
score: 0
Accepted
time: 305ms
memory: 72928kb
input:
4714726
output:
...........................................#..#.....................................................#.................#......#......#...#.. ...........................................#..#.....................................................#.................#......#......#...#..
result:
ok res = 4714726
Test #36:
score: 0
Accepted
time: 289ms
memory: 72904kb
input:
405106993
output:
.....................................................#.......#..#..............................#........................#....................#........#........#.. .....................................................#.......#..#..............................#........................#...................
result:
ok res = 405106993
Test #37:
score: 0
Accepted
time: 314ms
memory: 73100kb
input:
395136214
output:
.................................................#.............................................#..#.........................#........................#.................#............#........#.. .................................................#.............................................#..#...........
result:
ok res = 395136214
Test #38:
score: 0
Accepted
time: 347ms
memory: 72908kb
input:
318600029
output:
.........................................................................#................#...#...#..........................................#.................#................#......#......#.. .........................................................................#................#...#...#..........
result:
ok res = 318600029
Test #39:
score: 0
Accepted
time: 330ms
memory: 73020kb
input:
446626687
output:
...........................................................................#.....................#............................................#..........................................#...... ...........................................................................#.....................#............
result:
ok res = 446626687
Test #40:
score: 0
Accepted
time: 284ms
memory: 72764kb
input:
152602867
output:
........................................................#...........................#...#.............................#....................#..............#..............#.............. ........................................................#...........................#...#.............................
result:
ok res = 152602867
Test #41:
score: 0
Accepted
time: 283ms
memory: 72996kb
input:
989466381
output:
...........................................#......#....#........................#......................#.....................#............#......#.. ...........................................#......#....#........................#......................#.....................#............#......#..
result:
ok res = 989466381
Test #42:
score: 0
Accepted
time: 305ms
memory: 72908kb
input:
936862096
output:
...........................#.....#.......................................#.................#.............#............#........... ...........................#.....#.......................................#.................#.............#............#...........
result:
ok res = 936862096
Test #43:
score: 0
Accepted
time: 287ms
memory: 72948kb
input:
716629682
output:
.......................................................#.........................................#.............................................#...........#...........#..........#.......#.. .......................................................#.........................................#...............
result:
ok res = 716629682
Test #44:
score: 0
Accepted
time: 343ms
memory: 72832kb
input:
777283759
output:
.......................................................#.......................#................#........................................................#................#...........#.......#.. .......................................................#.......................#................#............
result:
ok res = 777283759
Test #45:
score: 0
Accepted
time: 298ms
memory: 72948kb
input:
791644428
output:
.......................................................................#....#.........................#.....................#............#....#....#.. .......................................................................#....#.........................#.....................#............#....#....#..
result:
ok res = 791644428
Test #46:
score: 0
Accepted
time: 301ms
memory: 73020kb
input:
653877186
output:
....................................#................................#........#.............................#.....................#....................#..............#........#.. ....................................#................................#........#.............................#...............
result:
ok res = 653877186
Test #47:
score: 0
Accepted
time: 276ms
memory: 72944kb
input:
927194288
output:
............................................#..............................#.............................#...........................#.....#.. ............................................#..............................#.............................#...........................#.....#..
result:
ok res = 927194288
Test #48:
score: 0
Accepted
time: 275ms
memory: 72932kb
input:
926281794
output:
..............................................................#...........................#...#...........................#...........................#...................#...............#....#.. ..............................................................#...........................#...#.............
result:
ok res = 926281794
Test #49:
score: 0
Accepted
time: 246ms
memory: 72808kb
input:
244063801
output:
.............................................................#.....#...#..........................#....................#.................#...........#......#.. .............................................................#.....#...#..........................#....................#.................#.....
result:
ok res = 244063801
Test #50:
score: 0
Accepted
time: 308ms
memory: 72944kb
input:
536539457
output:
..................................#......................#.....#........................................#............................#...........#......#.....#.. ..................................#......................#.....#........................................#............................#.......
result:
ok res = 536539457
Test #51:
score: 0
Accepted
time: 292ms
memory: 73032kb
input:
462293418
output:
...................................................#......................................#...#...............................#.....................#..................#............#....#.. ...................................................#......................................#...#...................
result:
ok res = 462293418
Test #52:
score: 0
Accepted
time: 307ms
memory: 72940kb
input:
36920527
output:
.................................................#...................................#..#..........................................#..............#.............#.............#.....#.. .................................................#...................................#..#..............................
result:
ok res = 36920527
Test #53:
score: 0
Accepted
time: 323ms
memory: 73020kb
input:
172808412
output:
.........................................................................#.....#...#.......................#.................#............#........#..... .........................................................................#.....#...#.......................#.................#............#..........
result:
ok res = 172808412
Test #54:
score: 0
Accepted
time: 333ms
memory: 73036kb
input:
702785565
output:
................................................#..................#...#..............................#.....................#................#................#............ ................................................#..................#...#..............................#.....................#......
result:
ok res = 702785565
Test #55:
score: 0
Accepted
time: 338ms
memory: 73696kb
input:
364908069
output:
..................................................................#....................#.......................#.......................#.....................#..............#......#.. ..................................................................#....................#.......................#........
result:
ok res = 364908069
Test #56:
score: 0
Accepted
time: 319ms
memory: 72968kb
input:
700033068
output:
..............................................................#....................#...........#........................................................#...............#............#.....#..#.. ..............................................................#....................#...........#.............
result:
ok res = 700033068
Test #57:
score: 0
Accepted
time: 286ms
memory: 72876kb
input:
971419570
output:
................................................#......................................#...#.......................................................#...................#.......#...#... ................................................#......................................#...#...........................
result:
ok res = 971419570
Test #58:
score: 0
Accepted
time: 321ms
memory: 73092kb
input:
215988289
output:
................................................................#.............#...........................#...........................#.....................#..............#...... ................................................................#.............#...........................#.................
result:
ok res = 215988289
Test #59:
score: 0
Accepted
time: 309ms
memory: 72988kb
input:
233354450
output:
.................................#.......#...#........................................#................#..............#.............#........... .................................#.......#...#........................................#................#..............#.............#...........
result:
ok res = 233354450
Test #60:
score: 0
Accepted
time: 332ms
memory: 72832kb
input:
460230232
output:
..........................................................#.....................#.....#...#.....................................#.................................#..........#......#......#.. ..........................................................#.....................#.....#...#.....................
result:
ok res = 460230232
Test #61:
score: 0
Accepted
time: 336ms
memory: 73456kb
input:
169672436
output:
...........................................#.........#......#....................#....................#.................#............#......#.. ...........................................#.........#......#....................#....................#.................#............#......#..
result:
ok res = 169672436
Test #62:
score: 0
Accepted
time: 357ms
memory: 72900kb
input:
116851312
output:
.......#.......#....#....#......................................#.........................#.............#...........#........ .......#.......#....#....#......................................#.........................#.............#...........#........
result:
ok res = 116851312
Test #63:
score: 0
Accepted
time: 309ms
memory: 73748kb
input:
654952096
output:
.......................................................................#......#.................#...........#.........#.........#.........#.. .......................................................................#......#.................#...........#.........#.........#.........#..
result:
ok res = 654952096
Test #64:
score: 0
Accepted
time: 302ms
memory: 72924kb
input:
456784940
output:
.......................................................#............................#........#..........................#.....................#.....................#................#........#.. .......................................................#............................#........#...............
result:
ok res = 456784940
Test #65:
score: 0
Accepted
time: 309ms
memory: 72964kb
input:
903918017
output:
......................................................................................#.....#..#..............................#.......................#......................#.........#.....#.. ......................................................................................#.....#..#..............
result:
ok res = 903918017
Test #66:
score: 0
Accepted
time: 328ms
memory: 73028kb
input:
242185681
output:
.................................................#..................................#......#.......................................#....................#...............#...........#.......#.. .................................................#..................................#......#...................
result:
ok res = 242185681
Test #67:
score: 0
Accepted
time: 322ms
memory: 73124kb
input:
931841631
output:
........................................................#........................................#.........................#...................#................#..............#............ ........................................................#........................................#................
result:
ok res = 931841631
Test #68:
score: 0
Accepted
time: 327ms
memory: 73576kb
input:
705201940
output:
...........................................................#.................................#................................................#...................#...........#.......#....#.. ...........................................................#.................................#..................
result:
ok res = 705201940
Test #69:
score: 0
Accepted
time: 332ms
memory: 72916kb
input:
388071742
output:
.....................................#...............................................#.........................#............#.......#.. .....................................#...............................................#.........................#............#.......#..
result:
ok res = 388071742
Test #70:
score: 0
Accepted
time: 321ms
memory: 72892kb
input:
675160794
output:
................................................................................#......#...#.................................#........................#...................#..............#.... ................................................................................#......#...#....................
result:
ok res = 675160794
Test #71:
score: 0
Accepted
time: 308ms
memory: 72912kb
input:
12451783
output:
............................................................#.........................#..#.....................................................#..............#.........#.......#.......#.. ............................................................#.........................#..#.........................
result:
ok res = 12451783
Test #72:
score: 0
Accepted
time: 391ms
memory: 73528kb
input:
275972627
output:
...........................................#..............................#..........#......#............................................#......................#..........#........#........#.. ...........................................#..............................#..........#......#.................
result:
ok res = 275972627
Test #73:
score: 0
Accepted
time: 327ms
memory: 73228kb
input:
89200061
output:
..................................................#.....................#...#..#.......................................#..........................#.............#..........#....#.. ..................................................#.....................#...#..#.......................................#...
result:
ok res = 89200061
Test #74:
score: 0
Accepted
time: 304ms
memory: 73000kb
input:
873057364
output:
......................................#......................#..........................................#.......................................#.......#.....#.. ......................................#......................#..........................................#....................................
result:
ok res = 873057364
Test #75:
score: 0
Accepted
time: 324ms
memory: 73008kb
input:
469614007
output:
.................................................................................#.....................................#......................#.............#...#..#.. .................................................................................#.....................................#................
result:
ok res = 469614007
Test #76:
score: 0
Accepted
time: 308ms
memory: 73032kb
input:
223340210
output:
..............................................................#.................................#......................................#......................................#.........#..... ..............................................................#.................................#...............
result:
ok res = 223340210
Test #77:
score: 0
Accepted
time: 319ms
memory: 73384kb
input:
822198166
output:
............................................................................#.....#.....#..#........................#........................#........#......#......#.. ............................................................................#.....#.....#..#........................#..................
result:
ok res = 822198166
Test #78:
score: 0
Accepted
time: 290ms
memory: 72936kb
input:
455915168
output:
.............................................................#...#........................#........................#............#...........#.....#.. .............................................................#...#........................#........................#............#...........#.....#..
result:
ok res = 455915168
Test #79:
score: 0
Accepted
time: 293ms
memory: 73020kb
input:
194086925
output:
..........................................#...#...................................#............................#...........#...........#.......... ..........................................#...#...................................#............................#...........#...........#..........
result:
ok res = 194086925
Test #80:
score: 0
Accepted
time: 295ms
memory: 72964kb
input:
360828081
output:
............................................................#............................#...#.......................................#.................#.........#.........#........#.. ............................................................#............................#...#.........................
result:
ok res = 360828081
Test #81:
score: 0
Accepted
time: 318ms
memory: 73160kb
input:
474052493
output:
..................................................#.........................#...#.....................................#..................#................#...............#...#.. ..................................................#.........................#...#.....................................#......
result:
ok res = 474052493