#include<iostream>
#include<string>
#include<memory.h>
using namespace std;
bool mod(string s)
{
    return (s[s.length()-1]-'0')%2;	
}
void div(string &s)
{
    int remain=0;
	for(int i=0;i<s.length();i++)
	{
	    int sum=remain*10+s[i]-'0';	
	    string ss="";char c=(sum/2+'0');
	    s[i]=c;
	    remain=sum%2;
	}	
}
bool zero(string s)
{
    if(s.find_first_not_of('0')==-1)return 1;
	return 0;	
}int vv[32];
long long aa[17][17],ans[17][17];
int v,m;
void xmu(long long a[][17],long long b[][17])
{
	long long c[17][17];
	memset(c,0,sizeof(c));
	for(long long i=0;i<=m+1;i++)
	for(long long j=0;j<=m+1;j++)
	for(long long k=0;k<=m+1;k++)
	c[i][j]=(c[i][j]+a[i][k]*b[k][j]%99991)%99991;
	memcpy(a,c,sizeof(c));
}
int main()
{
     freopen("0.txt","r",stdin);
	 freopen("1.txt","w",stdout);
	 int a,b,i,j;string s;
	 while(cin>>v>>m>>s&&v)
	 {
		 memset(vv,0,sizeof(vv));
	     for(i=1;i<v;i++)
	     {
		     cin>>a>>b;
			 vv[a]++; 		
		 }
		 int res[17];
		 memset(res,0,sizeof(res));
		 for(i=0;i<v;i++)
		 if(vv[i]<=m)res[vv[i]]++;
		 else res[m+1]++;
		 
		 for(i=0;i<=m+1;i++)
		 for(j=0;j<=m+1;j++)
		 if(i==j)ans[i][j]=1;
		 else ans[i][j]=0;
		 memset(aa,0,sizeof(aa));
		 for(i=0;i<=m;i++)
		     aa[i][i+1]=aa[i][0]=1;	
		 aa[m+1][m+1]=1;	
		 
		 for(;!zero(s);div(s),xmu(aa,aa))
		 if(mod(s)){
			 	xmu(ans,aa);
		 }
		 long long sum=0;
		/* for(i=0;i<=m+1;i++)cout<<res[i]<<" ";cout<<endl;
		 for(i=0;i<=m+1;i++)
		 {
		     for(j=0;j<=m+1;j++)
		     cout<<ans[i][j]<<" ";cout<<endl;
		 }
		 */
		 for(i=0;i<=m+1;i++)
		 {
		     for(j=0;j<=m+1;j++)
			     sum=(sum+res[j]*ans[j][i])%99991;		
		 }
		 cout<<sum<<endl;		
	 }
}

• 学习了,谢谢分享 (0) twilight 2009-09-13 22:42:36