結果

問題 No.2705 L to R Graph (Another ver.)
コンテスト
ユーザー maksim
提出日時 2024-03-29 23:13:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,875 bytes
コンパイル時間 1,572 ms
コンパイル使用メモリ 167,000 KB
実行使用メモリ 8,448 KB
最終ジャッジ日時 2024-09-30 16:51:59
合計ジャッジ時間 6,196 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

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];
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n>>p;
    for(int i=0;i<=n;++i)
    {
        for(int l=1;l<=n;++l)
        {
            for(int r=l;r<=n;++r)
            {
                int k=i/l;
                if(k*r>=i)
                {
                    f[i]++;
                }
            }
        }
    }
    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];
        for(int l=1;l<=n;++l)
        {
            for(int r=l+1;r<=n;++r)
            {
                res+=len*ways;res%=p;
            }
        }
        for(int l=1;l<=n;++l)
        {
            res+=(len/__gcd(l,len))*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