The Rascal Triangle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 243 Accepted Submission(s): 192
Problem Description
The
Rascal Triangle definition is similar to that of the Pascal Triangle.
The rows are numbered from the top starting with 0. Each row n contains
n+1 numbers indexed from 0 to n. Using R(n,m) to indicte the index m
item in the index n row:
R(n,m) = 0 for n < 0 OR m < 0 OR m > n
The first and last numbers in each row(which are the same in the top row) are 1:
R(n,0) = R(n,n) = 1
The interior values are determined by (UpLeftEntry*UpRightEntry+1)/UpEntry(see the parallelogram in the array below):
R(n+1, m+1) = (R(n,m) * R(n,m+1) + 1)/R(n-1,m)
Write a program which computes R(n,m) the
element of the
row of the Rascal Triangle.
Rascal Triangle definition is similar to that of the Pascal Triangle.
The rows are numbered from the top starting with 0. Each row n contains
n+1 numbers indexed from 0 to n. Using R(n,m) to indicte the index m
item in the index n row:
R(n,m) = 0 for n < 0 OR m < 0 OR m > n
The first and last numbers in each row(which are the same in the top row) are 1:
R(n,0) = R(n,n) = 1
The interior values are determined by (UpLeftEntry*UpRightEntry+1)/UpEntry(see the parallelogram in the array below):
R(n+1, m+1) = (R(n,m) * R(n,m+1) + 1)/R(n-1,m)
Write a program which computes R(n,m) the
element of therow of the Rascal Triangle.Input
The
first line of input contains a single integer P, (1 <= P <=
1000), which is the number of data sets that follow. Each data set is a
single line of input consisting of 3 space separated decimal integers.
The first integer is data set number, N. The second integer is row
number n, and the third integer is the index m within the row of the
entry for which you are to find R(n,m) the Rascal Triangle entry (0
<= m <= n <= 50,000).
first line of input contains a single integer P, (1 <= P <=
1000), which is the number of data sets that follow. Each data set is a
single line of input consisting of 3 space separated decimal integers.
The first integer is data set number, N. The second integer is row
number n, and the third integer is the index m within the row of the
entry for which you are to find R(n,m) the Rascal Triangle entry (0
<= m <= n <= 50,000).
Output
For
each data set there is onr line of output. It contains the data set
number, N, followed by a single space which is then followed by thr
Rascal Triangle entry R(n,m) accurate to the integer value.
each data set there is onr line of output. It contains the data set
number, N, followed by a single space which is then followed by thr
Rascal Triangle entry R(n,m) accurate to the integer value.
Sample Input
5
1 4 0
2 4 2
3 45678 12345
4 12345 9876
5 34567 11398
Sample Output
1 1
2 5
3 411495886
4 24383845
5 264080263
Source
解析：利用题中所给递推公式，将数据存放到数组中有时候是个不错的选择。但本题这样做很可能会MLE，所以应该考虑找出通项公式。可以先写个小程序输出The Rascal Triangle的前几行，观察找规律。
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAA0gAAAD2CAIAAABjrTAUAAAVxklEQVR4nO3dzXqrOLsG4Zz/SWsP+LYuGtALK3FQPUrdo152BhWBfpLY7q8mSZKkJXzNDpAkSdJneLCTJElaBOJg9/WFyJAkSYo2+UT19f/mZkiSJC0AcaLyYCdJkvRziBOVBztJkqSfQ5yoPNhJkiT9HOJE5cFOkiTp5xAnKg92kiRJP4c4UXmwkyRJ+jnEicqDnSRJ0s8hTlQe7CRJkn6O8gHFfkyxJEnSD3mWkiRJWoQHO0mSpEV4sJMkSVqEBztJkqRFeLCTJElaBOJgl/J+2JROSZL0N1E+7mRuxq2UTkmS9JchTiopB6aUTkmS9DchTiopB6aUTkmS9DchTiopB6aUTkmS9DchTiopB6aUTkmS9DchTiopB6aUTkmS9DchTiopB6aUTkmS9DchTiopB6aUTkmS9DchTiopB6aUTkmS9DdRPqAY/vG/KZ2SJOkv84wiSZK0CA92kiRJi/BgJ0mStAgPdpIkSYvwYCdJkrQIxMGO/z7TrLfERkRKkqSPo3zcydyM2iGPXBsxnpIk6ZcgTgDwg0jQwW7DL5QkSb8BcQKAH0Q82EmSpAiIE0DWQYRfyy+UJEm/AXECCDqIRKRGREqSpI9DnABSDiJ2SpIkMsQJIOIgEhG5CUqVJEkfhDgB8A8i/MK9rFpJkvQpiBMA/CDiu2IlSVIEygcUkz9W9+tkdtFQSqckSfoN7v2SJEmL8GAnSZK0CA92kiRJi/BgJ0mStAgPdpIkSYtAHOz4799MeatpSucmIlKSpCCUjzuZm1FL+Ry7lM4Wct0lSYqD2FnhG3zKgSmls+MXSpKUBbGzZm3wKbX8Tn6hJElZEDtr0AafkhrRGREpSVIQxM4ascGnvCYspbOFXHdJkoIgdtagDT4lNaIzIlKSpCCInTVrg0+p5XfyCyVJyoLYWeEbfMq7TVM6O36hJElZEDsrfINPOTCldHb8QkmSslA+oBj+kv+IyJbZCU+VJCmIe6okSdIiPNhJkiQtwoOdJEnSIjzYSZIkLcKDnSRJ0iIQB7ug90WSU79OZhfdM1KSpA+ifNzJ3IyH4Knktkvw8Wxp96ckSYgdK2XjhO/x5LZL8PHsIiIlSWoe7J7bIsmp5LYz/nh2EZGSJDUPdg/1QnJq0KvrIsazi4iUJKl5sHso4iCybyN3tpDx7CIiJUlqHuyeCDow7WFT48YzIlKSpObB7onzx4jAgzfYyLjxhOdJktQhdqygjZOcemgjp3ZGSpL0QYgdK2jjJKfG/YmzhXRGREqS1KYf7LL+HsdPheftZY0nOVKSpM69SpIkaREe7CRJkhbhwU6SJGkRHuwkSZIW4cFOkiRpEYiDHfz9himfpmvnZ6V0dvxCSdJvo3zcydyMGjyv+wr5gOLQTrKIeSRJegFiJ4BvSPC8SynN5E5y26W4YEnSxyF2AviGBM+7lNJM7iS3XYoLliR9HGIngG9IQa+y2tj5EV53SVIcxE4A35D2efDUTURkw3d63SVJcRA7QdaGBK+F53UpnR0/mF8oSfptiJ0ga0OC18LzupTOjh/ML5Qk/TbETgDfkFI+nmMDz+v4nVnXvSUUSpJ+G2IngG9IWa+14hdu+J1Z172FREqSfhXlA4rh7z3kF3YRkS2kM+W6p8wjSdJvcw+QJElahAc7SZKkRXiwkyRJWoQHO0mSpEV4sJMkSVoE4mAX8T6+iPcbMt8XedkD7DxjjuellM4WMt8lKRTl407mZtzqheRU4Oeuja6v4/lZEePZcua7JOVCrLDwhR6e12H/Twl1GKfzILSTLy5YkoIgVlj4Qg/P67AHEQ92vwobNhIXLElBECssfKHf8vh/RcIeRDzY/aqU+7OLiJSkUIgVFr7QH/ZLbO0hktO5wMEONZ4HKfdnxy+UpFyIFRa+0KccRNp/f23D6Qw92DXqeB4EjeeGXyhJuRArLHyhj9s4N5zO3IPdHrYzbjz5hZKUC7HCwhf6uI1zw+n0YPer4saTXyhJuRArLH+hT3kNU29DRZ5jmJ1ncZ0Nn9oSCiUpF+UDiskvTt9ERDbYy/yL64vqLGR1wlOD5rskhXJtlSRJWoQHO0mSpEV4sJMkSVqEBztJkqRFeLCTJElaBOJgB39/3NfJ7KL/GZVwCjeXH3dCG8yW3Fk/DoGdRyP8Qkk6o3zcydyM2vlzOmaV7Bsux402nqMPOin+OUV0Z/E4CnA8RyLGU5IuIVauoAUUlZrymxv+gWkT2nn7OFBEakSkJB0gVq6gBRSVmrLB1z2c2vROTuGtiNSISEk6QKxcKQsorTNlgy96UKnpnajIgp2S9HsQK1fKAkrrTNngL3uAr2GK7iwep7FTkn4PYuWKWECBkSkbfPpvwuqn3pdy3S9FRG6CUiWpQ6xcEQsoMDJlg09/7dqTZ9+Uct0vRURuglIlqUOsXBELKDAyZYMPfbdpSuft4ygRkZugVEnqECtXxAIKjEzZ4EMPTCmdt4+jRERuglIlqaN8QDHwJeoHqLzRuNHG80nnxLxupU5I6gg8bxM0npJ04JolSZK0CA92kiRJi/BgJ0mStAgPdpIkSYvwYCdJkrQIxMGO/74z5lvkzjEpnS3hf9X1dTIr7CB0PBv1/jxL6dxEREp6DeXjTuZm1M77/aySfcN53FI6266NENkcz09LGc9LKZ0tZP2U9DLEigBfmLALfcrGiQ07KMJQzaHjuUY2EL9Q0psQKwJ8YcIu9HUJtpMTduDB7rNS7s+DlOHt+IWS3oRYEfgLE+1PXZvogwjwr0ijGFRkyx/P+ikC5nwfiYiU9BrEihCxMNF2zRb7IvpDIac292AXNJ7A+/NSSmcjXXFJBIgVgb8wMX+CT/mNSMprrUYHkfdLatHjefsUAXO+j0RESnoNYkWAL0yJG+fts2+KPohw8rro8Xz47ETY8RzhF0p6E2JFgC9M2IU+dINP6SwenCt0PLGdBymdHb9Q0psQKwJ8YcIu9Ckb57kk6zVh75fUQscTe38epHR2/EJJb5q8Inz919yYAi1yNG4pnfunZrXt1Z2zqs7Sx5N2f44kdsJTJb3GtUCSJGkRHuwkSZIW4cFOkiRpER7sJEmSFuHBTpIkaRGIgx3//VzM952N3hdJqz2XAAuLJDu/h3/dNynz6IxfuJfSKaWjfNzJ3Iza138/r2FiSXc5bpC2vdtOQnOdx7k/UzpbyHVvOfPoEnA8R2j3p7Q2xEyDT3jsuo8NO6g7p2ff9kwv3KR0dvDr3mHDanHZ/EJpDYiZBp/w2AUUG3YA3+BTDkwpnR38unfYsFpcNr9QWgNipsEnPHYBPYcx/+SRssFv+AemDb8z5bqnzKMD7HiO8AulNSBmGnzCn1/MNDFmj/8aps3ti8NeLxq6jEEVbiI6U657yjw6wI7nCL9QWgNipvEn/P4neE5tXULuzBpPTuEmtzPruj95di7meI7wC6U1IGZa1oTn1KZsSBGdRQakcJPS2UKue8vprPE7+YXSGhAzLWvCc2pDX8P0T8++g1+4SencpNSmzKMav5NfKK0BMdP4E74XolJTXht0+Se50VPvu93ICZEtp7ODX/cuZR6dMcdzJCJSWsDkmfb1X3NjaqjC0bjRRrK4vpzOr5PRUxMjzzHYzroHUrhJmUeFiE7a/SmtzTkmSZK0CA92kiRJi/BgJ0mStAgPdpIkSYvwYCdJkrQIxMGO9j6pyx7g+7ku32+IevdZ/dZISGQb9ASNZ4Pdn+njiYrs+PN9c1mCKqyldEojlE9wmJvRFbvm4T/mGu1GxT/fN+oJ7ZyuGDdUc/p40u7PFjLfW876OULbj6TvQdzBtInEX0A3RQkhMmXjXOwgMt1inZxs+HzvUtbPEX6hVEPcwbSJlLIwwRf6lI1zsYPIdIt1crLh871LWT9H+IVSDXEH0yZSysI0KuEU7qXU7jd48p9mDgcRbGrceD58/H38wk3K+jnCL5RqiDuYNpFSFqaUhb7lpO57Rv9NcGjDpiaO55PHp4iIbDnr5wi/UKoh7mDaREpZmC5LOHld6Ib0T8++Kfr+fPjsm6LvT1pky7k/R/iFUg1xB9MmUsrCFLHQR++a//QF7zhnMO/P3PGsH58oYr63nPVzhF8o1RB3MG0ipSxM/IU+Zdd8MpKEZjs/K+X+3PDn+yZl/RzhF0o1xB1Mm0jFL0VQqfCFfrSg0xb6J53TI88N2JevpY8n7f7s4PO9S1k/RyIipcL8PWBvbkzdAync1J2zqg6+TurHaZ37pybmdfW4cVLTx5N2f56TDk/Nqjq7vT9nhT1Eu+7S93jvSpIkLcKDnSRJ0iI82EmSJC3Cg50kSdIiPNhJkiQtAnGwo73/aNTD76S9n6t+aySntn4rH6FwUw+anf8q+roD59GGvy5tUtb5kZROvY/ySRNzM7pRT0TnYdF/PepolEdo23vSSWiuLzfn/kzvTLnuhLaDiHWp5azzIymdmgVxZ9Bu0JSf5IoF9PzP96VsSA87p2ff9kwv3KR3plz36WEj8HWpS1nnR1I69T7EnUG7QVMmPHwBTdmQUjb4A+yB6QDbmXLdU+ZRB1+XupR1fiSlU+9D3Bm0GzRlwqcsoJv9hkT+UwJ2g9+7jEEVblI6W8h1bwnzKGVdSlnnR1I69T7EnUG7QVMmfLFi0pb7Q9vlfxMUnZDUogRSuEnp3PCv+yZiHqWsS0H356WUTr0PcWfQbtCUCX/5R66+dHJq6xJyJ3M8W85vwiI6U6678+izUtb5kZROvQ9xZ9Bu0JQJH7HQ32bY+T2X2+eUkhq8M+W6p3S2kHWp5azzIymdeh/izqDdoCkTnr+APvmFDbbzG1/zq27HbXrhJqWzhVz3UQNwHm3469ImZZ0fSenU+xB3Bu0GTZnwxZZJSB1tPLTXBtUvCbr8milSDkwLdEZcd9o86uDrUpeyzo+kdOp9838JsTc3puhJ6exPzQrb+zo5PzUxrys6G2k8239TR48TaiM6U657yjxqIetSy1nnR1I6NYv3hCRJ0iI82EmSJC3Cg50kSdIiPNhJkiQtwoOdJEnSIhAHO9r7es49tLcg1T2QyPbs3ZGz2vbSOxv4XYeXD0Jqo8ezeHyW9M7+7PtJhdHNyRnPWkTkYiifODA3oxutSsU/31f0oMZz1Jkynimdbdw8heP5WenjmdLZYOtnC9mPCrTx/DsQI0678PCJdNszvXCTvtCHdk73ZNwIzenjGXp/YjuLR+aC70e3+IXrQYw47cLDJ1LKwpSy0B+MerCdtLAD7MHuIHo8i8dfkzLfU9bPDr4f3eIXrgcx4rQLX/fwa2mFG+yfuvawu+bBeTCZf/WIO9W1wPEsHp8oYr63hPUzaz864xeuBzHitAtf9ESk0iLbYPVEdY56+J2HRyC1xbhBCjfp40m7Pzf8+b6JWD+D9qNLEZGLQYw47cJHbEgtuRP7E3zikJL/NMP/dcgmdzzrx6dIme8Rg9lyOkdSOleCGHHahffHuA+63dpRtS1nGR1tltjOy39yhI7n7eMvS5nvKetnC9mPCkGpy0CMOO3C83/NkPKqiydL0vTaUY+d31P3TM/r0seT1jlqSOl8+Oz7+PtRLat2DYgRp114+M502zO9cJOyIaV3Fv89BXz6dOnjSRvY9M7ikblSJtQIv3A98+fY3tyYUc/XCSrysAnFdU4s7EY9KZ37p6aEHdSdU5IupY8n6v5Mme8PO4Gplw8SOkdSOtfjWEuSJC3Cg50kSdIiPNhJkiQtwoOdJEnSIjzYSZIkLQJxsKO9X6Z4ixwkddST0tmffT/p0pO3yHFqW85nlsLvzy60s3hwipR5FL0uFY/PdY5hdo5ERD5E+USMuRndaBYV/3zfqCels8Gue8p4dsVCPyvp0nmDPzz7etG10M4Gu+4p88h16eMi9s0C6rp/BOI7oQ0o/AZNmfC3PdMLN0/GDZK6Ga1BqMgWe2BK6dw//n7MWco8Sl+XyPfn838C8QufQ3wntAGte6bXPpww0zsPsAvoAXZD2mwl8MhWdu6/YLoFOiGFBymp2HUpbp2H75u3+IXPIb4T2oDyV/m9iAU0IrLhO0c/tRcPTlF3Fo+/bI1OSOSenR/HT83aN88iIh9CfCe0AR1NIVpnG/y4ieoseuz8VykbfNGJuj8X6Bw9OEvEPGo5nRv4/bkJ2jcvpXQ+gfhOaAOa8pNHSmdL2JA22L/LtP+WkMfztrN4/E3LdBIiD8jzaC9iPFPW+ZTOkYjIhxDfCW1AI14rcJsB6exC13pO5NeVwxfMatu77exf9n7bIWCNzumFlyIiG35dClrnI/bNAr/wOcR3QhvQekki1D7ZgaZ33vZML9zwL/cZ8whyVvy2CVWb2Fk/+L6UeZSyLrWQdb5LuQFG+IXPIb4T2oDCb9BRT0pn8cgU8Mt9ibzB7yUemFI66wfflzKP0tel0IHldI7wC5+bv/fXfweB9JAjsZ1t3EO+7uenpiSNXA4dbTzbg865ed0ynYTUlHk06kSN59fJ5VMTC7uUzhHUdf+IFb4HSZIkNQ92kiRJy/BgJ0mStAgPdpIkSYvwYCdJkrQIxMGO9j6UogeSevsWJMi7e25jCJF7lz20yDb4jAZ+J+fObHfzhdO5Rx7PvdD7s3hwipT1M2U/2vD399qTSMo7uudmdLeziJB6XtwvH59u1Ll/BNU82t1RkW3QefgPgvNCf/nfszxZ3wmdHXw8u9D7s8Hme8r6GXGtNxH7e+H5/Yn4NmijCb/wKRMpZWHqRj2oyFZu8Ch15/TsYpo/+bL3wcezC70/94+/H3OWsn6m7EcdfH+/5cHum4rZTkiNm0iby2xOc9HDiWxXnai87rZzenbWwY4/npvc+/PwFA12/Yzbj+D7+y0Pdt90+bPR6Knp9m3Pf1X7Mvjkr3sgkW3Q2ZckzqUvOkf/fN9ovtA6W8h4tvD78/wsB3z93OPvR1n7+5kHu28KuvCjhZ7TeTmxaeOZstCPNk7apb89iBCW+4dzZ3pnCxnPFn5/np8liFg/O/5+1KL290se7L6pWNlRqXUMNpU2nrc9hMiWcxCp2/pGNb3zYLS4T+9MGc8F7s/iwbnI62eXsh+l7O8jHuy+abR67s1q21f98Atett84UeN52wMZyVEnrfbh9Z3eebC/Py8fnyVlPJe5P6cXXvqirp+96odf8Jrz5QaOZ+FJHuIboI1j0QNJfbKyT0990jM98iAisrF/I7JHnkqjcXM8fy76/oQUBq2fEftRlzKJRjzYfRP8wj/ZkMidtw9OFBHZcv6a8PDwNMWTwwehcy+98/zUXOT5nrJ+puxHHXx/vxVwsKP9/rPo4aR+nZyfmpi3V4wYZzyLHlpkGyehIttd58SwvWLQUJ0tZDxb+P1Jm+9FDCf16+T81MS8vWLQOONZeB4J/QYkSZL0rzzYSZIkLcKDnSRJ0iI82EmSJC3Cg50kSdIiPNhJkiQtwoOdJEnSIjzYSZIkLeL/AMbnRKJBCNEbAAAAAElFTkSuQmCC" alt="" />
很容易发现通项公式为1+(n-m)*m。
#include <cstdio> int P;
int N,n,m; int main()
{
scanf("%d",&P);
while(P--){
scanf("%d%d%d",&N,&n,&m);
printf("%d %d\n",N,+(n-m)*m);
}
return ;
}