總和由4組成4 5 6

Question

給出三個整數x，y和z。你必須找到所有數字的總和，這些數字的數字只有4,5和6，它們的十進制表示至多爲十四，十進制表示的最多爲十五，十進制表示的最多爲五十六進制

我現在用的概念Describe Here

我的代碼：

// fact[i] is i! 
    for(int i=0;i<=x;i++) 
     for(int j=0;j<=y;j++) 
      for(int k=0;k<=z;k++){ 

      int t = i+j+k; 
      if(t==0) continue; 
      long ways = fact[t-1]; 
      long pow = (long) Math.pow(10,t-1); 
      long rep=0; 
      if(i!=0){ 
       rep = fact[j]*fact[k]; 
       if(i>0) rep*=fact[i-1]; 

       o+= 4*pow*(ways/rep); 
      } 

      if(j!=0){ 
       rep = fact[i]*fact[k]; 
       if(j>0) rep*=fact[j-1]; 

       o+= 5*pow*(ways/rep); 
      } 

      if(k!=0){ 
       rep = fact[i]*fact[j]; 
       if(k>0) rep*=fact[k-1]; 

       o+= 6*pow*(ways/rep); 
      } 

     } 

但我得到了x=1 , y=1 and z=1我得到3315而正確答案是3675錯誤的答案。

請幫我找到我的錯誤。

4+5+6+45+54+56+65+46+64+456+465+546+564+645+654=3675 

Answer 1

問題不在於你的代碼，它與你的邏輯：設S是一組只由上述數字4，5和6號要計算SUM（S）。但是因爲你只考慮了這些數字的第一個數字，所以你實際上是在計算SUM（s，s - s％10^floor（log10（s）））。

你這樣做雖然正確，因爲

4 + 5 + 6 + 40 + 50 + 50 + 60 + 40 + 60 + 400 + 400 
    + 500 + 500 + 600 + 600 = 3315 

長話短說，所有你需要做的是應用用戶גלעד ברקן's approach下面來解決你的代碼。這將導致O（xyz（x + y + z））算法，並且通過查看SUM（i = 0到t-1，10^i）=（10^t-1） ）/ 9，所以真的足以改變一行在你的代碼：

// was: long pow = (long) Math.pow(10,t-1); 
long pow = (long) (Math.pow(10,t)-1)/9; 

還有使用僅使用一個最小的數學和combinatrics的動態編程一個非常簡單的O（XYZ）時間+空間法：令g（x，y，z）爲元組（count，sum），其中count是由正好爲 x 4，y 5s和z 6es組成的4-5-6數字的數目。 總和是他們的總和。然後，我們有以下復發：

using ll=long long; 
pair<ll, ll> g(int x, int y, int z) { 
    if (min(x,min(y,z)) < 0) 
     return {0,0}; 
    if (max(x,max(y,z)) == 0) 
     return {1,0}; 
    pair<ll, ll> result(0, 0); 
    for (int d: { 4, 5, 6 }) { 
     auto rest = g(x - (d==4), y - (d==5), z - (d==6)); 
     result.first += rest.first; 
     result.second += 10*rest.second + rest.first*d; 
    } 
    return result; 
} 

int main() { 
    ll res = 0; 
    // sum up the results for all tuples (i,j,k) with i <= x, j <= y, k <= z 
    for (int i = 0; i <= x; ++i) 
     for (int j = 0; j <= y; ++j) 
      for (int k = 0; k <= z; ++k) 
       res += g(i, j, k).second; 
    cout << res << endl; 
} 

我們可以添加記憶化到克避免計算結果的兩倍，從而產生一個多項式時間算法，而不需要組合學的見解。

對於您可以使用超過3位數的情況，這很容易推廣，如gen-y-s's answer所示。對於你的數字形狀有更復雜的限制的情況也是一般化的。如果你想在一個給定的範圍內對數字進行求和，通過結合它，它甚至可以被推廣到with another generic DP approach。

編輯：還有一種方法來描述你的函數F（X，Y，Z）直接，含4-5-6號碼最多 X四肢着地，Y五歲以下兒童和z的總和亂七八糟。你需要包容排除。例如，對於計數部分，我們有：（x，y，z）= c（x-1，y，z）+ c（x，y-1，z）+ c（x，y，z） z-1）-c（x-1，y-1，z-1）+ c（x-1， y-1，z-1）

這對和數稍微複雜一些。

Answer 2

在Python 3：

def sumcalc(x,y,z): 
    if x < 0 or y < 0 or z < 0: return -1 
    import itertools 
    sum = 0 
    for i, j, k in itertools.product(range(x + 1), range(y + 1), range(z + 1)): 
    e = (('4' * i) + ('5' * j) + ('6' * k)) 
    if e: 
     perms = [''.join(p) for p in itertools.permutations(e)] 
     for i in set(perms): sum += int(i) 
    return sum 

這種方法是簡單的，並且可以與大多數任何編程語言不一定包括類似的語法糖，如果任何被使用。的基本步驟是：

1. 對於給定的整數x，y和z都> = 0，寫一個串對於每個從0忽略的「4」，以重複x次從0「5」的所有組合的到y發生並且從'0到z發生'具有'6'。 （但爲了確保完整性，生成組合。）

2. 對於在（1）中生成的每個字符串，生成其字符的所有唯一且非空的排列。

3. 對於（2）中產生的每個字符串排列，將其轉換爲整數並將其添加到總和中。

Python 3整數具有無限的精度，所以不需要拖入Long或BigInteger類型來改進它。

Answer 3

編輯：我意識到帖子鏈接描述了相同的東西。我錯誤地認爲它與幾天前浮在SO上的類似問題有關，而這個問題完全不同。因此刪除它，但後來被取消刪除，因爲它可以解釋OP中代碼中的錯誤。

這可以解決作爲具有的Ô複雜組合問題（X Ý Z）。

讓我們分裂的問題分爲兩個部分：

組分A：查找，包括精確的x 4S，Y 5S和z 6S數量的總和。這是相當簡單：

1. 讓數如下：_ _ _..._ 4 _ ... _，其中所示的4出現在10^k位置。其餘的數字可以安排在(x+y+z-1)!/((x-1)! * y! * z!)的方式。因此，在這個位置4貢獻的總和是4 * 10^k * (x+y+z-1)!/((x-1)! * y! * z!)，這是4 * x * 10^k * (x+y+z-1)!/(x! * y! * z!)。

2. 同樣，5和6貢獻，並且該位置的數字總貢獻爲： 10^k * (x+y+z-1)!/(x! * y! * z!) * (4x + 5y + 6z)。

（例如，具有x=y=z=1並在10^2位置時，所述貢獻是400*2 + 500*2 + 600*2 = 3000（按照實施例）如圖每計算它是100 * 2!/(1! * 1! * 1!) * (4+5+6) = 3000。）

因此（X + Y + Z）位數的整體貢獻是：

​​

= (x+y+z-1)!/(x! * y! * z!) * (4x + 5y + 6z) * (10^(x+y+z) - 1)/9

所以在上面的例子中，所有3位數字的總和應該是： 2!/(1! * 1! * 1!) * (4+5+6) * (999)/9 = 3330。 根據示例，它是：456+465+546+564+645+654 = 3330。

部分-B：

1. 執行與上述相同，但其中x y和z分別承擔值從0-X，O-y和0-Z。這可以通過在（0..x），（0..y），（0..z）端點（包括端點）中的3向嵌套循環來完成。在每次迭代中使用上面的公式

2. 所以對於上面的例子，我們有x：0-1，y：0-1，z：0-1。可能的指數是{(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)}。根據上述公式計算的2位數字的和是例如：

   （0,1,1）：1！/（0！* 1！* 1！）*（5 + 6）* 99 （1,0,1）：1 /（1！* 0！* 1！）*（4 + 6）* 99/9 = 110 （1,1,0）：1/（1！* 1！* 0！）*（4 + 5）* 99/9 = 99

其加起來330。 在這個例子中，45+54+56+65+46+64 = 330。

對於給出15的單位也是如此。因此總和爲15+330+3330=3675。

注：

1. 上面可以推廣到鏈接問題和任何數量的數字（不要求數字是連續的）。如果數字爲零，則方法必須稍微調整，但基本原理相同。

2. 你可以使用類似的技術來計算7到100萬的數量等等。這是一個強大的組合方法。

Answer 4

python 3中的解決方案，它使用帶重複算法的排列。可以適應其他情況，因爲輸入是具有作爲請求數字的鍵的字典，並且值是每個數字的計數。

算法解釋： 您可以將排列看作一棵樹，其中根包含零長度數字，其子代表1位數字，下一級別具有2位數字等。每個節點有3個子節點，它們表示父節點的值由一個數字擴展。所以這個算法基本上是一個預定樹步行。每次遞歸調用都會獲取當前編號，並添加數字（保存在字典中，數字作爲關鍵字，計數作爲值）。它迭代字典，依次添加每個可能的數字，然後遞歸新數字和剩下的數字。該方法還在開始時返回當前數字，然後執行所述遞歸。

#!/usr/bin/env python3 

import itertools 
import copy 

class Matrix: 
    def __init__(self, dim): 
    m=None 
    for i in dim: 
     m=[copy.deepcopy(m) for j in range(i)] 
    self.mat=m 
    def getVal(self, coord): 
    m=self.mat 
    for i in coord: 
     m=m[i] 
    return m 
    def setVal(self, coord, val): 
    m=self.mat 
    l=coord.pop() 
    for i in coord: 
     m=m[i] 
    coord.append(l) 
    m[l]=val 

def sumOfNumbers(digits): 
    def _sumOfNumbers(counts): 
    max_v=-1 
    for v in counts: 
     if v<0: 
     return (0,0) 
     elif v>max_v: 
     max_v=v 
    if m.getVal(counts)==None: 
     c=0 
     s=0 
     if max_v==0: 
     c=1 
     else: 
     for i, d in enumerate(digits.keys()): 
      counts[i]-=1 
      r=_sumOfNumbers(counts) 
      counts[i]+=1 
      c+=r[0] 
      s+=r[1]*10+r[0]*d 

     m.setVal(counts, (c,s)) 
    return m.getVal(counts) 

    dim=[v+1 for v in digits.values()] 
    m=Matrix(dim) 
    tot_val=0 
    for i in itertools.product(*map(lambda x: range(x), dim)): 
    r=_sumOfNumbers(list(i)) 
    tot_val+=r[1] 

    return tot_val 

def main(): 
    x=1 
    y=1 
    z=1 
    print(x,y,z) 
    print(sumOfNumbers({4: x, 5: y, 6: z})) 

if __name__ == "__main__": 
    main() 

Answer 5

這裏是你需要的！ 希望它能正常工作:)

using namespace std;

typedef long long ll;

const ll mod = 1000000007;

INT主（）{

int q, a=0, b=0, c=0, x, y, z, l, r,count=0; 
long long int sum = 0,i,n,temp; 
cin >> x >> y>>z; 
string xyz = "4"; 
for (i = 0; i>-1; i++) 
{ 
    n = i; 
    //sum = 12345620223994828225; 
    //cout << sum; 
    while (n > 0) 
    { 
     temp = n % 10; 
     if 
      (temp == 4) 
     { 
      a++; 
     } 
     if (temp == 5) 
     { 
      b++; 
     } 
     if (temp == 6) 
     { 
      c++; 
     } 
     count++; 
     n = n/10; 

    } 

    if (a <= x && b <= y && c <= z && (a + b + c) == count) 
    { 
     temp = i%mod; 
     sum = (sum + temp) % mod; 

    } 
    else if ((a + b + c) > (x + y + z)) 
     break; 
    if (count == c) 
    { 
     i = 4 * pow(10, c); 
    } 
    count = 0; 
    a = 0; 
    b = 0; 
    c = 0; 
    temp = 0; 
} 
cout << sum+4; 

return 0; 

}

Answer 6

你的邏輯幾乎是正確的。您只是忘記了每個數字都可以出現在每個配置(i,j,k)的每個位置（您的條款中爲pow）。

for(int i=0;i<=x;i++) 
    for(int j=0;j<=y;j++) 
    for(int k=0;k<=z;k++){ 

     int t = i+j+k; 

     for (int p=0; p<t; p++){    // added loop 
     long ways = fact[t-1]; 
     long pow = (long) Math.pow(10,p); // changed 

，或者甚至更好，這要歸功於尼克拉斯B.的評論：您可以通過添加額外的循環輕鬆解決您的代碼，而不是增加一個循環只分配給pow

pow = (long) Math.pow(10,t - 1)/9 

Answer 7

剛計數沒有的4,5和6 occurances的和使用的memoization存儲在第二可變.. C++下面

#include <bits/stdc++.h> 
#define ll int 
#define mod 1000000007 
using namespace std; 
struct p 
{ 
    ll f,s; 
}dp[102][102][102]={0}; 

p c(ll x,ll y,ll z) 
{ 
    if (min(x,min(y,z)) < 0) 
    { 
     p temp; 
     temp.f=temp.s=0; 
     return temp; 
    } 
    if (!max(x,max(y,z))) 
    { 
     p temp; 
     temp.f=1; 
     temp.s=0; 
     return temp; 
    } 
    if(dp[x][y][z].f&&dp[x][y][z].s) return dp[x][y][z]; 
    p ans; 
    ans.f=ans.s=0; 
    for (int i=4;i<7;i++) 
    { 
     p temp; 
     if(i==4) temp=c(x-1, y, z); 
     if(i==5) temp=c(x, y-1, z); 
     if(i==6) temp=c(x, y, z-1); 
     ans.f = (ans.f+temp.f)%mod; 
     ans.s = ((long long)ans.s+((long long)i)*(long long)(temp.f) + 10*(long long)temp.s)%mod; 
    } 
    dp[x][y][z].f=ans.f; 
    dp[x][y][z].s=ans.s; 
    return ans; 
} 

int main() 
{ 
    ll x,y,z,ans=0; 
    scanf("%d%d%d",&x,&y,&z); 
    for (ll i = 0; i <= x; ++i) 
    { 
     for (ll j = 0; j <= y; ++j) 
     { 
      for (ll k = 0; k <= z; ++k) 
      { 
       ans = (ans + c(i, j, k).s)%mod; 
       cout<<dp[i][j][k].f<<" "<<dp[i][j][k].s<<endl; 
      } 
     } 
    } 
    printf("%d",ans); 
    return 0; 
}