救命呀DEV能过但是全是WA 不知道测试点 实在找不出错误

Sukidayo @ 2021-01-09 15:51:54

#include<bits/stdc++.h>
using namespace std;
int check(int *a,int n){
    int sum=0;
    for(int i=1000;i>0;i--){
        if(a[i]==-1){
            break;
        } 
        else if(a[i]==n){
            sum++;
        }  
    }
    return sum;
}

void compute(int n,int *ans){
    for(int i=0;i<1000;i++)
        ans[i]=0;
    ans[1000]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<1001;j++){
           ans[j]=ans[j]*i;
        }
        for(int j=1000;j>0;j--){
           if(ans[j]>9){
            ans[j-1]=ans[j-1]+ans[j]/10;
            ans[j]=ans[j]%10;
           }
        }
    }
    for(int i=0;i<1001;i++){
        if(ans[i]!=0){
            ans[i-1]=-1;
            break;
        }
    }
}
int main(){
    int t,a,b;
    cin>>t;
    static int c[1001]={0};
    for(int i=0;i<t;i++){
        cin>>a>>b;
        compute(a,c);
        cout<<check(c,b)<<endl; 
    }
    return 0;
}

by wsyhb @ 2021-01-09 16:21:10

@Sukidayo 注意 n! 的位数不为 n，其位数的粗略计算方法如下：

当 n \le 1000 时，n! \le 1000! = (1 \cdot 2 \cdot \cdots \cdot 10) \cdot (11 \cdot 12 \cdot \cdots \cdot 100) \cdot (101 \cdot 102 \cdot \cdots \cdot 1000) < 10^{10} \cdot (10^2)^{90} \cdot (10^3)^{900}=10^{2890}<10^{3000}。

因此 3000 位绰绰有余，当然，你也可以一开始就开 10000，然后根据实际结果开对应大小的数组。

修改后代码如下：

#include<bits/stdc++.h>
using namespace std;
int check(int *a,int n){
    int sum=0;
    for(int i=3000;i>0;i--){
        if(a[i]==-1){
            break;
        } 
        else if(a[i]==n){
            sum++;
        }  
    }
    return sum;
}

void compute(int n,int *ans){
    for(int i=0;i<3000;i++)
        ans[i]=0;
    ans[3000]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<3001;j++){
           ans[j]=ans[j]*i;
        }
        for(int j=3000;j>0;j--){
           if(ans[j]>9){
            ans[j-1]=ans[j-1]+ans[j]/10;
            ans[j]=ans[j]%10;
           }
        }
    }
    for(int i=0;i<3001;i++){
        if(ans[i]!=0){
            ans[i-1]=-1;
            break;
        }
    }
}
int main(){
    int t,a,b;
    cin>>t;
    static int c[3001]={0};
    for(int i=0;i<t;i++){
        cin>>a>>b;
        compute(a,c);
        cout<<check(c,b)<<endl; 
    }
    return 0;
}

上述代码已 AC。

by wsyhb @ 2021-01-09 16:22:41

公式太长而被吞的部分：=10^{2890}<10^{3000}

by Sukidayo @ 2021-01-10 11:25:33

@wsyhb 谢谢你！非常感谢！

by justinjia @ 2021-01-12 10:56:21