QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279577 | #7420. K-pop Strings | Dualqwq | TL | 1ms | 3676kb | C++20 | 1.2kb | 2023-12-08 21:32:37 | 2023-12-08 21:32:38 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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