QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279577#7420. K-pop StringsDualqwqTL 1ms3676kbC++201.2kb2023-12-08 21:32:372023-12-08 21:32:38

Judging History

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

  • [2023-12-08 21:32:38]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3676kb
  • [2023-12-08 21:32:37]
  • 提交

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;}
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() {
	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);

	BCJ ini;
	for(int i = 1;i <= n;i++) ini.ufs[i] = i;
	DFS(0,ini,1);
	cout << Ans << endl;
	return 0;
}

詳細信息

Test #1:

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

input:

1 16

output:

35

result:

ok 1 number(s): "35"

Test #2:

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

input:

4 0

output:

1499400

result:

ok 1 number(s): "1499400"

Test #3:

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

input:

15 5

output:

911125634

result:

ok 1 number(s): "911125634"

Test #4:

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

input:

35 5

output:

93640047

result:

ok 1 number(s): "93640047"

Test #5:

score: -100
Time Limit Exceeded

input:

100 16

output:


result: