QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532172#7927. Fortune TellingWaterSunWA 0ms3884kbC++141.9kb2024-08-25 00:59:482024-08-25 00:59:48

Judging History

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

  • [2024-08-25 00:59:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3884kb
  • [2024-08-25 00:59:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 998244353;
int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
	return (LL) a * b % mod;
}
int binpow(int a, int n)
{
	int res = 1;
	while(n)
	{
		if(n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

map<int, VI> dp;
const int ml6 = binpow(6, mod - 2);

LL sum = 0;

void solve(int n)
{
	if(dp.count(n))
		return;
	sum += n;

	if(n <= 6)
	{
		VI res(n, binpow(n, mod - 2));
		dp[n] = res;
        // cerr << n << " " << binpow(n,mod - 2) << " ???\n";
		return;
	}
	
    solve(5 * n / 6);
    solve(5 * n / 6 + 1);
    VI a = dp[5 * n / 6],b = dp[5 * n / 6 + 1];
	
	VI res(n);
	
	FOR(j, 0, 6)
	{
		int cnt = 0;
		FOR(i, 0, n)
		{
			if(i % 6 == j)
				continue;
			if(j < n % 6)
				res[i] = add(res[i], a[cnt]);
                // ,cerr << i << " " << cnt << " " << a[cnt] << " first\n";
			else
				res[i] = add(res[i], b[cnt]);
                // ,cerr << i << " " << cnt << " " << b[cnt] << " second\n";
			cnt++;
		}
	}
    // cerr << n << " begin:\n";
    // FOR(i, 0, n) cerr << res[i] << " "; cerr << "\n";
	FOR(i, 0, n)
		res[i] = mult(res[i], ml6);
    // cerr << "\n";
	dp[n] = res;
}



int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);

	int n;
	cin >> n;

	solve(n);
	VI res = dp[n];
	FOR(i, 0, n)
	{
		cout << res[i] << "\n";
	}
	//cerr << sum << "\n";

	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

3

output:

332748118
332748118
332748118

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

7

output:

305019108
876236710
876236710
876236710
876236710
876236710
305019108

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

8

output:

64701023
112764640
160828257
160828257
160828257
160828257
112764640
64701023

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10

output:

409773145
853745402
299473306
743445563
189173467
189173467
743445563
299473306
853745402
409773145

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

11

output:

989514850
873566509
757618168
641669827
525721486
409773145
525721486
641669827
757618168
873566509
989514850

result:

ok 11 lines

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3612kb

input:

12

output:

159099473
81800579
4501685
925447144
848148250
770849356
175103562
252402456
329701350
407000244
484299138
561598032

result:

wrong answer 1st lines differ - expected: '175103562', found: '159099473'