結果

問題 No.2709 1975 Powers
ユーザー えらーめぐえらーめぐ
提出日時 2024-03-31 14:53:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 861 ms / 2,000 ms
コード長 1,294 bytes
コンパイル時間 3,092 ms
コンパイル使用メモリ 263,868 KB
実行使用メモリ 363,136 KB
最終ジャッジ日時 2024-09-30 20:04:26
合計ジャッジ時間 15,354 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < n;i++)


long long modpow(long long a,long long n,long long m){//aのn乗(mod m)
    long long res = 1;
    while(n>0){
        if(n&1){//みてる桁のビットが立ってるか
            res = res*a%m;}
        a = a*a%m;//つぎの
        n>>=1;//けたに
    }
    return res;
}



#define all(x) x.begin(),x.end()


int main(){
    #define int long long
    int N,P,Q;cin >> N >> P >> Q;
    vector<int>A(N);
    rep(i,N)cin >> A[i];
    sort(all(A));
    A.erase(unique(all(A)),A.end());

    //10のAi乗の余りはいくつ、9の、…
    vector<int>_10(N),_9(N),_7(N),_5(N);
    rep(i,N){
        _10[i] = modpow(10,A[i],P);
        _9[i] = modpow(9,A[i],P);
        _7[i] = modpow(7,A[i],P);
        _5[i] = modpow(5,A[i],P);
    }
    vector dp(N+1,vector(5,vector(P,0)));//i番目までで、10まで、9まで…選んであって余りがkになる方法

    rep(i,N){//添え字はi+1
        dp[i+1] = dp[i];
        dp[i+1][0][_10[i]] += 1;
        rep(p,P){//前の余りがpだった
            dp[i+1][1][(p+_9[i])%P]+=dp[i][0][p];
            dp[i+1][2][(p+_7[i])%P]+=dp[i][1][p];
            dp[i+1][3][(p+_5[i])%P]+=dp[i][2][p];
        }
    }

    cout << dp[N][3][Q] << endl;
}
0