巧妙的方法

1281凸多边形对角线对角线问题；统计问题Description给出一个带n个顶点的凸多边形，我们保证它不存在3条对角线相交于同一个点。请统计每两条对角线的交点数的和。n=6时，图中的15个圆点即为所求交点Input输入只含一个整数n（3≤n≤100）。Output输出交点数。SampleInput6SampleOutput15Hint一个多边形是凸多边形当且仅当每个内角都小于180°。代码：#includestdio.hintmain(){intn;while(scanf(%d,&n)!=EOF){intallb;allb=n*(n-1)*(n-2)*(n-3)/24;printf(%d\n,allb);}return0;}1341巧用异或WhowillbepunishedDescriptionThistime,suddenly,teacherLiwantstofindoutwhohavemissedinterestingDPlessontohavefun.Thestudentswhoarefoundoutwillgetstrictlypunishment.Because,teacherLiwantsallthestudentsmastertheDPalgorithm.However,Lidoesn'twanttowastetheclasstimetocalloverthenamesofstudents.Soheletthestudentstowritedowntheirnamesinonepaper.Tohissatisfaction,thistime,onlyonestudenthasnotcome.Hecangetthenamewhohasnotcometoclass,but,itistroublesome,and,teacheralwayshavemanythingstothinkabout,so,teacherLiwantsyou,whoisintheACMteam,topickoutthename.InputThereareseveraltestcases.ThefirstlineofeachcasehaveonepositiveintegerN.Nisthenumberofthestudents,andNwillnotgreaterthan500,000.Then,followingNlines,eachlinecontainsonenameofstudentswhohaveattendedclass.TheN-1linesarepresentedafterNlines.TheseN-1linesindicatesthenamesofstudentswhohavecometoclassthistime,onenameinoneline.Thelengthofstudent'snameisnotgreaterthan30.Processtotheendoffile.OutputForeachtestcase,firstprintalinesayingScenario#k,wherekisthenumberofthetestcase.Thenoutputthenameofthestudentwhohavenotcometoclass.Onecaseperline.Printablanklineaftereachtestcase,evenafterthelastone.SampleInput3ABCBCSampleOutputScenario#1A代码A：#includeiostream#includecstdio#includestringusingnamespacestd;intmain(){intt;intk=1;while(cint){stringstr,sum;cinsum;for(intj=1;j2*t-1;j++){cinstr;for(inti=0;istr.size();i++)sum[i]=sum[i]^str[i];}printf(Scenario#%d\n,k);coutsumendlendl;k++;}return0;}代码B：#includeiostream#includecstdio#includestringusingnamespacestd;intmain(){intt;intk=1;intsum[32];while(cint){stringstr;for(inti=0;i32;i++)sum[i]=0;for(intj=1;j=t;j++){cinstr;for(inti=0;istr.size();i++)sum[i]=sum[i]+str[i];}for(intj=1;j=t-1;j++){cinstr;for(inti=0;istr.size();i++)sum[i]=sum[i]-str[i];}printf(Scenario#%d\n,k);for(inti=0;sum[i]!=0;i++)printf(%c,sum[i]);printf(\n\n);k++;}return0;}1353素因数问题LCM与数对Description请你求出以n为最小公倍数的不同正整数对(u,v)的个数。注：对于u≠v，数对(u,v)与(v,u)被视为不同的。Input本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。对于每组测试数据：第1行包含一个整数n(1≤n≤1012)。Output对于每组测试数据：第1行输出以n为最小公倍数的不同正整数对(u,v)的个数。SampleInput3234SampleOutput335代码：#includeiostream#includecstdio#includecmathusingnamespacestd;longlongPrime[6000000];intN=12000000;voidfliter(){boolisPrime[N];for(inti=2;iN;i++)isPrime[i]=true;for(inti=2;iN;i++){if(isPrime[i]){for(intj=2;i*jN;j++)isPrime[i*j]=false;}}intk=0;for(inti=2;iN&&k6000000;i++)if(isPrime[i])Prime[k++]=i;}longlongsolve(longlongn){longlongans=1;intk=0;inta=0;intcheck=(int)sqrt(n);while(n1&&Prime[k]=check){if(n%Prime[k]!=0){ans=ans*(1+2*a);a=0;k++;}else{a++;n=n/Prime[k];}}ans=ans*(1+2*a);if(n1)ans=ans*3;returnans;}intmain(){fliter();intT;cinT;while(T--){longlongn;scanf(%lld,&n);printf(%lld\n,solve(n));}return0;}Ps：思想：N为U,V的最小公倍数；设N的素因子是P1,P2，P3，P4.,...Ps；即N=P1^a1*P2^a2*P3^a3.......Ps^as;则V，U,一定包含这些素因子即V=P1^ai1*P2^ai2*P3^ai3........Ps^ais(ai1属于[0,a1]，ai2属于[0,a2]..........)U=P1^aj1*P2^aj2*P3^aj3........Ps^ajs(aj1属于[0,a1]，aj2属于[0,a2]..........)则U,V的情况取决于ai1，ai2，。。。。aj1,aj2......的取值情况对于ai1，aj1一定有一个要等于a1，如果都不等于a1，则最小公倍数一定不会有P1^a1这一项因子。假设ai1=a1，则aj1可取0，1,2,3,4，。。。。a1-1，即有a1种取法。如果aj1=a1，同理ai1有a1种取法。还有两者都是a1的情况，所以是（1+2*a1）种情况；则总共情况是（1+2*a1）*（1+2*a2）。。。。。（1+2*as）1362组合的递推公式XianGe画方方DescriptionXianGe受到委屈时，总要念叨着“画个圈圈诅咒你”。这回，他要“画个方方祝福你”。XianGe得到了一张包含r行c列的表格，他要按照如下规矩画出k个矩形：1.他每次都沿着表格线在刚刚画出的矩形内部画一个新矩形（画第一个矩形时，他将整个表格的边框视为刚刚画出的矩形）。2.每次画出的新矩形是严格在刚刚画出的矩形内部的（即不含公共点或者公共边）。现在给出表格的大小，他要画出k个矩形，他想知道有多少种不同的画法。Input本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。对于每组测试数据：第1行包含三个以空格分隔的整数r，c和k(1 ≤r,c,k≤ 1000)。Output对于每组测试数据：第1行输出XianGe有多少种不同的画法。由于这个数字可能非常大，所以请将答案对1000000007取模后输出。SampleInput2331441SampleOutput19因为宪哥每次都严格在上次的矩形里画新矩形所以可以再r-1行里选出2*k个行，在c-1列里选出2*k个列，用来作为各个矩形的边。这样选出来的边只能确定一种方案。因为矩形不会有交叉嘛所以最靠上和最靠下的两行为最外层矩形的长，最靠左和最靠右的两列为最外层矩形的宽。剩下由外向内递推你举个栗子画一下就知道了这个不知道的应该是组合公式的递推因为数据很大，相乘会出现超界而WA所以用这种递推方式进行计算这样两个数之和保证在INT型内不会超界代码：#includeiostream#includecstdio#defineINF1000000007usingnamespacestd;longlongn[1001][1001];voidinitiate(){for(inti=0;i=1000;i++){n[i][0]=1;n[i][i]=1;}for(inti=1;i=1000;i++)for(intj=1;ji;j++)n[i][j]=(n[i-1][j]+n[i-1][j-1])%INF;}intmain(){initiate();intT;cinT;while(T--){intr,c,k;scanf(%d%d%d,&r,&c,&k);if(2*kr-1||2*kc-1)printf(0\n);elseprintf(%lld\n,(n[r-1][2*k]*n[c-1][2*k])%INF);}}1365巧妙的规律UnluckyNumberIIIDescriptionSomepositiveintegers’representationsonlyconsistoftheunluckydigits4and7.WecallthemUnluckyNumbers.Forexample,numbers74,774,7areunluckywhile2,12,352arenot.Letf(x)betheminimumunluckynumberwhichisnotlessthanx.Whatisthevalueoff(a) + f(a + 1) +f(a + 2)+ ...+f(b - 2) + f(b - 1) + f(b)?InputTherearemultipletestcases.ThefirstlineofinputisanintegerTindicatingthenumberoftestcases.ThenTtestcasesfollow.Foreachtestcase:Li