結果

問題 No.2709 1975 Powers
ユーザー えらーめぐえらーめぐ
提出日時 2024-03-31 14:53:37
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 255 ms
110,336 KB
testcase_03 AC 423 ms
181,248 KB
testcase_04 AC 720 ms
306,176 KB
testcase_05 AC 577 ms
242,816 KB
testcase_06 AC 179 ms
78,464 KB
testcase_07 AC 75 ms
36,736 KB
testcase_08 AC 535 ms
228,224 KB
testcase_09 AC 632 ms
267,520 KB
testcase_10 AC 77 ms
38,912 KB
testcase_11 AC 117 ms
53,760 KB
testcase_12 AC 428 ms
184,064 KB
testcase_13 AC 776 ms
327,552 KB
testcase_14 AC 231 ms
101,504 KB
testcase_15 AC 509 ms
218,368 KB
testcase_16 AC 326 ms
139,520 KB
testcase_17 AC 87 ms
42,368 KB
testcase_18 AC 446 ms
191,744 KB
testcase_19 AC 644 ms
273,664 KB
testcase_20 AC 233 ms
102,144 KB
testcase_21 AC 531 ms
226,304 KB
testcase_22 AC 861 ms
363,136 KB
testcase_23 AC 686 ms
290,432 KB
testcase_24 AC 398 ms
169,088 KB
testcase_25 AC 658 ms
278,272 KB
testcase_26 AC 735 ms
310,784 KB
権限があれば一括ダウンロードができます

ソースコード

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