結果

問題 No.3187 Mingle
ユーザー GGanari
提出日時 2025-07-25 15:08:00
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,717 bytes
コンパイル時間 9,244 ms
コンパイル使用メモリ 170,312 KB
実行使用メモリ 322,596 KB
最終ジャッジ日時 2025-07-25 15:08:23
合計ジャッジ時間 11,840 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define INF 1000000001LL
#define LNF 1000000000000000001LL
#define MAX 200000
#define long long long
#define all(x) x.begin(),x.end()
using namespace std;

long MOD;

int dp[301][300001];
long power(long a, long b)
{
    if(b == 1)
        return a;
    long c = power(a,b/2);
    if(b&1)
        return (((c*c)%MOD)*a)%MOD;
    else
        return ((c*c)%MOD);
}

long modinv(long k)
{
    return power(k,MOD-2);
}
int main()
{
	ios_base::sync_with_stdio(0); 
    cin.tie(0);
    

    int n,p;
    cin >> n >> p;
    MOD = p;

    for(int i =3; i<=n; i++)
    {
        int cur = 1;
        // 1~n j , dp[i-(i%j)]
        long res = 0;
        int cnt = 0;
        while(cur <= i)
        {
            int p = i/cur;
            
            if(p <= 300)
            {
                int next = i/p;
                int s = i-i%cur;
                int e = i-i%next;
                if(i%next == 0)
                {
                    cnt++;
                    e-=p;
                }
                if(e >= s)
                    res+=(dp[p][e]-dp[p][max(0,s-p)]+MOD);
                cur = next+1;

            }
            else
            {
                if(i%cur == 0)
                    cnt++;
                res+=dp[0][i-i%cur];
                cur++;
            }
        }
        long modN = modinv(i);
        res%=MOD;

        dp[0][i] = (((res*modN+1)%MOD)*modinv((i-cnt) * modN%MOD))%MOD;

        for(int j = 1; j<=300; j++)
            dp[j][i] = (dp[j][max(0,(i-j))]+dp[0][i])%MOD;
    }

    cout << dp[0][n] << endl;
    return 0;
}
0