#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long llo;
#define a first
#define b second
#define endl "\n"
int aa=7;
int aac[1000001][20];
vector<int> pre[120];
int sl3[21];
int sl[22];
int l;
int dp[1600000];//3^12
int last[1600000];//3^12
int ans[1000001];//q
int it[1100001];//n
int num[1100001];//q
int oo[1600000];
int ok;
void find(int ind,int tot,int ind2){//pre_sub
if(ind==aa){
pre[tot].pb(ind2);
// cout<<tot<<" "<<ind2<<endl;
}
else{
if(aac[ind2][ind]%2==0){
find(ind+1,tot,ind2);
}
if(aac[ind2][ind]>0){
find(ind+1,tot+sl[aa-ind-1],ind2);
}
}
}
void find2(int ind,int ind2,int tot=0){//
if(ind==l-aa){
last[tot]=ind2;
// cout<<tot<<","<<ind2<<endl;
return;
}
if(ind==ind2){
find2(ind+1,ind2,tot+2*sl3[(l-aa)-ind-1]);
}
else{
find2(ind+1,ind2,tot);
find2(ind+1,ind2,tot+sl3[(l-aa)-ind-1]);
}
if(ind<ind2){
find2(ind+1,ind2,tot+2*sl3[(l-aa)-ind-1]);
}
}
int find3(int ind){//dp
if(dp[ind]>-1){
return dp[ind];
}
if(last[ind]==-1){
dp[ind]=it[oo[ind]+ok*(sl[l-aa])];
return dp[ind];
}
dp[ind]=find3(ind-sl3[l-aa-last[ind]-1])+find3(ind-2*sl3[l-aa-last[ind]-1]);
return dp[ind];
}
void find4(int ind5,int su1=0,int su2=0){
if(ind5==12){
oo[su1]=su2;
/*if(su1==4){
cout<<su2<<endl;
}*/
}
else{
find4(ind5+1,su1,su2);
find4(ind5+1,su1+sl3[12-ind5-1],su2+sl[12-ind5-1]);
find4(ind5+1,su1+2*sl3[12-ind5-1],su2);
}
}
//void(int)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(last,-1,sizeof(last));
memset(num,0,sizeof(num));
sl[0]=1;
for(int i=1;i<22;i++){
sl[i]=2*sl[i-1];
}
sl3[0]=1;
for(int i=1;i<14;i++){
sl3[i]=3*sl3[i-1];
}
int q;
cin>>l>>q;
aa=min((int)7,l-1);
int n=sl[l];
char ss;
for(int i=0;i<n;i++){
cin>>ss;
it[i]=ss-'0';
}
for(int ii=0;ii<q;ii++){
for(int i=0;i<l;i++){
cin>>ss;
if(ss=='0'){
aac[ii][i]=0;
if(l==1){
cout<<it[0]<<endl;
}
}
else if(ss=='1'){
aac[ii][i]=1;
if(l==1){
cout<<it[1]<<endl;
}
else{
if(i>=aa){
num[ii]+=sl3[l-i-1];
}
}
}
else{
aac[ii][i]=2;
if(l==1){
cout<<it[0]+it[1]<<endl;
}
else{
if(i>=aa){
num[ii]+=2*sl3[l-i-1];
}
}
}
}
}
/*for(int i=0;i<q;i++){
cout<<num[i]<<" ";
}
cout<<endl;*/
if(l==1){
return 0;
}
for(int i=0;i<q;i++){
find((int)0,(int)0,i);
}
memset(ans,(int)0,sizeof(ans));
for(int i=0;i<l-aa;i++){
find2((int)0,i,(int)0);
}
/* for(int j=0;j<1600000;j++){
int jj=j;
int ind5=0;
int sp=0;
while(jj){
if(jj%3==1){
sp+=sl[ind5];
}
jj/=3;
ind5+=1;
}
oo[j]=sp;
}*/
find4(0);
//cout<<oo[4]<<endl;
for(int i=0;i<120;i++){
ok=i;
if(pre[i].size()){
memset(dp,(int)-1,sizeof(dp));
for(auto j:pre[i]){
//ans[j]+=it[i];
find3(num[j]);
ans[j]+=dp[num[j]];
// cout<<i<<":"<<j<<":"<<dp[num[j]]<<endl;
}
}
}
for(int i=0;i<q;i++){
cout<<ans[i]<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
22136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
22136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
22136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
22136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
22136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
