結果

問題 No.2705 L to R Graph (Another ver.)
ユーザー maksimmaksim
提出日時 2024-03-29 23:38:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,021 ms / 3,000 ms
コード長 2,182 bytes
コンパイル時間 1,555 ms
コンパイル使用メモリ 171,880 KB
実行使用メモリ 22,336 KB
最終ジャッジ日時 2024-03-29 23:39:56
合計ジャッジ時間 74,624 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,616 KB
testcase_01 AC 2 ms
7,616 KB
testcase_02 AC 2 ms
7,616 KB
testcase_03 AC 2 ms
7,616 KB
testcase_04 AC 2 ms
7,616 KB
testcase_05 AC 2 ms
7,616 KB
testcase_06 AC 3 ms
7,616 KB
testcase_07 AC 2 ms
7,616 KB
testcase_08 AC 1,410 ms
18,880 KB
testcase_09 AC 1,702 ms
20,672 KB
testcase_10 AC 1,066 ms
16,704 KB
testcase_11 AC 1,279 ms
18,112 KB
testcase_12 AC 800 ms
15,040 KB
testcase_13 AC 391 ms
11,968 KB
testcase_14 AC 1,588 ms
19,968 KB
testcase_15 AC 101 ms
9,024 KB
testcase_16 AC 803 ms
15,168 KB
testcase_17 AC 259 ms
10,816 KB
testcase_18 AC 1,496 ms
19,392 KB
testcase_19 AC 599 ms
13,632 KB
testcase_20 AC 324 ms
11,456 KB
testcase_21 AC 1,197 ms
17,600 KB
testcase_22 AC 1,178 ms
17,472 KB
testcase_23 AC 1,880 ms
21,568 KB
testcase_24 AC 1,896 ms
21,696 KB
testcase_25 AC 1,875 ms
21,440 KB
testcase_26 AC 1,909 ms
21,824 KB
testcase_27 AC 1,806 ms
21,056 KB
testcase_28 AC 1,760 ms
20,928 KB
testcase_29 AC 1,726 ms
20,800 KB
testcase_30 AC 1,797 ms
21,056 KB
testcase_31 AC 1,740 ms
20,928 KB
testcase_32 AC 1,804 ms
20,916 KB
testcase_33 AC 1,758 ms
20,928 KB
testcase_34 AC 1,927 ms
21,824 KB
testcase_35 AC 1,743 ms
20,928 KB
testcase_36 AC 1,911 ms
21,696 KB
testcase_37 AC 1,957 ms
22,080 KB
testcase_38 AC 1,745 ms
20,928 KB
testcase_39 AC 1,926 ms
21,568 KB
testcase_40 AC 1,838 ms
21,440 KB
testcase_41 AC 2,008 ms
22,208 KB
testcase_42 AC 1,910 ms
21,440 KB
testcase_43 AC 1,992 ms
22,336 KB
testcase_44 AC 2,019 ms
22,336 KB
testcase_45 AC 1,991 ms
22,336 KB
testcase_46 AC 2,016 ms
22,336 KB
testcase_47 AC 2,021 ms
22,336 KB
testcase_48 AC 1,993 ms
22,336 KB
testcase_49 AC 2,013 ms
22,336 KB
testcase_50 AC 1,993 ms
22,336 KB
testcase_51 AC 2,013 ms
22,336 KB
testcase_52 AC 2,015 ms
22,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
const int inf=1e18;
int p;
int po(int a,int b) {if(b==0) {return 1;} if(b==1) {return a;} if(b%2==0) {int u=po(a,b/2);return (u*u)%p;} else {int u=po(a,b-1);return (a*u)%p;}}
int inv(int x) {return po(x,p-2);}
const int maxn=1e5+5;
int arr[maxn];int f[maxn];
vector<int> di[maxn];
int wa[maxn];int mem[maxn];
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n>>p;
    for(int i=1;i<=n;++i) {for(int j=i;j<=n;j+=i) {di[j].app(i);}}
    int answ=0;
    for(int i=0;i<=n;++i)
    {
        if(i==0) {f[i]=n*(n+1)/2;continue;}
        f[i]=0;
        answ=0;
        for(int l=1;l<=i;)
        {
            int k=i/l;
            int l2=i/k+1;
            int r=max(l,(i+k-1)/k);
            if(r<=n) {mem[l]=n-r+1;answ+=mem[l]*(l2-l);l=l2;}
        }
        f[i]=answ;
    }
    int invn=inv(n);
    int cur=1;for(int i=0;i<n-1;++i) {cur*=n;cur%=p;}
    arr[0]=cur;
    for(int i=0;i<n-1;++i)
    {
        cur*=invn;cur%=p;cur*=(n-i-1);cur%=p;
        arr[i+1]=cur;
    }
    for(int i=n-1;i>=0;--i) {arr[i]+=arr[i+1];arr[i]%=p;}
    int res=0;
    for(int len=1;len<=n;++len)
    {
        int ways=arr[len-1];
        res+=((len*((n*(n-1)/2)%p))%p)*ways;res%=p;
        reverse(all(di[len]));
        for(int u:di[len])
        {
            wa[u]=n/u;
            for(int v:di[len])
            {
                if(v>u && v%u==0)
                {
                    wa[u]-=wa[v];
                }
            }
            res+=(((len/u)*wa[u])%p)*ways;res%=p;
        }
    }
    for(int i=0;i<n;++i) {arr[i]=arr[i+1];}
    for(int i=n-1;i>=0;--i) {arr[i]+=arr[i+1];arr[i]%=p;}
    for(int i=0;i<=n-1;++i)
    {
        int ways=arr[i];
        res+=f[i]*ways;res%=p;
    }
    int c=1;for(int i=0;i<n;++i) {c*=n;c%=p;} c*=((n*(n+1)/2)%p);c%=p;
    res-=c;
    cout<<((n*res)%p+p)%p;
    return 0;
}
0