結果
問題 | No.950 行列累乗 |
ユーザー |
![]() |
提出日時 | 2019-12-13 23:04:12 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,827 bytes |
コンパイル時間 | 2,828 ms |
コンパイル使用メモリ | 200,016 KB |
実行使用メモリ | 24,232 KB |
最終ジャッジ日時 | 2024-06-27 20:15:09 |
合計ジャッジ時間 | 7,162 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 WA * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:236:18: warning: ‘w’ may be used uninitialized in this function [-Wmaybe-uninitialized] 236 | ll y=b[h][w]*gyaku(a[h][w],mod); | ^
ソースコード
#include<bits/stdc++.h> //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<pii,int> ppii; typedef pair<int,pii> pipi; typedef pair<ll,ll> pll; typedef pair<pll,ll> ppll; typedef pair<ll,pll> plpl; typedef tuple<ll,ll,ll> tl; ll mod; ll mod2=998244353; ll mod3=1000003; ll mod4=998244853; ll inf=1000000000; double pi=2*acos(0); #define rep(i,m,n) for(ll i=m;i<n;i++) #define rrep(i,n,m) for(ll i=n;i>=m;i--) int dh[4]={1,-1,0,0}; int dw[4]={0,0,1,-1}; int ddh[8]={-1,-1,-1,0,0,1,1,1}; int ddw[8]={-1,0,1,-1,1,-1,0,1}; ll lmax(ll a,ll b){ if(a<b)return b; else return a; } ll lmin(ll a,ll b){ if(a<b)return a; else return b; } ll gcd(ll a,ll b){ if(a<b)swap(a,b); if(b==0)return a; if(a%b==0)return b; return gcd(b,a%b); } ll Pow(ll n,ll k){ ll ret=1; ll now=n; while(k>0){ if(k&1)ret*=now; now*=now; k/=2; } return ret; } ll beki(ll n,ll k,ll md){ ll ret=1; ll now=n; while(k>0){ if(k%2==1){ ret*=now; ret%=md; } now*=now; now%=md; k/=2; } return ret; } ll gyaku(ll n,ll md){ return beki(n,md-2,md); } vector<vector<ll>> matmul(vector<vector<ll>> a,vector<vector<ll>> b){ ll n=a.size(); vector<vector<ll>> ret; vector<ll> e; rep(i,0,n)e.push_back(0); rep(i,0,n)ret.push_back(e); rep(i,0,n){ rep(j,0,n){ ll sum=0; rep(k,0,n){ sum+=(a[i][k]*b[k][j])%mod; sum%=mod; } ret[i][j]=sum; } } return ret; } vector<vector<ll>> matbeki(vector<vector<ll>> a,ll n){ vector<vector<ll>> ret; ll m=a.size(); vector<ll> e; rep(i,0,m)e.push_back(0); rep(i,0,m)ret.push_back(e); rep(i,0,m){ rep(j,0,m){ if(i==j)ret[i][j]=1; else ret[i][j]=0; } } while(n>0){ if(n%2){ ret=matmul(ret,a); } a=matmul(a,a); n/=2; } return ret; } int main(){ ios::sync_with_stdio(false);cin.tie(0); ll p;cin>>p; mod=p; vector<vector<ll>> a,b; rep(i,0,2){ vector<ll> v; rep(j,0,2){ ll r;cin>>r; v.push_back(r); } a.push_back(v); } rep(i,0,2){ vector<ll> v; rep(j,0,2){ ll r; cin>>r; v.push_back(r); } b.push_back(v); } ll u=(a[0][0]*a[1][1])%mod-(a[0][1]*a[1][0])%mod+mod; ll uu=(b[0][0]*b[1][1])%mod-(b[0][1]*b[1][0])%mod+mod; u%=mod; uu%=mod; if(u!=0){ ll mm=0; while(mm*mm<p)mm++; unordered_map<ll,ll> mp; ll now=1; rep(i,0,mm){ if(mp[now]==0)mp[now]=i+1; if(i==0&&uu==1)mp[now]=0; now*=u; now%=mod; } ll g=gyaku(u,mod); g=beki(g,mm,mod); now=uu; ll m=inf; rep(i,0,mm){ if(mp[now]!=0){ if(i*mm+mp[now]-1>=1){ m=min(m,i*mm+mp[now]-1); break; } } now=now*g; now%=mod; } if(m==inf){ cout<<-1<<endl; return 0; } // cout<<m<<endl; vector<vector<ll>> c,d; u=gyaku(u,mod); c={{(u*a[1][1])%mod,(u*(-a[0][1]+mod))%mod}, {(u*(-a[1][0]+mod))%mod,(u*a[0][0])%mod}}; /*rep(i,0,2){ rep(j,0,2){ cout<<c[i][j]<<" "; } cout<<endl; }*/ c=matbeki(c,m); c=matmul(c,b); d=matbeki(a,mod-1); mm=1; while(mm*mm<p+1)mm++; // cout<<mm<<endl; map<vector<vector<ll>>,ll> mp2; vector<vector<ll>> noww={{1,0},{0,1}}; rep(i,0,mm){ if(mp2[noww]==0)mp2[noww]=i+1; noww=matmul(noww,d); } ll ud=(d[0][0]*d[1][1])%mod-(d[0][1]*d[1][0])%mod+mod; ud%=mod; ud=gyaku(ud,mod); vector<vector<ll>> gg={{(ud*d[1][1])%mod,(ud*(-d[0][1]+mod))%mod}, {(ud*(-d[1][0]+mod))%mod,(ud*d[0][0])%mod}};; gg=matbeki(gg,mm); noww=c; ll ans=inf; rep(i,0,mm){ if(mp2[noww]!=0){ ans=min(ans,i*mm+mp2[noww]-1); break; } noww=matmul(gg,noww); } if(ans==inf)cout<<-1<<endl; else cout<<ans*(p-1)+m<<endl; } else{ if(uu!=0){ cout<<-1<<endl; return 0; } vector<vector<ll>> k={{0,0},{0,0}}; if((a[0][0]+a[1][1])%mod==0){ if(b==k){ cout<<1<<endl; return 0; } else{ cout<<-1<<endl; return 0; } } ll h=-1,w; rep(i,0,2){ rep(j,0,2){ if(a[i][j]!=0){ h=i; w=j; break; } } if(h>=0)break; } ll g=(a[0][0]+a[1][1])%mod; vector<ll> v; ll y=b[h][w]*gyaku(a[h][w],mod); y%=mod; //cout<<y<<" "<<h<<" "<<w<<endl; map<ll,vector<ll>> mp; ll m=0; while(m*m<p)m++; //cout<<g<<endl; ll now=1; rep(i,0,m){ // cout<<now<<endl; mp[now].push_back(i+1); now*=g; now%=mod; } ll t=gyaku(g,mod); t=beki(t,m,mod); now=y; rep(i,0,m){ rep(j,0,mp[now].size()) v.push_back(i*m+mp[now][j]-1); now*=t; now%=mod; } rep(i,0,v.size()){ // cout<<v[i]<<endl; //if(v[i]==0)continue; vector<vector<ll>> w=matbeki(a,v[i]+1); // rep(j,0,2)cout<<w[j][0]<<" "<<w[j][1]<<endl; if(w==b){ cout<<v[i]+1<<endl; return 0; } } cout<<-1<<endl; } }