QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405190#7927. Fortune Tellingevirir#TL 3205ms142272kbC++141.8kb2024-05-05 13:32:352024-05-05 13:32:37

Judging History

你现在查看的是最新测评结果

  • [2024-05-05 13:32:37]
  • 评测
  • 测评结果:TL
  • 用时:3205ms
  • 内存:142272kb
  • [2024-05-05 13:32:35]
  • 提交

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...

result: