c - 有多少矩阵的迹等于 givan 迹？

Question

我已经给出了矩阵的“n”迹。我想知道有多少矩阵(仅 2*2 阶)的迹等于“n”，并且所有矩阵必须 positive invertible ，即它们的行列式必须大于 '0'。

For ex:
trace=3
No.of matrices=2

trace=4
No.of matrices=11

trace=5
No.of matrices=30

我已经为此编写了一个代码，但效率不高，因为我的代码成功地为 n=1500 提供了输出，之后我就超出了时间限制。谁能帮我？

我的代码是:

#include<stdio.h>

int main()
{
    int t,n,nsot,i,j,l;
    int arr[2000],k;
    unsigned long long  sum1=0,sum2=0,sum=0;
    scanf("%d",&t);
    while(t--)
    {
        sum1=0;
        sum2=0;
        //sum=0;
        scanf("%d",&n);
        nsot=n/2;
        for(i=1;i<=nsot;i++)
        {
            arr[i]=i*(n-i);
            //printf("%d ",arr[i]);
            sum1=0;
                for(k=1;k<arr[i];k++)
                {
                    //printf("%f\n",ceil(arr[i]/k));
                    sum1=sum1+((arr[i] - 1) / k);

                }
                if(i==(n-i))
            sum=sum1;
            else
            sum=0;

            //printf("%d\n",sum);
            //printf("%llu",sum2);
            sum2=sum1+sum2;
        }
        printf("%llu\n",(2*sum2)-sum);
    }
}

Answer 1

所以我猜你想要正矩阵元素和行列式 > 0。

轨迹的可能值为[1, n - 1]； [2, n - 2] ...，所以 n -1 值。

对于这些(O(n) 次检查)中的每一个，我们将检查我们可以用多少种方式来填充矩阵的剩余元素，以使行列式保持正值。

令矩阵为:

a1 a3
a4 a2

然后行列式是 a1*a2 - a3*a4。对于固定的 a1 和 a2，将 a3 从 1 迭代到 n - 1 .然后你必须解决:

a1*a2 - x*a4 > 0
a1*a2 > x*a4
x < a1*a2 / a4

所以你可以在O(1) => 总复杂度O(n^2)中找到x，应该很快.

这似乎是您正在做的，除了您的最内层循环使其成为 O(n^3)(您还迭代了 x):

l=1;
while(k*l<arr[i])
{
    sum1++; 
    l++;
}

假设 k = 10 和 arr[i] = 103。 l 最后会是什么？你能找到 10、103 和 l 的最终值之间的关系吗？那将是你的公式。