> #include <iostream>
> #include <cstdio>
> #define INF 2000000000
> using namespace std;
> 
> int mod[21][21],r[21],tr[21],p,best,lastm,lastr;
> 
> void solve(int num,int now) {
> int t,i,ii,j;
> 
> 	if (num>=best) return;
> 	if (now==0) {
> 		best=num;
> 		return;
> 	}
> 	t=mod[now][now-1];
> 	for (i=0;i<p;++i)
> 		if ((t*i)%p==r[now]) {
> 			for (j=1;j<now;++j) {
> 				tr[j]=r[j];
> 				r[j]=(r[j]-i*mod[j][now-1]%p+p)%p;
> 			}
> 			ii=(i==0)?0:1;
> 			solve(num+ii,now-1);
> 			for (j=1;j<now;++j)
> 				r[j]=tr[j];
> 		
> 		}
> 
> }			
> 
> 
> 
> 
> 
> int main() {
> int n,t1,t2,i,j,k;
> 	while (true) {
> 		scanf("%d%d",&n,&p);
> 		if (!(p+n)) break;
> 		for (i=1;i<=n;++i) {
> 			scanf("%d",&r[i]);
> 			--r[i];
> 		}
> 		memset(mod,0,sizeof(mod));
> 		for (i=1;i<=n;++i) {
> 			scanf("%d",&j);
> 			for (;j>0;--j) {
> 				scanf("%d%d",&t1,&t2);
> 				mod[i][t1-1]=t2;
> 			}
> 			for (j=1;j<i;++j) {
> 				if (mod[i][j-1]==0) continue;
> 				t1=mod[j][j-1];
> 				t2=mod[i][j-1];
> 				r[i]=((r[i]*t1)%p-(r[j]*t2)%p+p)%p;
> 				for (k=j;k<n;++k) 
> 					mod[i][k]=((mod[i][k]*t1)%p-(mod[j][k]*t2)%p+p)%p;
> 			}
> 		}
> 		for (lastm=n;lastm>0;--lastm) {
> 			for (j=lastm-1;j<n;++j)
> 				if (mod[lastm][j]!=0) break;
> 			if (j<n) break;
> 		}
> 		for (lastr=n;lastr>0;--lastr) 
> 			if (r[lastr]!=0) break;	
> 		best=INF;
> 		/*for (i=1;i<=n;++i) {
> 			for (j=0;j<i-1;++j)
> 				printf("    0");
> 			for (j=i-1;j<n;++j)
> 				printf("%5d",mod[i][j]);
> 			printf(" =%5d\n",r[i]);
> 		}
> 		best=0;
> 		for (i=n;i>=1;--i) {
> 			t1=mod[i][i-1];
> 			for (j=0;j<p;++j)
> 				if ((t1*j)%p==r[i]) break;
> 			if (j==p) break;
> 			if ((r[i]=j)>0) ++best;
> 			for (j=1;j<i;++j)
> 				r[j]=(r[j]-r[i]*mod[j][i-1]%p+p)%p;
> 		}*/
> 		if (lastm>=lastr) 
> 			solve(0,n);
> 		if (best==INF) printf("No solution\n");
> 		else 
> 			printf("%d\n",best);
> 		
> 	}
> 	return 0;
> }
> 
> 
> 

• Re:tle (0) gigatron 2005-01-23 18:36:20