Background

dts的一个更大的脑洞

Description

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

Format

Input

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

Output

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

Sample 1

Input

5 3 1 10007
10 7 1 6888641
25 12 1234343 26512489
100 12343 1 35832829
1000000 1000000 1 1070335969
2342342 238452872 5 25366529
48101980551053313 238746273842 3 140164417
7115613354243901 28762387598769 65653907200776721 199185089
127309524378807937 127309524378807937 163807646567825547 934302401
2428747171408701 7623859 528447189038130055 121531577

Output

10 22
1749385 3607663
20439797 26315628
14956741 21182901
204135301 619857020
2297661 15017171
90669161 103081460
156124501 2330733
591804344 650055121
30608897 86002609

Limitation

1s, 4194304KiB for each test case.

Hint

每组输入不超过10^5组数据
对于100%的数据，每组n,m,t,k满足，n≤2^60,m≤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,m,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%lld",&n,&m,&t,&key))
        {
            m%=key;
            ll p=ny(m,key);
            if (p<0)
                p+=((key-p)/key)*key;
            ll f=qp(m-1,n,key)+(m-1)*((n&1)?-1:1),g=(m-1)*qp(m-1,n,key)+(1-m)*((n&1)?-1:1);
            if (f<0)
                f+=((key-f)/key)*key;
            if (g<0)
                g+=((key-g)/key)*key;
            f=((f%key)*p)%key,g=((g%key)*p)%key;
            //f(x)=(m-1)^x/m+(m-1)*(-1)^x/m
            //g(x)=(m-1)*(m-1)^x/m+(1-m)*(-1)^x/m
            t%=key;
            printf("%lld %lld\n",(f*t)%key,(g*t)%key);
        }
    }
};

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

Source

Vijos Original