結果
問題 |
No.389 ロジックパズルの組み合わせ
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }