結果
問題 |
No.2362 Inversion Number of Mod of Linear
|
ユーザー |
|
提出日時 | 2025-04-23 19:02:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,033 bytes |
コンパイル時間 | 1,848 ms |
コンパイル使用メモリ | 195,252 KB |
実行使用メモリ | 16,072 KB |
最終ジャッジ日時 | 2025-04-23 19:02:25 |
合計ジャッジ時間 | 5,241 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | WA * 1 TLE * 1 -- * 6 |
ソースコード
#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; assert(a>=0&&b>=0); ll A=a,B=b; if(p==0&&q==1){ ll a1=a/m,b1=b/m; a%=m,b%=m; res=n*(n-1)/2*a1+n*b1; 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(1||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; }