HDU-4599

solution

已 知   d p i [ n ] = 0 , ( i = 1 , 2 ) 已知~dp_i[n]=0,(i=1,2) 已知 dpi​[n]=0,(i=1,2)

d p 1 [ i ] = d p 1 [ i + 1 ] ∗ 5 6 + d p 1 [ 1 ] ∗ 1 6 + 1 dp_1[i]=dp_1[i+1]*\frac56+dp_1[1]*\frac16+1 dp1​[i]=dp1​[i+1]∗65​+dp1​[1]∗61​+1

= > d p 1 [ n ] − ( d p 1 [ 1 ] + 5 6 ) = 6 [ d p 1 [ n − 1 ] − ( d p 1 [ 1 ] + 5 6 ) ] ， d p 1 [ 0 ] = d p 1 [ 1 ] + 1 =>dp_1[n]-(dp_1[1]+\frac56)=6[dp_1[n-1]-(dp_1[1]+\frac56)]，dp_1[0]=dp_1[1]+1 =>dp1​[n]−(dp1​[1]+65​)=6[dp1​[n−1]−(dp1​[1]+65​)]，dp1​[0]=dp1​[1]+1

= > d p 1 [ n ] − d p 1 [ 1 ] − 6 5 = − 6 n 5 =>dp_1[n]-dp_1[1]-\frac65=-\frac{6^n}{5} =>dp1​[n]−dp1​[1]−56​=−56n​

= > d p 1 [ 1 ] + 6 5 = 6 n 5 = > d p 1 [ 0 ] = 6 n − 1 5 =>dp_1[1]+\frac65=\frac{6^n}{5}=>dp_1[0]=\frac{6^n-1}5 =>dp1​[1]+56​=56n​=>dp1​[0]=56n−1​

同理，

d p 2 [ 0 ] = 6 ∗ 6 n − 1 5 dp_2[0]=6*\frac{6^n-1}5 dp2​[0]=6∗56n−1​

显 然 G ( n ) = 6 ∗ n 显然G(n)=6*n 显然G(n)=6∗n

求 最 小 的 M 1 , M 2 使 得 ， G ( M 1 ) > = F ( N ) ， G ( M 2 ) > = H ( N ) ， 求最小的M_1,M_2使得，G (M_1) >= F (N)，G(M_2)>=H(N)， 求最小的M1​,M2​使得，G(M1​)>=F(N)，G(M2​)>=H(N)，

其 中 F ( N ) = d p 1 [ 0 ] ， H ( N ) = d p 2 [ 0 ] . 其中F(N)=dp_1[0]，H(N)=dp_2[0]. 其中F(N)=dp1​[0]，H(N)=dp2​[0].

于是有，

M 1 > = c e i l ( 6 n − 1 30 ) = 6 n + 24 30 ， M 2 > = 6 n − 1 5 M_1>=ceil(\frac{6^n-1}{30})=\frac{6^n+24}{30}，M_2>=\frac{6^n-1}5 M1​>=ceil(306n−1​)=306n+24​，M2​>=56n−1​

code

/*Siberian Squirrel*/
/*Cute JinFish*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1), eps = 1e-6;
/*const int MOD = 998244353, r = 119, k = 23, g = 3;
const int MOD = 1004535809, r = 479, k = 21, g = 3;*/
const int INF = 0x3f3f3f3f, MOD = 2011;
const int M = 3e2 + 10, N = 5e6 + 10;
int sgn(double x) {
    if(fabs(x) < eps) return 0;
    return x < 0? -1: 1;
}
//inline int rnd(){static int seed=2333;return seed=(((seed*666666ll+20050818)%998244353)^1000000007)%1004535809;}
//double Rand() {return (double)rand() / RAND_MAX;}

ll n;

ll quick_pow(ll ans, ll p, ll res = 1) {
    ans %= MOD, p %= MOD - 1;
    for(; p; p >>= 1, ans = ans * ans % MOD)
        if(p & 1) res = res * ans % MOD;
    return res % MOD;
}

ll inv(ll ans) {
    return quick_pow(ans, MOD - 2);
}

void init() {}

void solve(double _p = 0) {
    cout << ((quick_pow(6, n) + 24 + MOD) % MOD * inv(30) % MOD) << ' ';
    cout << (quick_pow(6, n) - 1 + MOD) % MOD * inv(5) % MOD << endl;
}
/*


*/
int main() {
//    ios::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
// srand(time(0));
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    init();
    int o = 1;
//	cin >> o;
    while(o --) {
        while(cin >> n && n) {
            solve();
        }
    }
    return 0;
}