subject
The first question on the first day is usually a big water question to send points, and this time is no exception.
Given n m-dimensional vectors, the value of each dimension can only be 1 or 2 or 3 or 4. Then there are q questions, each of which is one of the four questions:
(1) Given A vector C, ask how many methods there are to select two vectors A and B from these n vectors, so that for each one-dimensional i(1 ≤ i ≤ m), the maximum values of A i and B i are less than or equal to C i.
(2) Given A vector C, ask how many methods there are to select two vectors A and B from these n vectors, so that for each one-dimensional i(1 ≤ i ≤ m), the minimum values of A i and B i are greater than or equal to C i.
(3) Given A vector C, ask how many ways to select two vectors A and B from these n vectors, so that for each one-dimensional i(1 ≤ i ≤ m), the maximum values of A i and B i are greater than or equal to C i.
(4) Given A vector C, ask how many methods there are to select two vectors A and B from these n vectors, so that for each one-dimensional i(1 ≤ i ≤ m), the minimum values of A i and B i are less than or equal to C i.
Among them, C is also an m-dimensional vector, and the value of each dimension can only be 1 or 2 or 3 or 4. A i represents the value of the ith dimension of vector a, and B i and C i are the same.
In order to more accurately explain the meaning of "how many methods", we stipulate that if the vector read in for the ith time is the ith vector, then one method corresponds to a set {i,j} (i is not equal to j). The two methods are not the same method if and only if their corresponding sets {i,j} are different.
thinking
An ill intentioned title and an ill intentioned face
And when you really start doing this problem, you know what nausea is
This is a high-dimensional prefix and, how many dimensions? Not much, just 10 dimensions
410 array? Yes, six more
Questioner: come on, hurt each other
The first and second questions are simple high-dimensional prefixes, suffixes and. The third and fourth questions need to separate the previous differences and make prefixes, suffixes and again
949 lines of code, 26.8 KB, ah, you know
whole
whole
whole
body
body
body
rise
rise
rise
stand
stand
stand
code:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int u[10],rr[4][4][4][4][4][4][4][4][4][4],ll[4][4][4][4][4][4][4][4][4][4];
long long ans1[4][4][4][4][4][4][4][4][4][4],x;
long long ans3[4][4][4][4][4][4][4][4][4][4];
long long ans2[4][4][4][4][4][4][4][4][4][4];
long long ans4[4][4][4][4][4][4][4][4][4][4];
inline int read()
{
int ret,c,f=1;
while (((c=getchar())> '9'||c< '0')&&c!='-');
if (c=='-') f=-1,ret=0;
else ret=c-'0';
while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret*f;
}
int readc()
{
char c=getchar();
while (c<'0'||c>'9') c=getchar();
return c-'1';
}
int main()
{
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
int n=read(),m=read();
for (int i=1;i<=n;i++)
{
for (int j=0;j<m;j++)
{
u[j]=readc();
}
getchar();
ll[u[0]][u[1]][u[2]][u[3]][u[4]][u[5]][u[6]][u[7]][u[8]][u[9]]++;
rr[u[0]][u[1]][u[2]][u[3]][u[4]][u[5]][u[6]][u[7]][u[8]][u[9]]++;
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=1;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0-1];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][4-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=1;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3][q4][q5][q6][q7][q8][q9-1][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][4-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=1;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3][q4][q5][q6][q7][q8-1][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][4-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=1;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3][q4][q5][q6][q7-1][q8][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][4-q7][3-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=1;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3][q4][q5][q6-1][q7][q8][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][3-q3][3-q4][3-q5][4-q6][3-q7][3-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=1;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3][q4][q5-1][q6][q7][q8][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][3-q3][3-q4][4-q5][3-q6][3-q7][3-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=1;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3][q4-1][q5][q6][q7][q8][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][3-q3][4-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=1;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2][q3-1][q4][q5][q6][q7][q8][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][3-q2][4-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=1;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1][q2-1][q3][q4][q5][q6][q7][q8][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[3-q1][4-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=1;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ll[q1-1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
rr[3-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0]+=rr[4-q1][3-q2][3-q3][3-q4][3-q5][3-q6][3-q7][3-q8][3-q9][3-q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
x=ll[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
ans1[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]=x*(x-1)/2;
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]=ans1[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
x=rr[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
ans2[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]=x*(x-1)/2;
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]=ans2[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<3;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0+1];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<3;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9+1][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<3;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3][q4][q5][q6][q7][q8+1][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<3;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3][q4][q5][q6][q7+1][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<3;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3][q4][q5][q6+1][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<3;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3][q4][q5+1][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<3;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3][q4+1][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<3;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2][q3+1][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<3;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1][q2+1][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<3;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans4[q1+1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=1;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0-1];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=1;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9-1][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=1;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3][q4][q5][q6][q7][q8-1][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=1;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3][q4][q5][q6][q7-1][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=1;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3][q4][q5][q6-1][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=1;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3][q4][q5-1][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=1;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3][q4-1][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=1;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2][q3-1][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=0;q1<4;q1++) for (int q2=1;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1][q2-1][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=1;q1<4;q1++) for (int q2=0;q2<4;q2++)
{
for (int q3=0;q3<4;q3++) for (int q4=0;q4<4;q4++)
{
for (int q5=0;q5<4;q5++) for (int q6=0;q6<4;q6++)
{
for (int q7=0;q7<4;q7++) for (int q8=0;q8<4;q8++)
{
for (int q9=0;q9<4;q9++) for (int q0=0;q0<4;q0++)
{
ans4[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans4[q1-1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=1;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0-1];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=1;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9-1][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=1;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3][q4][q5][q6][q7][q8-1][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=1;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3][q4][q5][q6][q7-1][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=1;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3][q4][q5][q6-1][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=1;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3][q4][q5-1][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=1;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3][q4-1][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=1;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2][q3-1][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=1;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1][q2-1][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=1;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]-=ans3[q1-1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=2;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0+1];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=2;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9+1][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=2;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3][q4][q5][q6][q7][q8+1][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=2;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3][q4][q5][q6][q7+1][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=2;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3][q4][q5][q6+1][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=2;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3][q4][q5+1][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=2;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3][q4+1][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=2;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2][q3+1][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=3;q1>=0;q1--) for (int q2=2;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1][q2+1][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
for (int q1=2;q1>=0;q1--) for (int q2=3;q2>=0;q2--)
{
for (int q3=3;q3>=0;q3--) for (int q4=3;q4>=0;q4--)
{
for (int q5=3;q5>=0;q5--) for (int q6=3;q6>=0;q6--)
{
for (int q7=3;q7>=0;q7--) for (int q8=3;q8>=0;q8--)
{
for (int q9=3;q9>=0;q9--) for (int q0=3;q0>=0;q0--)
{
ans3[q1][q2][q3][q4][q5][q6][q7][q8][q9][q0]+=ans3[q1+1][q2][q3][q4][q5][q6][q7][q8][q9][q0];
}
}
}
}
}
int mm=read();
for (int i=1;i<=mm;i++)
{
int qq=read();
for (int j=0;j<m;j++)
{
u[j]=readc();
}
getchar();
if (qq==1)
{
printf("%lld\n",ans1[u[0]][u[1]][u[2]][u[3]][u[4]][u[5]][u[6]][u[7]][u[8]][u[9]]);
}
if (qq==2)
{
printf("%lld\n",ans2[u[0]][u[1]][u[2]][u[3]][u[4]][u[5]][u[6]][u[7]][u[8]][u[9]]);
}
if (qq==3)
{
printf("%lld\n",ans3[u[0]][u[1]][u[2]][u[3]][u[4]][u[5]][u[6]][u[7]][u[8]][u[9]]);
}
if (qq==4)
{
printf("%lld\n",ans4[u[0]][u[1]][u[2]][u[3]][u[4]][u[5]][u[6]][u[7]][u[8]][u[9]]);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}