Background

dts的一个脑洞

Description

甲，乙，丙传球，持球者可以将球传给除自己外的任何人，一开始（第0次），球在甲手上，问传了n次后，球在甲手上有多少种方案以及球不在甲手上又有多少种方案。
设方案数ans，请回答ans*t对k取模的结果，t,k将在输入中给出，数据保证k是一个质数。

Format

Input

输入包含多组数据，请处理到文件结束
每组数据1行，包含n,t,k三个数

Output

对于每组数据，输出一行二个数，球在甲手上方案数的t倍对k取模的结果以及球不在甲手上方案数的t倍对k取模的结果

Sample 1

Input

5 1 10007
10 1 6888641
25 1234343 26512489
100 1 35832829
1000000 1 1070335969
2342342 5 25366529
48101980551053313 3 140164417
7115613354243901 65653907200776721 199185089
127309524378807937 163807646567825547 934302401
2428747171408701 528447189038130055 121531577

Output

10 22
342 682
17020371 9996939
33466184 31099537
508273138 1016546274
3741878 7483746
100615353 61066295
148887812 102723208
101454550 57968686
41646825 115331836

Limitation

1s, 4194304KiB for each test case.

Hint

每组输入不超过10^5组数据
对于100%的数据，每组n,t,k满足，n≤2^60,t≤2^60,k≤2^30

C++ Code

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    ll n,t,key;
    
    ll qp(ll x,ll y,ll key)
    {
        ll ans=1;
        for (ll i=x,j=y;j>0;i=(i*i)%key,j/=2)
            if (j&1)
                ans=(ans*i)%key;
        return ans;
    }
    
    ll ny(ll x,ll key)
    {
        if (x==1)
            return 1;
        else
            return -(key/x)*ny(key%x,key)%key;
    }
    
    void main()
    {
        while (~scanf("%lld%lld%lld",&n,&t,&key))
        {
            ll p=ny(3,key);
            if (p<0)
                p+=((key-p)/key)*key;
            ll f=qp(2,n,key)+2*((n&1)?-1:1),g=2*qp(2,n,key)-2*((n&1)?-1:1);
            if (f<0)
                f+=((key-f)/key)*key;
            if (g<0)
                g+=((key-g)/key)*key;
            f=(f*p)%key,g=(g*p)%key;
            //f(x)=(1/3)*2^x+(2/3)*(-1)^x
            //g(x)=(2/3)*2^x-(2/3)*(-1)^x
            t%=key;
            printf("%lld %lld\n",(f*t)%key,(g*t)%key);
        }
    }
};

int main()
{
    dts::main();
}

Source

Vijos Original