QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279596#7420. K-pop StringsDualqwqTL 6090ms3888kbC++201.7kb2023-12-08 21:49:462023-12-08 21:49:46

Judging History

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

  • [2023-12-08 21:49:46]
  • 评测
  • 测评结果:TL
  • 用时:6090ms
  • 内存:3888kb
  • [2023-12-08 21:49:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5,K = 25,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
const int invc = qpow(35,P - 2);
mt19937 Rnd(1919810);
int n,k,L,R;
struct BCJ {
	vector<int> ufs;
	int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]);}
	inline void Merge(int x,int y) { ufs[find(x)] = find(y);}
};
int Ans,CNT;
vector<pair<int,int> > rep;
inline void DFS(int x,BCJ &S,int coef) {
	if(x == (int)rep.size()) {
		// Plus(Ans,coef);
		int mul = 1;
		for(int i = 1;i <= n;i++) if(S.ufs[i] == i) mul = 35ll * mul % P;
		Plus(Ans,1ll * coef * mul % P);
		++CNT;
		return;
	}
	int mid = rep[x].first,len = rep[x].second;
	bool flg = 0;
	for(int i = mid - len + 1;i <= mid;i++)
		if(S.find(i) != S.find(i + len)) {flg = 1;break;}
	if(!flg) return;
	BCJ T = S;
	DFS(x + 1,S,coef);
	for(int i = mid - len + 1;i <= mid;i++) {
		// if(T.find(i) != T.find(i + len)) coef = 1ll * coef * invc % P;
		T.Merge(i,i + len);
	}
	DFS(x + 1,T,P - coef);
}
int main() {
	// freopen("tmp.in","r",stdin);
	cin >> n >> k;
	if((n - k) & 1) --k;
	if(n - k <= 0) k = n - 2;
	L = (n - k) / 2;R = (n + k) / 2;
	L = max(1,L);R = min(n,R);
	for(int i = L;i <= R;i++)
		for(int len = (n - k) / 2;len <= min(i,n - i);++len)
			rep.emplace_back(i,len);
	shuffle(rep.begin(),rep.end(),Rnd);
	BCJ ini;ini.ufs.resize(n + 1);
	for(int i = 1;i <= n;i++) ini.ufs[i] = i;
	DFS(0,ini,1);
	cout << Ans << endl;
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
	cerr << CNT << endl;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3752kb

input:

1 16

output:

35

result:

ok 1 number(s): "35"

Test #2:

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

input:

4 0

output:

1499400

result:

ok 1 number(s): "1499400"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

15 5

output:

911125634

result:

ok 1 number(s): "911125634"

Test #4:

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

input:

35 5

output:

93640047

result:

ok 1 number(s): "93640047"

Test #5:

score: 0
Accepted
time: 570ms
memory: 3800kb

input:

100 16

output:

991183816

result:

ok 1 number(s): "991183816"

Test #6:

score: 0
Accepted
time: 2426ms
memory: 3772kb

input:

22 16

output:

960803400

result:

ok 1 number(s): "960803400"

Test #7:

score: 0
Accepted
time: 6090ms
memory: 3888kb

input:

20 16

output:

235606959

result:

ok 1 number(s): "235606959"

Test #8:

score: -100
Time Limit Exceeded

input:

17 15

output:


result: