QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #611028 | #7006. Rikka with Subsequences | konata2828 | AC ✓ | 755ms | 4272kb | C++23 | 1.1kb | 2024-10-04 18:52:29 | 2024-10-04 18:52:29 |
Judging History
answer
// Hydro submission #66ffc8ea55b5e82bc01754fe@1728039147013
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n;
int a[205];
bool e[205][205];
int f[205][205],g[205][205];
void test()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
char x;
cin>>x;
e[i][j]=x-'0';
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=g[i][j]=0;
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(a[i]==a[j]&&a[j]==a[k])
f[j][k]=g[j][k]+1;
else
f[j][k]=0;
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
f[j][k]=(f[j][k]+f[j-1][k]+f[j][k-1]-f[j-1][k-1]+mod)%mod;
(ans+=f[n][n])%=mod;
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(a[j]==a[k]&&e[a[i]][a[j]])
(g[j][k]+=f[j-1][k-1])%=mod;
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
for(int i=1;i<=t;i++)
test();
}
/*
1
4
1 2 1 2
1111
1111
1111
1111
*/
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
input:
1 4 1 2 1 2 1111 1111 1111 1111
output:
51
result:
ok single line: '51'
Test #2:
score: 0
Accepted
time: 755ms
memory: 4272kb
input:
20 195 4 5 4 3 2 4 3 5 1 5 4 3 4 3 1 5 4 4 5 2 2 2 2 4 1 5 3 4 1 1 1 2 1 1 5 5 4 5 4 5 5 4 5 2 1 2 5 4 5 1 1 3 1 2 2 3 3 5 2 3 3 1 4 4 2 4 2 4 3 4 1 1 1 4 3 5 1 1 3 2 2 5 1 3 1 5 1 5 5 3 5 3 3 2 5 1 3 2 4 1 5 5 1 3 3 2 4 2 3 3 3 4 1 3 3 3 5 5 1 1 4 2 5 1 2 5 4 3 5 1 5 5 5 4 2 2 5 3 2 3 4 1 3 2 1 5 3...
output:
806298135 541285042 48173297 222851978 875793336 100057791 156057874 129923599 551277543 874547790 544405786 653241411 521317929 370918040 803940504 969296122 806596012 469227084 338962879 194278629
result:
ok 20 lines