Submission #20034

# Submission time Handle Problem Language Result Execution time Memory
20034 2016-02-25T08:46:22 Z hongjun7 로봇 (kriii4_F) C++
Compilation error
0 ms 0 KB
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 1000000007
#define N 33
long long int gcd(long long int x, long long int y)
{
	x = std::abs(x);
	y = std::abs(y);
	if(y==0)return x;
	while(x%y)
	{
		long long int z = x%y;
		x=y;
		y=z;
	}
	return y;
}
class B{
public:
	long long int p, q;
	B(){p=0;q=1;}
	B(long long int x){p=x%M;q=1;gg();}
	B(long long int x, long long int y){p=x%M;q=y%M;gg();}

	void gg()
	{
		if(q<0){q = M+q;}
		if(p<0){p = M+p;}
	}

	B operator +(B &a){
		B r = B(p*a.q + q*a.p, q*a.q);
		return r;
	}
	void operator +=(B &a){
		B r = B(p*a.q + q*a.p, q*a.q);
		p=r.p;
		q=r.q;
	}
	B operator +(long long int a){
		B r = B(p + q*a, q);
		return r;
	}
	B operator -(B &a){
		B r = B(p*a.q - q*a.p, q*a.q);
		return r;
	}
	B operator *(B &a){
		B r = B(p*a.p, q*a.q);
		return r;
	}
	B operator *(long long int a){
		B r = B(p*a, q);
		return r;
	}
	B operator /(B &a){
		B r = B(p*a.q, q*a.p);
		return r;
	}
};
class A{
public:
	B a[N][N];
	A(){for(int i=0;i<N;i++)for(int j=0; j<N; j++) a[i][j] = 0;}
	void iden(){
		for(int i=0;i<N;i++)for(int j=0; j<N; j++) a[i][j] = 0;
		for(int i=0;i<N;i++)a[i][i] = 1;
	}
	A operator *(A &p)
	{
		A r;
		int i, j, k;
		for(i=0; i<N; i++)
		{
			for(j=0;j<N;j++)
			{
				r.a[i][j] = 0;
				for(k=0; k<N; k++)
				{
					r.a[i][j] += (a[i][k] * p.a[k][j]);
				}
			}
		}
		return r;
	}
	A operator -(A &p)
	{
		A r;
		int i, j, k;
		for(i=0; i<N; i++)
		{
			for(j=0;j<N;j++)
			{
				r.a[i][j] = a[i][j] - p.a[i][j];
			}
		}
		return r;
	}
	A operator +(A &p)
	{
		A r;
		int i, j, k;
		for(i=0; i<N; i++)
		{
			for(j=0;j<N;j++)
			{
				r.a[i][j] = a[i][j] + p.a[i][j];
			}
		}
		return r;
	}

	void print()
	{
		for(int i=0; i<N; i++,printf("\n"))
			for(int j=0; j<N; j++)
				printf("%lld/%lld ",a[i][j].p, a[i][j].q);
	}
};
long long int gcd_ext(long long int a,long long int m)
{
    long long int x,y,q,s[100],t[100],i,z;
    s[0]=1;t[0]=0;
    s[1]=0;t[1]=1;
    x=m;y=a;
    for(i=2;y;i++)
    {
        q=x/y;
        s[i]=s[i-2]-q*s[i-1];
        t[i]=t[i-2]-q*t[i-1];
		z=x%y;
		x=y;
		y=z;
    }
    return (t[i-2]+m+m)%m;
}
A exxp(A a,int n)
{
	A r,z;
	int i, j, k;
	r.iden();
	z = a;
	while(n)
	{
		if(n%2)
		{
			r = r*z;
		}
		z = z*z;
		n/=2;
	}
	return r;
}
int main() {
	int i, j, k, l;

	long long int n,ll,mm,rr;
	scanf("%lld %lld %lld %lld",&n,&ll,&mm,&rr);

	B p,q,r;
	p = B(ll, mm+ll+rr);
	q = B(mm, mm+ll+rr);
	r = B(rr, mm+ll+rr);

	A me;
	// a b c d S T   6
	// aa ab ac ad bb bc bd cc cd dd  16
	// aS bS cS dS aT bT cT bT  8
	// E F G 3


	// a b c d
	me.a[0][0] = me.a[1][1] = me.a[2][2] = me.a[3][3] = q;
	me.a[1][0] = me.a[2][1] = me.a[3][2] = me.a[0][3] =	p;
	me.a[3][0] = me.a[0][1] = me.a[1][2] = me.a[2][3] = r;
	// S T
	me.a[4][4] = 1;
	me.a[4][0] = 1; me.a[4][2] = -1;
	me.a[5][5] = 1;
	me.a[5][1] = 1; me.a[5][3] = -1;
	// aa ab ac ad
	for(i=0;i<4;i++)
	{
		for(j=i;j<4;j++)
		{
			int id1, id2;
			if(i<j)
				id1 = i*4+j+6;
			else
				id1 = j*4+i+6;

			for(k=0; k<4; k++)
			{
				for(l=0; l<4; l++)
				{
					if(k<l)
						id2 = k*4+l+6;
					else
						id2 = l*4+k+6;
					me.a[id1][id2] += me.a[j][l] * me.a[i][k];
				}
			}
		}
	}
	//aS bS cS dS
	for(i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			me.a[i+22][j+22] = me.a[i][j];
		}
		for(j=0;j<4;j++)
		{
			int id;
			if(0<j)
				id = 0*4 + j + 6;
			else
				id = j*4 + 0 + 6;
			me.a[i+22][id] += me.a[i][j];
		}
		for(j=0;j<4;j++)
		{
			int id;
			if(2<j)
				id = 2*4 + j + 6;
			else
				id = j*4 + 2 + 6;
			me.a[i+22][id] += (me.a[i][j] * (-1));
		}
	}
	//aT bT cT dT
	for(i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			me.a[i+26][j+26] = me.a[i][j];
		}
		for(j=0;j<4;j++)
		{
			int id;
			if(1<j)
				id = 1*4 + j + 6;
			else
				id = j*4 + 1 + 6;
			me.a[i+26][id] += me.a[i][j];
		}
		for(j=0;j<4;j++)
		{
			int id;
			if(3<j)
				id = 3*4 + j + 6;
			else
				id = j*4 + 3 + 6;
			me.a[i+26][id] += (me.a[i][j] * (-1));
		}
	}
	// E
	me.a[30][30] = 1;
	me.a[30][22] = 2;
	me.a[30][24] = -2;
	me.a[30][0] = 1;
	me.a[30][2] = 1;
	//F
	me.a[31][31] = 1;
	me.a[31][27] = 2;
	me.a[31][29] = -2;
	me.a[31][1] = 1;
	me.a[31][3] = 1;
	//G
	me.a[32][30] = 1;
	me.a[32][31] = 1;

	int ii=n;
	int jj = 32;
	//for(ii=0; ii<=n; ii++)
	{
		A rrr = exxp(me,ii+1);
		{
		B res = ((rrr.a[jj][0]) * q) +((rrr.a[jj][1]) * p) + ((rrr.a[jj][3]) * r)
			+ ((rrr.a[jj][6])*q*q) + ((rrr.a[jj][7])*q*p) + ((rrr.a[jj][9])*q*r)
			+ ((rrr.a[jj][11])*p*p) + ((rrr.a[jj][13])*p*r) + ((rrr.a[jj][21])*r*r)
			;
		//res = rrr.a[32][0] + rrr.a[32][6];
		//printf("%lld / %lld\n",res.p, res.q);

		long long int zz = gcd_ext(res.q, M);
		long long int zzz = (zz * res.p)%M;
		printf("%lld\n",zzz);
		}
	}

}

Compilation message

F.cpp: In member function ‘A A::operator*(A&)’:
F.cpp:81:16: error: no match for ‘operator+=’ (operand types are ‘B’ and ‘B’)
      r.a[i][j] += (a[i][k] * p.a[k][j]);
                ^
F.cpp:81:16: note: candidate is:
F.cpp:36:7: note: void B::operator+=(B&)
  void operator +=(B &a){
       ^
F.cpp:36:7: note:   no known conversion for argument 1 from ‘B’ to ‘B&’
F.cpp: In member function ‘A A::operator-(A&)’:
F.cpp:90:13: warning: unused variable ‘k’ [-Wunused-variable]
   int i, j, k;
             ^
F.cpp: In member function ‘A A::operator+(A&)’:
F.cpp:103:13: warning: unused variable ‘k’ [-Wunused-variable]
   int i, j, k;
             ^
F.cpp: In function ‘A exxp(A, int)’:
F.cpp:141:6: warning: unused variable ‘i’ [-Wunused-variable]
  int i, j, k;
      ^
F.cpp:141:9: warning: unused variable ‘j’ [-Wunused-variable]
  int i, j, k;
         ^
F.cpp:141:12: warning: unused variable ‘k’ [-Wunused-variable]
  int i, j, k;
            ^
F.cpp: In function ‘int main()’:
F.cpp:201:21: error: no match for ‘operator+=’ (operand types are ‘B’ and ‘B’)
      me.a[id1][id2] += me.a[j][l] * me.a[i][k];
                     ^
F.cpp:201:21: note: candidate is:
F.cpp:36:7: note: void B::operator+=(B&)
  void operator +=(B &a){
       ^
F.cpp:36:7: note:   no known conversion for argument 1 from ‘B’ to ‘B&’
F.cpp:229:19: error: no match for ‘operator+=’ (operand types are ‘B’ and ‘B’)
    me.a[i+22][id] += (me.a[i][j] * (-1));
                   ^
F.cpp:229:19: note: candidate is:
F.cpp:36:7: note: void B::operator+=(B&)
  void operator +=(B &a){
       ^
F.cpp:36:7: note:   no known conversion for argument 1 from ‘B’ to ‘B&’
F.cpp:255:19: error: no match for ‘operator+=’ (operand types are ‘B’ and ‘B’)
    me.a[i+26][id] += (me.a[i][j] * (-1));
                   ^
F.cpp:255:19: note: candidate is:
F.cpp:36:7: note: void B::operator+=(B&)
  void operator +=(B &a){
       ^
F.cpp:36:7: note:   no known conversion for argument 1 from ‘B’ to ‘B&’
F.cpp:280:32: error: no match for ‘operator+’ (operand types are ‘B’ and ‘B’)
   B res = ((rrr.a[jj][0]) * q) +((rrr.a[jj][1]) * p) + ((rrr.a[jj][3]) * r)
                                ^
F.cpp:280:32: note: candidates are:
F.cpp:32:4: note: B B::operator+(B&)
  B operator +(B &a){
    ^
F.cpp:32:4: note:   no known conversion for argument 1 from ‘B’ to ‘B&’
F.cpp:41:4: note: B B::operator+(long long int)
  B operator +(long long int a){
    ^
F.cpp:41:4: note:   no known conversion for argument 1 from ‘B’ to ‘long long int’
In file included from /usr/include/c++/4.9/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/4.9/algorithm:61,
                 from F.cpp:2:
/usr/include/c++/4.9/bits/stl_iterator.h:334:5: note: template<class _Iterator> std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)
     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
     ^
/usr/include/c++/4.9/bits/stl_iterator.h:334:5: note:   template argument deduction/substitution failed:
F.cpp:280:52: note:   ‘B’ is not derived from ‘const std::reverse_iterator<_Iterator>’
   B res = ((rrr.a[jj][0]) * q) +((rrr.a[jj][1]) * p) + ((rrr.a[jj][3]) * r)
                                                    ^
F.cpp:159:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld",&n,&ll,&mm,&rr);
                                             ^