Xét một số nguyên có đúng N chữ số trong hệ cơ số K. Số đó được gọi là bình thường nếu trong hệ cơ số K, số đó không có hai chữ số 0 liên tiếp. Vi dụ: 1010230

Question

Xét một số nguyên có đúng N chữ số trong hệ cơ số K. Số đó được gọi là bình thường nếu trong hệ cơ số K, số đó không có hai chữ số 0 liên tiếp. Vi dụ: 1010230 là một số bình thường trong hệ cơ số 7. 1000198 là không phải một số trong hệ cơ số 7. 0001235 là một số bình thường có 4 chữ số trong hệ cơ số 7. Cho ba số nguyên N, K, M, hãy tính phần dư khi chia số lượng số bình thường có N chữ số trong hệ cơ số K cho M. Dữ liệu Gồm ba dòng Dòng thứ nhất chứa số nguyên N Dòng thứ hai chứa số nguyên K. Dòng thứ ba là số nguyên M. Cả ba số đều được biểu diễn trong hệ cơ số 10
.Kết quả Một dòng duy nhất chứa kết quả của bài toán (trong hệ cơ số 10).
2<=m,n,k<=1e18
input `:` 2 10 100 
output `:` 90

tranminhduc8902 · Answer

\begin{array}{c} \color{#FFFFFFff}{F}\color{#D0E4FFff}{u}\color{#A4C8FFff}{r}\color{#78ACFFff}{i}\color{#4C90FFff}{n}\color{#2064FFff}{a} \color{#0040A4ff}{F}\color{#2064FFff}{o}\color{#4C90FFff}{r}\color{#78ACFFff}{c}\color{#A4C8FFff}{a}\color{#D0E4FFff}{l}\color{#FFFFFFff}{o}\color{#D0E4FFff}{s} \end{array}
/**
 *  author:  furinaforcalos
 *  created:  10.05.2025
**/
#include 
#define hutao long long
using namespace std;
hutao n,m,k,dp[1000006];
hutao nhan(hutao a,hutao b)
{
    a%=m, b%=m;
    hutao q=(long double)a*b/m;
    return (a*b-q*m)%m;
}
struct heso
{
    vector> dp;
    hutao row() const {return dp.size();}
    hutao col() const {return dp[0].size();}
    auto & operator [] (hutao i) {return dp[i];}
    const auto & operator[] (hutao i) const {return dp[i]; }
    heso()=default;
    heso(hutao r, hutao c): dp(r, vector(c)){}
    heso(const vector>&d): dp(d)
    {
        assert(d.size());
        hutao size=d[0].size();
        assert(size);
        for(auto x:d) assert(x.size()==size);
    }
    static heso identity(hutao n){
        heso a=heso(n,n);
        while(n--) a[n][n]=1;
        return a;
    }
    heso operator *(const heso &b)
    {
        heso a=*this;
        assert(a.col()==b.row());
        heso c(a.row(),b.col());
        for(hutao i=0; i0; exp >>= 1, base=(base*base)){
            if(exp&1) ans=(ans*base);
        }
        return ans;
    }
};
int main(){
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    cin>>n>>k>>m;
    heso a(1,2);
    a.dp={{(k-1)%m,1}};
    heso b(2,2);
    b.dp = {
        {(k-1)%m,1},
        {(k-1)%m,0}
    };
    b=b^(n-1);
    a=a*b;
    cout

tuandung16 · Answer

`\color{#1AD5F7}{⋆⟡D}\color{#1AD5F7}{r}\color{#4DA6E6}{a}\color{#668EDD}{g}\color{#8077D5}{o}\color{#995FCD}{n}\color{#EA2F90}{⟡⋆}`

#include
#define ll long long
using namespace std;
ll n,hk,m;
ll mul(ll a,ll b){
    ll r=0; a%=m;
    while(b){
        if(b&1) r=(r+a)%m;
        a=(a+a)%m; b/=2;
    }
    return r;
}
ll check(ll n){
    if(n==1) return hk-1;
    if(n==2) return mul(hk-1, hk);
    ll a=1,b=0,c=0,d=1,x=1,y=0,z=0,t=1;
    n -= 2;
    while(n){
        if(n&1){
            ll aa=mul(a,x)+mul(b,z), bb=mul(a,y)+mul(b,t);
            ll cc=mul(c,x)+mul(d,z), dd=mul(c,y)+mul(d,t);
            a=aa%m; b=bb%m; c=cc%m; d=dd%m;
        }
        ll xx=mul(x,x)+mul(y,z), yy=mul(x,y)+mul(y,t);
        ll zz=mul(z,x)+mul(t,z), tt=mul(z,y)+mul(t,t);
        x=xx%m; y=yy%m; z=zz%m; t=tt%m;
        n /= 2;
    }
    return (mul(a, mul(hk-1,hk)) + mul(b, mul(hk-1,hk))) % m;
}
int main(){
    cin>>n>>hk>>m;
    cout

TRẢ LỜI

Bạn muốn hỏi điều gì?

Tham Gia Group 2K10 Ôn Thi Vào Lớp 10 Miễn Phí

Bạn muốn hỏi điều gì?

Tìm kiếm với hình ảnh

Hãy đăng nhập hoặc tạo tài khoản miễn phí!

Lưu vào

TRẢ LỜI

Bạn muốn hỏi điều gì?

Tham Gia Group 2K10 Ôn Thi Vào Lớp 10 Miễn Phí

Bạn muốn hỏi điều gì?

Lý do báo cáo vi phạm?