Chef Counting Matrices 矩阵
题目大意：给你一个2*2的矩阵的迹--n。让你求所有元素为正且行列式的值为正的情况数。根据矩阵的概念可得：迹=a11+a22; 行列式的值=a11*a22-a12*a21>0
用dp表示两数乘积为i的情况数。sum表示乘积小于等于i的情况数总和。
对于n=2500，最大乘积MAX=n/2*n/2，预处理一下（开始i<N错了我好久）。最后枚举a11的值，a12=n-a11。求乘积小于a11*a12的情况总数即可。
#include<stdio.h>
const int N=2501,MAX=N*N/4;
typedef long long LL;
int dp,sum;
void init(){
for(int i=1;i<MAX;i++){// i<N is wa
for(int j=1;j<MAX;j++){
if(i*j>MAX) break;
dp++;
}
}
for(int i=1;i<MAX;i++){
sum=sum+dp;
}
}
int main(){
init();
int tt,n;
scanf("%d",&tt);
while(tt--){
scanf("%d",&n);
LL ans=0;
for(int i=1;i<n;i++){//枚举a11
int mul=i*(n-i);//取值范围是1-n*n/4
ans+=(LL)sum;
}
printf("%lld\n",ans);
}
}
页:
[1]