QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863802 | #8116. Kocke | Unforgettablepl | 0 | 0ms | 0kb | C++20 | 1.2kb | 2025-01-19 22:44:26 | 2025-01-19 22:44:31 |
answer
// #pragma GCC optimize("Os")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int modulo = 1e9+7;
int32_t main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n,K;
cin >> n >> K;
vector DP(501,vector(125250,vector<int>(2,0)));
vector lookup(501,vector(501,0));
int cnt = 0;
for(int i=1;i<=500;i++){
for(int j=i;j<=500;j++){
lookup[i][j]=cnt++;
}
}
for(int i=1;i<=K;i++)DP[1][lookup[i][i]][0]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=K;j++){
for(int k=j+1;k<=K;k++){
DP[i][lookup[j][k]][0]=(DP[i-2][lookup[j][k]][0]+DP[i-1][lookup[j+1][k]][0])%modulo;
if(i-(k-j)>=1)DP[i][lookup[j][k]][0]=(DP[i][lookup[j][k]][0]+DP[i-(k-j)][lookup[j+1][k]][1])%modulo;
DP[i][lookup[j][k]][1]=(DP[i-2][lookup[j][k]][1]+DP[i-1][lookup[j][k-1]][1])%modulo;
if(i-(k-j)>=1)DP[i][lookup[j][k]][1]=(DP[i][lookup[j][k]][1]+DP[i-(k-j)][lookup[j][k-1]][0])%modulo;
}
}
}
long long ans = 0;
for(int l=1;l<=K;l++){
for(int r=l+1;r<=K;r++){
ans += (DP[n][lookup[l][r]][0]+DP[n][lookup[l][r]][1])%modulo;
ans += (DP[n-1][lookup[l][r]][0]+DP[n-1][lookup[l][r]][1])%modulo;
ans%=modulo;
}
}
cout << ans << '\n';
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
2 3
output:
4
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%