शीर्षक यह सब कहते हैं।तरीके की संख्या लिखने के लिए एन प्रत्येक भाग पर प्रतिबंध के साथ कश्मीर की संख्या का योग के रूप में
मैं कहाँ प्रत्येक भाग कश्मीर मैं = k मैं < = r मैं दिया सरणी r
के लिए की सीमा में होना चाहिए n
k
हिस्से की राशि के रूप में विभाजित करने के लिए की जरूरत है।
-
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 <= 10
7
1 <= k <= 10
5
1 <= r
i
<= 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 और कश्मीर मूल्यों।
मैं अपने पुनरावर्ती क्रिया या क्या कैसे बेहतर बना सकते हैं इस समस्या के हल के लिए अन्य तरीके हैं।
यदि आप संभव हो तो मूल समस्या का लिंक साझा कर सकते हैं? यदि प्रश्न प्रत्येक विभाजन के लिए ऊपरी सीमा समान है तो सवाल बहुत आसान हो जाता है लेकिन स्पष्ट रूप से यह आपके द्वारा प्रदान किए गए उदाहरण से नहीं है। – Suparshva
'k' हमेशा' r' के आकार के बराबर है? – ImaginaryHuman072889
@ ImaginaryHuman072889 हां हमेशा। – Atul