QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#405190 | #7927. Fortune Telling | evirir# | TL | 3205ms | 142272kb | C++14 | 1.8kb | 2024-05-05 13:32:35 | 2024-05-05 13:32:37 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MOD = 998244353;
int mult(int a,int b)
{
return (a*1LL*b)%MOD;
}
int qp(ll x, int y) {
int z = 1;
for (; y; y >>= 1, x = x * x % MOD) {
if (y & 1) z = 1LL * z * x % MOD;
}
return z;
}
int inv(int a){return qp(a,MOD-2);}
int in[7];
const int MAXN = 3e5+5;
map<int,int>dp[MAXN];
int solve(int n,int k){
if(n==1){
//Bcout<<n<<" "<<k<<" "<<1<<'\n';
return 1;
}
if(dp[n].find(k) != dp[n].end())return dp[n][k];
int num = min(n,6);
dp[n][k] = 0;
for(int i=1;i<=num;i++){
if(k%6 == i%6)continue;
int k0 = k - (k-1)/6;
int n0 = n - (n-1)/6;
int rk = k%6;
int rn = n%6;
if(rk == 0)rk = 6;
if(rn == 0)rn = 6;
if(rk >= i)k0--;
if(rn >= i)n0--;
dp[n][k] += solve(n0,k0);
if(dp[n][k]>=MOD)dp[n][k]-=MOD;
}
dp[n][k] = mult(dp[n][k],in[num]);
//cout<<n<<" "<<k<<" "<<dp[n][k]<<'\n';
return dp[n][k];
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=6;i++)in[i] = inv(i);
for(int i=1;i<=n;i++)cout<<solve(n,i)<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 17652kb
input:
3
output:
332748118 332748118 332748118
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 17588kb
input:
7
output:
305019108 876236710 876236710 876236710 876236710 876236710 305019108
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 17636kb
input:
8
output:
64701023 112764640 160828257 160828257 160828257 160828257 112764640 64701023
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 17720kb
input:
10
output:
409773145 853745402 299473306 743445563 189173467 189173467 743445563 299473306 853745402 409773145
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 5ms
memory: 17652kb
input:
11
output:
989514850 873566509 757618168 641669827 525721486 409773145 525721486 641669827 757618168 873566509 989514850
result:
ok 11 lines
Test #6:
score: 0
Accepted
time: 6ms
memory: 17688kb
input:
12
output:
175103562 138336949 101570336 64803723 28037110 989514850 989514850 28037110 64803723 101570336 138336949 175103562
result:
ok 12 lines
Test #7:
score: 0
Accepted
time: 2ms
memory: 17604kb
input:
13
output:
159099473 484299138 167572226 849089667 532362755 215635843 175103562 215635843 532362755 849089667 167572226 484299138 159099473
result:
ok 13 lines
Test #8:
score: 0
Accepted
time: 3205ms
memory: 142272kb
input:
131091
output:
567383016 662994174 732938392 473447067 205102363 749004511 410127252 89326957 304368813 405336094 96918015 896888521 737639871 508973310 349553790 121346210 739328699 633788498 95902577 411856713 705314547 568274283 647209576 401593169 250679135 133612309 639836192 600464933 338261759 832985164 518...
result:
ok 131091 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 17624kb
input:
14
output:
947151085 589891892 674722122 956565255 240164035 522007168 561598032 561598032 522007168 240164035 956565255 674722122 589891892 947151085
result:
ok 14 lines
Test #10:
score: 0
Accepted
time: 6ms
memory: 17724kb
input:
15
output:
637039767 460763713 462646547 333815057 96269873 856969042 271282146 750138182 271282146 856969042 96269873 333815057 462646547 460763713 637039767
result:
ok 15 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 17624kb
input:
16
output:
228892706 883702432 747017242 402641198 772461176 894058019 115446252 447880564 447880564 115446252 894058019 772461176 402641198 747017242 883702432 228892706
result:
ok 16 lines
Test #12:
score: 0
Accepted
time: 6ms
memory: 17636kb
input:
17
output:
903981410 862346530 997767939 885172564 487381090 33762637 823581070 80265784 832169836 80265784 823581070 33762637 487381090 885172564 997767939 862346530 903981410
result:
ok 17 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 17600kb
input:
18
output:
31744296 579723162 218537119 508969018 404962409 246598953 48644633 989179173 465496473 465496473 989179173 48644633 246598953 404962409 508969018 218537119 579723162 31744296
result:
ok 18 lines
Test #14:
score: 0
Accepted
time: 6ms
memory: 17648kb
input:
19
output:
856240157 861682308 431212253 293953179 552074030 697393155 911422408 885288577 288395015 423610073 288395015 885288577 911422408 697393155 552074030 293953179 431212253 861682308 856240157
result:
ok 19 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 17632kb
input:
2
output:
499122177 499122177
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 17648kb
input:
20
output:
308054940 613046471 627077388 876731984 177753318 168429486 670640271 198941540 78614976 772809215 772809215 78614976 198941540 670640271 168429486 177753318 876731984 627077388 613046471 308054940
result:
ok 20 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 17708kb
input:
21
output:
982695520 584249571 230343344 502166250 95786010 45929897 966423983 499961052 602742551 195298383 571250409 195298383 602742551 499961052 966423983 45929897 95786010 502166250 230343344 584249571 982695520
result:
ok 21 lines
Test #18:
score: 0
Accepted
time: 5ms
memory: 17700kb
input:
22
output:
966781769 485759206 207027266 706375129 431325017 29239160 854886038 860244349 975296442 757095317 214558602 214558602 757095317 975296442 860244349 854886038 29239160 431325017 706375129 207027266 485759206 966781769
result:
ok 22 lines
Test #19:
score: -100
Time Limit Exceeded
input:
220223
output:
904620830 570662262 259789297 26081430 875852152 157789135 813374609 696357431 573660829 912186928 302936478 446257515 508716017 720193773 61498818 573701804 35401989 335790053 147155562 720189556 202742334 898770323 563779215 679480614 964058891 284782141 780438196 409505450 327113979 435543803 703...