QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #392156 | #8330. Count off 3 | 2745518585 | WA | 759ms | 88020kb | C++20 | 2.9kb | 2024-04-17 10:22:48 | 2024-04-17 10:22:48 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N=20001;
const ll P=1e9+7;
int n,pw[7][N],b[7];
ll f1[N][8][8][8],f2[N][8][8][8];
char a[N];
int main()
{
for(int i=1;i<=6;++i)
{
pw[i][0]=1;
for(int j=1;j<=10000;++j) pw[i][j]=pw[i][j-1]*i%7;
}
f1[0][0][0][0]=f2[0][1][1][1]=1;
for(int i=1;i<=10000;++i)
{
for(int j1=0;j1<=6;++j1) for(int j2=0;j2<=6;++j2) for(int j3=0;j3<=6;++j3)
{
(f1[i][j1][j2][j3]+=f1[i-1][j1][j2][j3])%=P;
(f2[i][j1][j2][j3]+=f2[i-1][j1][j2][j3])%=P;
if(i%2==1)
{
(f1[i][(j1+pw[1][i])%7][(j2+pw[2][i])%7][(j3+pw[3][i])%7]+=f1[i-1][j1][j2][j3])%=P;
}
else
{
(f2[i][(j1+pw[1][i])%7][(j2+pw[2][i])%7][(j3+pw[3][i])%7]+=f2[i-1][j1][j2][j3])%=P;
}
}
}
for(int i=0;i<=10000;++i)
{
for(int j1=0;j1<=6;++j1) for(int j2=0;j2<=6;++j2) for(int j3=0;j3<=6;++j3) (f2[i][j1][j2][7]+=f2[i][j1][j2][j3])%=P;
for(int j1=0;j1<=6;++j1) for(int j2=0;j2<=6;++j2) for(int j3=0;j3<=7;++j3) (f2[i][j1][7][j3]+=f2[i][j1][j2][j3])%=P;
for(int j1=0;j1<=6;++j1) for(int j2=0;j2<=7;++j2) for(int j3=0;j3<=7;++j3) (f2[i][7][j2][j3]+=f2[i][j1][j2][j3])%=P;
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",a+1);
n=strlen(a+1);
for(int i=1;i<=6;++i) b[i]=0;
ll s=0;
for(int i=n-1;i>=1;--i)
{
if(a[n-i]=='1')
{
// for(int i=1;i<=6;++i) printf("%d ",b[i]);printf("\n");
for(int j1=0;j1<=6;++j1) for(int j2=0;j2<=6;++j2) for(int j3=0;j3<=6;++j3)
{
if(f1[i-1][j1][j2][j3]==0) continue;
vector<int> p1={7,((-b[1]-j1)%7+7)%7,((-b[6]+j1)%7+7)%7},p2={7,((-b[2]-j2)%7+7)%7,((-b[5]+j2)%7+7)%7},p3={7,((-b[3]-j3)%7+7)%7,((-b[4]+j3)%7+7)%7};
if(p1[1]==p1[2]) p1.pop_back();
if(p2[1]==p2[2]) p2.pop_back();
if(p3[1]==p3[2]) p3.pop_back();
for(auto k1:p1) for(auto k2:p2) for(auto k3:p3)
{
int z=((k1<7)^(k2<7)^(k3<7))?-1:1;
s=(s+z*f1[i-1][j1][j2][j3]*f2[i-1][k1][k2][k3]%P)%P;
// printf("%d %d %d %d %d %d: %d %lld %lld\n",j1,j2,j3,k1,k2,k3,z,f1[i-1][j1][j2][j3],f2[i-1][k1][k2][k3]);
}
}
for(int j=1;j<=6;++j) b[j]=(b[j]+pw[j][i])%7;
}
}
if(a[n]=='1')
{
for(int i=1;i<=6;++i) b[i]=(b[i]+1)%7;
if([&](){for(int i=1;i<=6;++i) if(b[i]==0) return false; return true;}()) ++s;
}
printf("%lld\n",s);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 39ms
memory: 88020kb
input:
5 1 1010 110101 1000111000 101101001000
output:
1 2 15 114 514
result:
ok 5 number(s): "1 2 15 114 514"
Test #2:
score: 0
Accepted
time: 91ms
memory: 84804kb
input:
10 1 11 1000 10111011 1000110100101001 11101110000001000011010011011000 110011000111110001101010101100100011010010101000011111001101011 11010111011101000010101111011111011011100001001101010011101011111111011011111101110110010011001101000001000111100010010111000010 10000000000000000000000000000000000...
output:
1 1 2 45 6591 814196699 193088128 849103726 497125329 363076920
result:
ok 10 numbers
Test #3:
score: -100
Wrong Answer
time: 759ms
memory: 85088kb
input:
10 1 101 100101000 111111001111011001111100111 100001101010101000101110010111010010001101101110011111000001010001111100101010000 111001010100100100110011110111000111001001001001000100000011000110011000110101010010100000100101110101000011000011100010011001011000101110100111000110011011010111011111011...
output:
1 2 64 27062688 486363229 184013394 580592021 118930214 -227335289 344619804
result:
wrong answer 9th numbers differ - expected: '772664718', found: '-227335289'