結果

問題 No.389 ロジックパズルの組み合わせ
コンテスト
ユーザー 6v8
提出日時 2016-07-09 04:50:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,388 bytes
コンパイル時間 1,187 ms
コンパイル使用メモリ 110,636 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-10-13 08:06:32
合計ジャッジ時間 5,023 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 1 -- * 89
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <sstream> //string stream its useful!
#include<string>
#include<iostream>
#include<utility> //pair
#include <vector> // vector
#include <algorithm>    // swap,sort,binary_search
#include <functional>   // std::greater
#include <map> //map
#include<set> //set
#include<queue> //queue
#include<list> //list
#include<cmath>
#include<numeric>
#include<cassert>
#include <iomanip> //cout<<setprecision


typedef long long ll;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

using namespace std;
void omajinai() {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(15);
    //freopen("txt.csv","r",stdin);
}

const ll W = 1000000007LL;

map<pair<int,long>,ll> memo;

long g(int t){
    long x = 1;
    for(int i = 0 ; i<t;i++){x*=10;}
    return x;
}


ll kake(ll a, long k){
    if(a<k) return kake(k,a);
    ll ans = 0;
    vector<bool> b;
    b.push_back(k%2);
    while(k!=0){k>>=1; b.push_back(k%2);}
    reverse(b.begin(), b.end());
    for(auto i = b.begin();i!=b.end();i++){
        ans+=*i * a; ans%=W; ans<<=1;
    }
    ans>>=1;
    return ans;
}


ll getans(long m,vector<long> v , int cursor){
    long mysum = accumulate(v.begin(),v.end(), 0L)  + v.size() - 1 ;
    if(mysum == 0 ) return 1;
    if(mysum == m) return 1;
    if(mysum > m) return 0;
    long t = m - (accumulate(v.begin(),v.end(), 0L) + v.size() -1 ) + 1 + v.size() -1 ;
    long s = v.size();
    vector<long> ansl(s);
    for(int i = 0 ; i<s;i++){
        ansl[i] = t-i;
    }
    vector<int> l(s+1,0);
    
    for(long i = 1; i<=s;i++){
        long k = i;
        for(long j = 2; j<=sqrt(s);j++){
            while(k%j == 0) k/=j,l[j]++;
        }
        l[k]++;
    }
    
    for(long i = 1; i<=s;i++){
        while(l[i]>0){
            l[i]--;
            for(int  j = 0 ; j<s;j++){
                if(ansl[j]%i == 0){ansl[j]/=i; break;}
                assert(j!=s-1);
            }
        }
    }
    
    
    return accumulate(ansl.begin(),ansl.end(),1LL,[](ll sum , long k)->ll{return kake(sum,k);})%W;
}

           
int main(){
    omajinai();
    long m; cin>>m;
    cin.ignore();
    vector<long> v;
    string s;
    getline(cin,s);
    stringstream x(s);
    long t;
    while(x>>t){v.push_back(t);}
    string myans = to_string(getans(m,v,0));
    if(myans == "0") myans = "NA";
    cout<<myans<<endl;
    
    
}
0