题目2 : 大神与三位小伙伴
- 样例输入
-
2 1 3
- 样例输出
-
Case 1: 1 Case 2: 72
中文题目，不解释，开始写了个搜索找三个数，结果一直A不了，就写了个直接循环的判断，暴力程序过小数据还是没问题的，O（10^7）的复杂度：代码：//source here #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1e9+7; long long ans; int main() { int i,j,k; int tes,p; cin>>tes; for(int cas=1;cas<=tes;cas++) { ans=0; cin>>p; printf("Case %d: ",cas); for(i=1;i<=p;i++) { for(j=1;j<=p;j++) { for(k=1;k<=p;k++) { int tt=0; if(i==j) tt++; if(j==k) tt++; if(i==k) tt++; if(tt!=1) { ans=(ans+i*j*k)%maxn; } } } } cout<<ans<<endl; } return 0; } /* 4 400 */
后来想推公式，发现网上有个写的特别详细：1.先计算所有情况：
(1,1,1) n*n*n
(1,1,2) n*n*(n-1)
……
(n,n,n) 1*1*1
全部加起来就是(1+2+...+n)^3(注：本文中所有^表示幂，而不是异或)，
同时，1+2+..+n=n*(n+1)/2，
所以，(1+2+...+n)^3=(n*(n+1)/2)^3。
2.排除掉有两个及以上的同样价值的：
就会有(x,x,i),(x,i,x)(i,x,x) 三种情况(1 <= x,i <= n)。
所以可以得出一共有(1^2+2^2+3^2+...+n^2)*(1+2+...+n)*3，
又因为1^2+2^2+3^3+...+n^2=n*(n+1)*(2*n+1)/6，
所以(1^2+2^2+3^2+...+n^2)*(1+2+...+n)*3=n*(n+1)*(2*n+1)/6*n*(n+1)/2*3。
3.把三个相同的加回来：
那就是1^3+2^3+...+n^3，
而这个又等于(1+2+...+n)^2，
同时，1+2+..+n=n*(n+1)/2，
就可以再简化为(n*(n+1)/2)^2。
但是要注意的是，这些在第2中情况里被算了3次！
所以乘三！
4.得出最后结果
经过化简为(n*(n+1)/2)^3-n*n*(n+1)*(n+1)*(n-1)/2
然后想的就是如何计算这个公式，乘法的时候下面有分母，一般处理这样的情况会使用逆元，但这个题目有点特殊n最大为10^18，那么不会爆long long，n*n会爆unsigned long long，根据上面的公式可以想到分奇数和偶数讨论。具体实现见代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int mod=1e9+7; int main() { int tes; long long ans,n,tmp,t1,t2; cin>>tes; for(int cas=1;cas<=tes;cas++) { cin>>n; printf("Case %d: ",cas); if(n%2==0) { t1=n/2%mod; t2=(n+1)%mod; } else { t1=(n+1)/2%mod; t2=n%mod; } tmp=t1*t2%mod; ans=tmp*tmp%mod*tmp%mod; tmp=tmp*(n%mod)%mod*((n+1)%mod)%mod*((n-1)%mod)%mod; ans=(ans-tmp+mod)%mod; cout<<ans<<endl; } return 0; } /* 4 400 */
描述
L国是一个有着优美景色且物产丰富的国家，很多人都喜欢来这里旅游并且喜欢带走一些纪念品，
大神同学也不例外。距离开L国的时间越来越近了，大神同学正在烦恼给她可爱的小伙伴们带什么
纪念品好，现在摆在大神同学面前的有三类纪念品A, B, C可以选择，每类纪念品各有N种。其中种
类为A_i, B_i, C_i的纪念品价值均为i, 且分别有N+1-i个剩余。现在大神同学希望在三类纪念品中各
挑选一件然后赠送给她的三名可爱的小伙伴，但是她又不希望恰好挑出来两件价值相同的纪念品，
因为这样拿到相同价值纪念品的两位小伙伴就会认为大神同学偏袒另一位小伙伴而不理睬她超过
一星期。现在，大神同学希望你买到的三件纪念品能让三位小伙伴都开心并且不和她闹别扭，她想
知道一共有多少种不同挑选的方法？
因为方案数可能非常大，大神同学希望知道挑选纪念品的方案数模10^9+7之后的答案。
输入
第一行包括一个数T，表示数据的组数。
接下来包含T组数据，每组数据一行，包括一个整数N。
输出
对于每组数据，输出一行“Case x: ”，其中x表示每组数据的编号(从1开始)，后接一个数，
表示模10^9+7后的选择纪念品的方案数。
数据范围
小数据：
1<=T<=10
1<=N<=100
大数据：
1<=T<=1000
1<=N<=10^18
样例解释
对于第二组数据，合法的方案有以下几种，(X,Y,Z)表示选择了A类纪念品中价值为X的，
B类纪念品中价值为Y的，C类纪念品中价值为Z的。
(1,1,1): 3*3*3=27种
(1,2,3): 3*2*1=6种
(1,3,2): 3*1*2=6种
(2,1,3): 2*3*1=6种
(2,2,2): 2*2*2=8种
(2,3,1): 2*1*3=6种
(3,1,2): 1*3*2=6种
(3,2,1): 1*2*3=6种
(3,3,3): 1*1*1=1种
一共27+6+6+6+8+6+6+6+1=72种选择纪念品的方案
注意，如(1,1,2), (2,3,3), (3,1,3)都因为恰好选择了两件价值相同的纪念品，所以并不是
一种符合要求的纪念品选择方法。