QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#391979 | #8176. Next TTPC 3 | i_am_noob# | WA | 216ms | 40644kb | C++14 | 4.2kb | 2024-04-16 23:39:13 | 2024-04-16 23:39:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
const int mod=998244353,N=1<<21,G=3;
int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}
int mul(int x, int y){return (ll)x*y%mod;}
int Pow(int x, ll y=mod-2){int res=1; for(; y; y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x); return res;}
struct NTT{
ll w[N];
NTT(){
ll dw=Pow(G,(mod-1)/N);
w[0]=1;
for(int i=1; i<N; ++i) w[i]=mul(w[i-1],dw);
}
void operator()(vector<int> &a, bool inv=false){
int x=0,n=a.size();
for(int j=1; j<n-1; ++j){
for(int k=n>>1; (x^=k)<k; k>>=1);
if(j<x) swap(a[j],a[x]);
}
for(int L=2; L<=n; L<<=1){
int dx=N/L,dl=L>>1;
for(int i=0; i<n; i+=L){
for(int j=i,x=0; j<i+dl; ++j,x+=dx){
int tmp=mul(a[j+dl],w[x]);
a[j+dl]=sub(a[j],tmp);
a[j]=add(a[j],tmp);
}
}
}
if(inv){
reverse(a.begin()+1,a.end());
ll invn=Pow(n);
for(int i=0; i<n; ++i) a[i]=mul(a[i],invn);
}
}
}ntt;
vector<int> mul(vector<int> a, vector<int> b, int bound=N){
int m=a.size()+b.size()-1,n=1;
while(n<m) n<<=1;
a.resize(n),b.resize(n);
ntt(a),ntt(b);
vector<int> out(n);
for(int i=0; i<n; ++i) out[i]=mul(a[i],b[i]);
ntt(out,true),out.resize(min(m,bound));
return out;
}
int n,val1[N],val2[N];
string s[4],t="TTPC";
bool a[N],b[N];
void ahcorz(){
cin >> n; n--;
for(int i=0; i<4; ++i){
string de; cin >> de;
s[i].clear();
for(auto c: de) s[i]+='0'+(c==t[i]);
}
int m1=0,m2=0;
{
int pos1=0,pos2=0;
for(int i=0; i<N; ++i){
a[i]=(s[0][pos1]=='1'&&s[1][pos2]=='1');
pos1++,pos2++;
if(pos1>=sz(s[0])) pos1=0;
if(pos2>=sz(s[1])) pos2=0;
m1++;
if(pos1==0&&pos2==0) break;
}
}
{
int pos1=0,pos2=0;
for(int i=0; i<N; ++i){
b[i]=(s[2][pos1]=='1'&&s[3][pos2]=='1');
pos1++,pos2++;
if(pos1>=sz(s[2])) pos1=0;
if(pos2>=sz(s[3])) pos2=0;
m2++;
if(pos1==0&&pos2==0) break;
}
}
vector<int> P(m1),Q(m2);
//for(int i=0; i<m1; ++i) cout << a[i];
//cout << '\n';
//for(int i=0; i<m2; ++i) cout << b[i];
//cout << '\n';
for(int i=0; i<m1; ++i) P[i]=a[i];
for(int i=0; i<m2; ++i) Q[i]=b[m2-1-i];
vector<int> R=mul(P,Q);
ll M=m1/__gcd(m1,m2)*m2;
memset(val1,-1,sizeof val1),memset(val2,-1,sizeof val2);
for(ll i=0; i<M; i+=m2) val1[i%m1]=i;
for(ll i=0; i<M; i+=m1) val2[i%m2]=i;
vector<pair<ll,ll>> vec;
for(int i=0; i<m1; ++i) if(val1[i]>=0) vec.pb({val1[i],R[i+m2-1]});
for(int i=1; i<m2; ++i) if(val2[i]>=0) vec.pb({val2[i],R[m2-1-i]});
sort(all(vec));
ll tot=0;
for(auto &[x,y]: vec) tot+=y;
if(tot==0){
cout << "-1\n";
return;
}
ll res=M*(n/tot);
n%=tot;
//cout << tot << "\n";
for(auto &[x,y]: vec){
//cout << x << ' ' << y << ' ' << n << "\n";
if(n>=y){
n-=y;
continue;
}
for(int i=0; i<m1; ++i) if(val1[i]==x){
for(int j=0; j<m2; ++j) if(i+j<m1&&a[i+j]&&b[j]){
if(n==0){
res+=x+j;
break;
}
n--;
}
break;
}
for(int i=1; i<m2; ++i) if(val2[i]==x){
for(int j=0; j<m1; ++j) if(i+j<m2&&a[j]&&b[i+j]){
if(n==0){
res+=x+j;
break;
}
n--;
}
break;
}
}
cout << res+1 << "\n";
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int t=1;// cin >> t;
while(t--){
ahcorz();
}
}
详细
Test #1:
score: 100
Accepted
time: 11ms
memory: 39396kb
input:
3 TTPC TLE P AC
output:
34
result:
ok "34"
Test #2:
score: 0
Accepted
time: 9ms
memory: 38492kb
input:
670055 TF OITFKONTO GFPPNPWTZP CCZFB
output:
-1
result:
ok "-1"
Test #3:
score: 0
Accepted
time: 7ms
memory: 39748kb
input:
910359 TOKYO TECH PROGRAMMING CONTEST
output:
1401951321
result:
ok "1401951321"
Test #4:
score: -100
Wrong Answer
time: 216ms
memory: 40644kb
input:
518530 TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...
output:
1919533597525
result:
wrong answer 1st words differ - expected: '518530', found: '1919533597525'