結果

問題 No.1581 Multiple Sequence
ユーザー riano
提出日時 2021-07-24 19:42:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 924 bytes
コンパイル時間 1,798 ms
コンパイル使用メモリ 178,536 KB
実行使用メモリ 78,880 KB
最終ジャッジ日時 2024-07-20 02:01:32
合計ジャッジ時間 5,466 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define Pr pair<ll,ll>
#define Tp tuple<ll,ll,ll>
using Graph = vector<vector<int>>;

const ll mod = 1000000007;

map<Pr,ll> memo;
ll search(ll m,ll sum,vector<vector<ll>> &div){
    if(sum<0) return 0;
    if(sum==0) return 1;
    Pr p = make_pair(m,sum);
    if(memo.count(p)) return memo[p];
    ll cnt = 0;
    for(ll x:div[m]){
        cnt += search(x,sum-x,div);
    }
    memo[p] = cnt;
    //cout << m << " " << sum << " " << cnt << endl;
    return cnt;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll M; cin >> M;
    vector<vector<ll>> div(M+1);
    for(ll i=1;i<=M;i++){
        for(ll j=i;j<=M;j+=i){
            div[j].push_back(i);
        }
    }
    ll ans = 0;
    for(ll i=1;i<=M;i++){
        ans += search(i,M-i,div);
    }
    cout << ans << endl;
}
0