Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### I_love_penny's blog

By I_love_penny, history, 6 years ago, In this problem you are given "x" amount of money in currency "s" and you want to maximise the amount in "m" steps to currency "f". cost matrix is given for transfer rate. Sounds similar to finding number of ways to reach from one node to another in k steps. So the answer to problem is (s,f) value of mth power of given cost matrix (exchange rate matrix). we need to modify matrix multiplication accordingly to get maximum cost.

code

But we want ans%mod , this mod will ruin my multiplication of matrix. I will not get maximum. Editorial suggest to use power of primes , can someone please explain that.  Comments (2)
 » Multiplying values will result into overflow , since you have to multiply values up to 10^9 times. And, if you perform modulo operation within matrix expo, the properties of max value will no more be valid. So, simplest way to solve this problem is by representation of integer number in the form of prime factorization. As the largest value in the given input will be 10, so every integers can easily represented using prime factorization of 2,3,5,7 and the largest values obtained after several multiplication will ultimately bounded to these prime factorization. So, we can store power of 2,3,5,7 as a single entry of base matrix and perform matrix expo accordingly. Now, the task is to compare after multiplication of two integers with another one. This task can be done by converting the prime factorization representation value into LOG value and doing comparison accordingly. Since, the largest integer number has greater LOG value. Want to see code?///==================================================/// /// HELLO WORLD !! /// /// IT'S ME /// /// BISHAL GAUTAM /// /// [ [email protected] ] /// ///==================================================/// #include #define X first #define Y second #define mpp make_pair #define nl printf("\n") #define SZ(x) (int)(x.size()) #define pb(x) push_back(x) #define pii pair #define pll pair ///--------------------- #define S(a) scanf("%d",&a) #define P(a) printf("%d",a) #define SL(a) scanf("%lld",&a) #define S2(a,b) scanf("%d%d",&a,&b) #define SL2(a,b) scanf("%lld%lld",&a,&b) ///------------------------------------ #define all(v) v.begin(),v.end() #define CLR(a) memset(a,0,sizeof(a)) #define SET(a) memset(a,-1,sizeof(a)) #define fr(i,a,n) for(int i=a;i<=n;i++) using namespace std; typedef long long ll; ///==========CONSTANTS=============/// /// Digit 0123456789012345678 /// #define MX 200005 #define inf 100000000 #define MD 1000000007LL #define eps 1e-9 ///===============================/// template T BigMod(T b,T p,T m) { T r=1; while(p) { if(p&1)r=(r*b)%m; b=(b*b)%m; p>>=1; } return r; } #define N 21 int ms;///Matrix Size GLOBAL: N struct data { ll n2,n3,n5,n7; data() { n2=0,n3=0,n5=0,n7=0; }; data(ll a,ll b,ll c,ll d) { n2=a,n3=b,n5=c,n7=d; } }; struct mat { data m[N][N]; mat() {}; void unify( ) { for(int i=0; ilg ) return a; else return b; } data Multi(data a,data b) { return data(a.n2+b.n2,a.n3+b.n3,a.n5+b.n5,a.n7+b.n7); } data MakeData(int n) { if(n==0) return data(-1,-1,-1,-1); data ret; while(n%2==0)ret.n2++,n/=2; while(n%3==0)ret.n3++,n/=3; while(n%5==0)ret.n5++,n/=5; while(n%7==0)ret.n7++,n/=7; return ret; } void Print(data ret) { cout<>= 1; } } int main() { int tc,n,cs=1,i,x,p,s,f,j,k,L; S(n); S(p); S2(s,f); S(L); ms=n; fr(i,0,ms-1) { fr(j,0,ms-1) { S(x); b.m[i][j]=MakeData(x); } } Matex(L); ll ans=p; data rs=ret.m[s][f]; ans=(ans*BigMod(2LL,rs.n2,MD))%MD; ans=(ans*BigMod(3LL,rs.n3,MD))%MD; ans=(ans*BigMod(5LL,rs.n5,MD))%MD; ans=(ans*BigMod(7LL,rs.n7,MD))%MD; printf("%lld\n",ans); return 0; }