QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#800870#9553. The HermitPepinotTL 0ms0kbC++231.6kb2024-12-06 16:21:392024-12-06 16:21:40

Judging History

你现在查看的是最新测评结果

  • [2024-12-06 16:21:40]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-12-06 16:21:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
using pii=pair<int,int>;

const int N=100005,M=100000;
const int mod=998244353;

int n,m;
int f[22][N],cnt[N];

int fac[N],infac[N];

int quick_pow(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

int cc(int a,int b){
    if(b>a) return 0;
    return fac[a] * infac[b] % mod * infac[a - b] % mod;
}

void pre(){
     fac[0]=infac[0]=1;
     for(int i=1;i<=M;i++)
     {
         fac[i]=fac[i-1]*i%mod;
         infac[i]=infac[i - 1] * quick_pow(i,mod-2,mod)%mod;
     }

     //求cnt[i]
    
     for(int i=1; i<=M; i++) {
         int w=i;
         for(int j=2; w!=1; j++) {
             while(w%j==0) {
                 w/=j;
                 cnt[i]++;
             }
         }
         cnt[i]++;
         
     }
     cnt[1]=1;

     // 求f[i][j]
      for(int j=1; j<=M; j++) {
          // cout<<j<<":";
          for(int i=1; i<=cnt[j]; i++) {
              f[i][j]=cc(cnt[j]-1,i-1);
              // cout<<f[i][j]<<" \n"[i==cnt[j]+1];
          }
      }
}

//f[i][j] 表示长度为i,当前数为j的方案数

void solve(){
    cin>>m>>n;

    int ans=0;

    for(int j=1; j<=m; j++) {
        for(int i=1; i<=cnt[j]; i++) {
            ans+=f[i][j]*cc(m/j-1,n-i);
            ans%=mod;
        }
    }

    // cout<<cc(m,n)*n<<" "<<ans<<endl;
    cout<<(cc(m,n)*n-ans)%mod;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);

    pre();

    solve();

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4 3

output:


result: