QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279582 | #7420. K-pop Strings | Dualqwq | TL | 3924ms | 4044kb | C++20 | 1.4kb | 2023-12-08 21:35:13 | 2023-12-08 21:35:14 |
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;}
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;
}
Details
Tip: Click on the bar to expand more detailed information
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