結果

問題 No.2709 1975 Powers
コンテスト
ユーザー mitani
提出日時 2024-03-31 14:04:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,171 bytes
コンパイル時間 3,334 ms
コンパイル使用メモリ 232,576 KB
実行使用メモリ 217,840 KB
最終ジャッジ日時 2024-09-30 18:55:36
合計ジャッジ時間 6,750 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'll pow_mod(ll, ll)':
main.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(x) x.begin(), x.end()
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#include <atcoder/all>
using namespace atcoder;
//using mint=static_modint<998244353>;
using mint=static_modint<1000000007>;

ll mod;

ll pow_mod(ll n,ll k){
    if(k==0)return 1;
    if(k%2==1)return pow_mod(n,k-1)*n%mod;
    if(k%2==0){
        ll t=pow_mod(n,k/2);
        return t*t%mod;
    }
}

int main(){
	ll n,p,q;cin>>n>>p>>q;
    mod=p;
    vector<ll> a(n);
    rep(i,n)cin>>a[i];
    sort(all(a));


    ll dp[n+1][5][p];
    rep(i,n+1)rep(j,5)rep(k,p)dp[i][j][k]=0;
    dp[0][0][0]=1;

    rep(i,n){
        rep(j,5){
            if(j==4)continue;
            rep(k,p){
                dp[i+1][j][k]+=dp[i][j][k];
                if(j==0)dp[i+1][j+1][(k+pow_mod(10,a[i]))%p]+=dp[i][j][k];
                if(j==1)dp[i+1][j+1][(k+pow_mod(9,a[i]))%p]+=dp[i][j][k];
                if(j==2)dp[i+1][j+1][(k+pow_mod(7,a[i]))%p]+=dp[i][j][k];
                if(j==3)dp[i+1][j+1][(k+pow_mod(5,a[i]))%p]+=dp[i][j][k];
            }
        }
    }

    cout<<dp[n][4][q]<<endl;
}
0