2017-12-22 126 views
6

शीर्षक यह सब कहते हैं।तरीके की संख्या लिखने के लिए एन प्रत्येक भाग पर प्रतिबंध के साथ कश्मीर की संख्या का योग के रूप में

मैं कहाँ प्रत्येक भाग कश्मीर मैं = k मैं < = r मैं दिया सरणी r के लिए की सीमा में होना चाहिए nk हिस्से की राशि के रूप में विभाजित करने के लिए की जरूरत है।

उदाहरण के लिए

-

n = 4, k = 3 and r = [2, 2, 1] 
ans = 2 
#[2, 1, 1], [1, 2, 1] 

आदेश मायने रखती है। (2, 1, 1) और (1, 2, 1) अलग हैं।

मैंने सितारों और बार विधि का उपयोग करके इसे हल करने के बारे में सिखाया, लेकिन ऊपरी बाउंड आर i के कारण होने के कारण मैं इसे संपर्क करने के लिए नहीं जानता।

मैं एक सीधा प्रत्यावर्तन समारोह लागू किया और यह केवल छोटे मानों के लिए ठीक काम करता है।

मूल समस्या का प्रतिबन्ध हैं

1 <= n <= 107

1 <= k <= 105

1 <= ri<= 51

सभी गणना प्रधानमंत्री Modulo के तहत किया जाएगा।

मैं यहाँ एक ऐसी ही समस्या पाया, लेकिन मैं कैसे इस कार्यक्रम में लागू करने के लिए पता नहीं है। HERE

मेरे जानवर बल पुनरावर्ती क्रिया - गणना के परिणाम के भंडारण के लिए एक नक्शा का उपयोग करने का

#define MAX 1000 
const int md = 1e9 + 7; 

vector <int> k; 
vector <map<int, int>> mapper; 

vector <int> hold; 

int solve(int sum, int cur){ 

    if(cur == (k.size() - 1) && sum >= 1 && sum <= k[cur]) return 1; 
    if(cur == (k.size() - 1) && (sum < 1 || sum > k[cur])) return 0; 

    if(mapper[cur].find(sum) != mapper[cur].end()) 
     return mapper[cur][sum]; 

    int ans = 0; 
    int start = 1; 

    for(int i=start; i<=k[cur]; ++i){ 


     int remain = sum - i; 
     int seg = (k.size() - cur) - 1; 
     if(remain < seg) break; 

     int res = solve(sum - i, cur + 1); 
     ans = (1LL * ans + res) % md; 
    } 

    mapper[cur][sum] = ans; 
    return ans; 
} 


int main(){ 

    for(int i=0; i<MAX; ++i) k.push_back(51); // restriction for each part default 51 
    mapper.resize(MAX); 

    cout << solve(MAX + MAX, 0) << endl; 
} 

इसके बजाय मैं एक दो आयामी सारणी का प्रयोग किया है और यह बहुत अच्छा प्रदर्शन बढ़ावा दिया है, लेकिन मैं क्योंकि बड़े का उपयोग नहीं कर सकते n और कश्मीर मूल्यों।

मैं अपने पुनरावर्ती क्रिया या क्या कैसे बेहतर बना सकते हैं इस समस्या के हल के लिए अन्य तरीके हैं।

+0

यदि आप संभव हो तो मूल समस्या का लिंक साझा कर सकते हैं? यदि प्रश्न प्रत्येक विभाजन के लिए ऊपरी सीमा समान है तो सवाल बहुत आसान हो जाता है लेकिन स्पष्ट रूप से यह आपके द्वारा प्रदान किए गए उदाहरण से नहीं है। – Suparshva

+0

'k' हमेशा' r' के आकार के बराबर है? – ImaginaryHuman072889

+0

@ ImaginaryHuman072889 हां हमेशा। – Atul

उत्तर

1

यह दिलचस्प समस्या है।

प्रथम कहना r_i = r_i - 1, n = n - k, [0, r_i] में संख्या सिर्फ सुविधा के लिए देता है। अब यह जवाब बदले बिना 2 की शक्ति m बनाने के लिए कुछ काल्पनिक संख्या जोड़ना संभव नहीं है।

अब [0, r_i] के प्रत्येक अंतराल को बहुपद 1 * x^0 + 1 * x^1 + ... + 1 * x & r_i के रूप में दर्शाते हैं। अब अगर हम इन सभी बहुआयामी पद गुणा, x^n पर गुणांक जवाब हो जाएगा।

यहां नंबर थियोरेटिक ट्रांसफॉर्म (एनटीटी) नामक संरचना है जो O(size * log(size)) में दो बहुपद मॉड्यूलो p गुणा करने की अनुमति देती है।

तुम सिर्फ एनटीटी का उपयोग कर इसे गुणा करेंगे, तो कोड O(n * k * log (k * max(r))) की तरह कुछ में काम करेंगे। यह बहुत धीमा है।

लेकिन अब हमारे कल्पित संख्या मदद करते हैं। आइए विभाजित करें और तकनीकों को जीतें। हम O(log m) चरणों बना देंगे, हर कदम पर 2 * i वें और 2 * i + 1 वें बहुआयामी पद गुणा। अगले चरण में हम इस चरण के परिणामी बहुपदों को गुणा करेंगे।

हर कदम O(k * log(k)) में काम करता है और वहाँ O(log(k)) कदम दूर है, इसलिए algorhitm O(k * log^2 (k)) में काम करता है। यह तेजी से asymptotically है, लेकिन मुझे यकीन नहीं है कि यह इस समस्या के लिए टीएल फिट बैठता है। मुझे लगता है कि यह अधिकतम परीक्षण पर लगभग 20 सेकंड काम करेगा।

संबंधित मुद्दे