今日の反省会場

AtCoder Beginner Contest 110
unratedだったとして喜んでいいのか

どうして2完なの?

C

S→Tが全射と決め打ってWA。心折られる。というか全単射の証明難しくないか。

D

前日のコドフェスCの想定解がDPだったことから、数え上げ→DPのイメージが出来上がる。はじめ非DP解で重複組み合わせまで行くも、前日の考察経路に重複組み合わせがあったためDP解に切り替える。遷移式まで出すも計算量がまずい。そうこうしてたら終わり。

DのDP解は結局どうなりましたか?¹

dp[ ][ ]:=左から番目まで見て、積が

とやるのは で流石に無理なので…。について考えると、結果に影響するのはがの約数のとき。（数列にの約数しか出てこないしね）これを考慮すると座圧チックなことができて、

dp[ ][ ]:=左から番目まで見て、積がの約数の小さいほうから番目

に直せる。このとき の実装は思いつくのでざっと計算してみる。 約数の個数が大きそうな数でパッと思い浮かぶのが、 で個。オーダーは間違いなさそうなので大体 回…ICPCなら間に合うんじゃね

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int prime_factorization(int n){
    int ret=1;
    int i=2,cnt=1;
    while(n>1){
        if(n%i==0){
            n/=i;
            cnt++;
        }else{
            ret*=cnt;
            cnt=1;
            i++;
        }
    }
    ret*=cnt;
    return ret;
}

int dp[100000][2500];

int main(){
    int n,m; cin>>n>>m;
    // 座圧みたいな
    int nn=prime_factorization(m);
    map<int,int> mp;
    int cnt=0; for(int i=1;i*i<=m;i++)if(m%i==0){mp[cnt]=i,mp[nn-1-cnt]=m/i,cnt++;};
    // dp[i][j]:=i番目まで見て積がmの約数でj番目になる個数
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<nn;j++){
            for(int k=0;k<=j;k++){
                if(mp[j]%mp[k]==0) dp[i][j]+=dp[i-1][k]%MOD;
                dp[i][j]%=MOD;
            }
        }
    }
    cout<<dp[n][nn-1]<<endl;
    return 0;
}

---

1. 解答漁ってたらdp[10^5][32]の解があるらしい。解読次第追記↩