結果

問題 No.2709 1975 Powers
ユーザー えらーめぐえらーめぐ
提出日時 2024-03-31 14:53:37
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 870 ms / 2,000 ms
コード長 1,294 bytes
コンパイル時間 3,488 ms
コンパイル使用メモリ 263,976 KB
実行使用メモリ 363,264 KB
最終ジャッジ日時 2024-03-31 14:53:54
合計ジャッジ時間 15,180 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 257 ms
110,464 KB
testcase_03 AC 431 ms
181,376 KB
testcase_04 AC 736 ms
306,304 KB
testcase_05 AC 581 ms
242,944 KB
testcase_06 AC 182 ms
78,464 KB
testcase_07 AC 77 ms
36,864 KB
testcase_08 AC 543 ms
228,224 KB
testcase_09 AC 642 ms
267,648 KB
testcase_10 AC 83 ms
38,912 KB
testcase_11 AC 122 ms
53,888 KB
testcase_12 AC 433 ms
184,192 KB
testcase_13 AC 786 ms
327,680 KB
testcase_14 AC 239 ms
101,632 KB
testcase_15 AC 519 ms
218,496 KB
testcase_16 AC 333 ms
139,648 KB
testcase_17 AC 95 ms
42,368 KB
testcase_18 AC 455 ms
191,872 KB
testcase_19 AC 651 ms
273,792 KB
testcase_20 AC 241 ms
102,272 KB
testcase_21 AC 542 ms
226,432 KB
testcase_22 AC 870 ms
363,264 KB
testcase_23 AC 690 ms
290,560 KB
testcase_24 AC 403 ms
169,216 KB
testcase_25 AC 663 ms
278,400 KB
testcase_26 AC 745 ms
310,656 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