結果

問題 No.2362 Inversion Number of Mod of Linear
コンテスト
ユーザー Ryushi Birender
提出日時 2025-04-23 17:56:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,018 bytes
コンパイル時間 1,919 ms
コンパイル使用メモリ 194,040 KB
実行使用メモリ 11,040 KB
最終ジャッジ日時 2025-04-23 17:56:25
合計ジャッジ時間 5,999 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 1 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &a){
    #define gc getchar()
    char c;a=0;int f=1;
    while(!isdigit(c=gc))if(c=='-')f=-1;
    do a=a*10+c-'0';
    while(isdigit(c=gc));
    a*=f;
}
template<typename T>
void write(T a){
    if(a<0)putchar('-'),a=-a;
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
char GC(){
    char c=getchar();
    while(c<=32)c=getchar();
    return c;
}
template<typename T>
void chmin(T &x,T y){if(x>y)x=y;}
template<typename T>
void chmax(T &x,T y){if(x<y)x=y;}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef pair<ll,int> PLI;
typedef __int128 lll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
namespace GENSOKYO{
ll n,m,a,b;
ll f(int p,int q,ll n,ll m,ll a,ll b){
    ll res=0;
    if(p==0&&q==1){
        ll a1=a/m,b1=b/m;
        a%=m,b%=m;
        res=n*(n-1)/2*a1+n*b1;
        if(a==0)return res;
        ll k=(a*(n-1)+b)/m;
        if(k)res+=k*n-f(0,1,k,a,m,m-b+a-1);
    }else if(p==0&&q==2){
        ll a1=a/m,b1=b/m;
        a%=m,b%=m;
        if(a1||b1){
            res+=a1*a1*(n-1)*n*(2*n-1)/6;
            res+=2*a1*b1*n*(n-1)/2;
            res+=b1*b1*n;
            if(a1)res+=2*a1*f(1,1,n,m,a,b);
            if(b1)res+=2*b1*f(0,1,n,m,a,b);
        }
        ll k=((n-1)*a+b)/m;
        if(k)res+=k*k*n-2*f(1,1,k,a,m,m-b+a-1)-
            f(0,1,k,a,m,m-b+a-1);
    }else if(p==1&&q==1){
        ll a1=a/m,b1=b/m;
        a%=m,b%=m;
        if(a1||b1){
            if(a1)res+=a1*(n-1)*n*(2*n+1)/6;
            if(b1)res+=b1*n*(n-1)/2;
        }
        ll k=((n-1)*a+b)/m;
        if(k)res+=k*n*(n-1)/2+f(0,1,k,a,m,m-b+a-1)/2
            -f(0,2,k,a,m,m-b+a-1)/2;
    }else assert(0);
    return res;
}
void main(){
    cin>>n>>m>>a>>b;
    cout<<2*f(1,1,n,m,a,b)-(n-1)*f(0,1,n,m,a,b)-n*f(0,1,n,m,a,0)+f(1,1,n,m,a,0)<<endl;;
}
}
signed main(){
    int T=1;cin>>T;
    while(T--)GENSOKYO::main();
    return 0;
}
0