QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279582#7420. K-pop StringsDualqwqTL 3924ms4044kbC++201.4kb2023-12-08 21:35:132023-12-08 21:35:14

Judging History

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

  • [2023-12-08 21:35:14]
  • 评测
  • 测评结果:TL
  • 用时:3924ms
  • 内存:4044kb
  • [2023-12-08 21:35:13]
  • 提交

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;}
mt19937 Rnd(114514);
int n,k,L,R;
struct BCJ {
	int ufs[N];
	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;
vector<pair<int,int> > rep;
inline void DFS(int x,BCJ &S,int coef) {
	if(x == (int)rep.size()) {
		int mul = 1;
		for(int i = 1;i <= n;i++) if(S.find(i) == i) mul = 35ll * mul % P;
		Plus(Ans,1ll * coef * mul % P);
		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++)
		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;
	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;
	return 0;
}

详细

Test #1:

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

input:

1 16

output:

35

result:

ok 1 number(s): "35"

Test #2:

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

input:

4 0

output:

1499400

result:

ok 1 number(s): "1499400"

Test #3:

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

input:

15 5

output:

911125634

result:

ok 1 number(s): "911125634"

Test #4:

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

input:

35 5

output:

93640047

result:

ok 1 number(s): "93640047"

Test #5:

score: 0
Accepted
time: 803ms
memory: 4012kb

input:

100 16

output:

991183816

result:

ok 1 number(s): "991183816"

Test #6:

score: 0
Accepted
time: 3924ms
memory: 3892kb

input:

22 16

output:

960803400

result:

ok 1 number(s): "960803400"

Test #7:

score: -100
Time Limit Exceeded

input:

20 16

output:


result: