QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21620 | #2841. 赛艇 | Mr_Eight# | WA | 510ms | 189740kb | C++14 | 14.5kb | 2022-03-07 16:56:58 | 2022-05-08 03:43:21 |
Judging History
answer
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
template<class T>
inline void read(T &x) {
x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
if(fu)x=-x;
}
inline int read() {
int x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
return fu?-x:x;
}
template<class T,class... Args>
inline void read(T& t,Args&... args) {
read(t);
read(args...);
}
char _n_u_m_[40];
template<class T>
inline void write(T x ) {
if(x==0) {
putchar('0');
return;
}
T tmp = x > 0 ? x : -x ;
if( x < 0 ) putchar('-') ;
register int cnt = 0 ;
while( tmp > 0 ) {
_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
tmp /= 10 ;
}
while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
}
template<class T>
inline void write(T x ,char ch) {
write(x);
putchar(ch);
}
}
using namespace fastIO;
#define mod 998244353
#define MOD mod
#define P mod
#define inv2 499122177
#define EXP 1
//快速幂
inline long long pw(long long x,long long p) {
long long res=1;
for(; p; p>>=1,x=x*x%mod)
if(p&1)res=res*x%mod;
return res;
}
//分数取模
inline long long getm(long long top,long long bot) {
return (top*pw(bot,mod-2))%mod;
}
namespace getinv {
int *inv,*fac,*ifac;//逆元,阶乘,阶乘逆元
//预处理逆元函数,若需使用多项式积分/ln/exp/快速幂等,则需在main函数开头调用
void init_inv(int n) {
inv=new int[n+1];
inv[0]=1;
inv[1]=1;
for(register int i=2; i<=n; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
//预处理逆元,阶乘,阶乘逆元
void init_inv_with_fac(int n) {
inv=new int[n+1];
fac=new int[n+1];
ifac=new int[n+1];
inv[0]=fac[0]=ifac[0]=1;
inv[1]=1;
for(register int i=2; i<=n; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(register int i=1; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;
for(register int i=1; i<=n; ++i) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
}
}
using namespace getinv;
namespace Poly {
int *w[30];//单位根
//预处理单位根函数,需在main函数开头调用
void NTT_set(int MAXN) {
for(int i=2,t=0; i<2*MAXN; i<<=1,t++) {
w[t]=new int[i>>1];
ll wn=pw(3,(MOD-1)/i);
w[t][0]=1;
for(int j=1; j<(i>>1); j++) w[t][j]=w[t][j-1]*wn%MOD;
}
}
struct poly {
vector<int>a;//f=a[0]+a[1]*x+a[2]*x^2+...+a[n]*x^n
//n次多项式size为n,其中a.size()=n+1
/*--------------------构造函数--------------------*/
poly() {
}
poly(int sz) {
a.resize(sz+1);
}
#if __cplusplus >= 201103L
poly(initializer_list<int>x) {
a=x;
}
#endif
poly(vector<int>vec) {
a=vec;
}
template<class T>
poly(T s,T t) {
//含左边界,不含右边界
a=vector<int>(s,t);
}
poly(const poly &x) {
a=x.a;
}
/*--------------------基本操作--------------------*/
inline int size() {
return a.size()-1;
}
inline void resize(int x) {
a.resize(x+1);
}
inline int& operator[](int pos) {
return a[pos];
}
inline poly subpoly(int l,int r) {
//含左边界,不含右边界
return poly(&a[l],&a[r]);
}
/*--------------------快速数论变换--------------------*/
//NTT变换
inline void NTT() {
int N=a.size(),len=1;//N=多项式次数+1
while(len<N)len<<=1;
if(N<len) {
resize(len-1);
}
unsigned ll A[len];
F(i,0,len-1)A[i]=a[i];
register int j=len>>1;
for(register int i=1; i<len-1; i++) {
if (i<j) swap(A[i],A[j]);
int k=len>>1;
while (j>=k) {
j-=k;
k>>=1;
}
j+=k;
}
for(register int i=2,t=0; i<=len; i<<=1,t++) {
if(t==17)for(register int j=0; j<len; ++j)A[j]%=MOD;
for(register int j=0; j<len; j+=i)
for(register int k=j; k<j+(i>>1); k++) {
unsigned ll u=A[k];
unsigned ll v=w[t][k-j]*A[k+(i>>1)]%MOD;
A[k]=u+v;
A[k+(i>>1)]=u-v+mod;
}
}
F(i,0,len-1)a[i]=A[i]%mod;
}
//NTT逆变换
inline void UNTT() {
int N=a.size(),len=1;//N=多项式次数+1
while(len<N)len<<=1;
if(N<len) {
resize(len-1);
}
unsigned ll A[len];
F(i,0,len-1)A[i]=a[i];
register int j=len>>1;
for(register int i=1; i<len-1; i++) {
if (i<j) swap(A[i],A[j]);
int k=len>>1;
while (j>=k) {
j-=k;
k>>=1;
}
j+=k;
}
for(register int i=2,t=0; i<=len; i<<=1,t++) {
if(t==17)for(register int j=0; j<len; ++j)A[j]%=MOD;
for(register int j=0; j<len; j+=i)
for(register int k=j; k<j+(i>>1); k++) {
unsigned ll u=A[k];
unsigned ll v=w[t][k-j]*A[k+(i>>1)]%MOD;
A[k]=u+v;
A[k+(i>>1)]=u-v+mod;
}
}
reverse(A+1,A+len);
ll nev=pw(len,MOD-2);
for(int i=0; i<len; i++) a[i]=(A[i]%MOD)*nev%MOD;
}
/*--------------------多项式运算--------------------*/
//多项式加法
inline poly operator+(poly b) {
register int n=size(),bn=b.size();
if(n>=bn) {
poly rt(a);
for(register int i=0; i<=bn; ++i)rt.a[i]=(a[i]+b.a[i])%mod;
return rt;
}
poly rt(b);
for(register int i=0; i<=n; ++i)rt.a[i]=(a[i]+b.a[i])%mod;
return rt;
}
//多项式减法
inline poly operator-(poly b) {
register int n=size(),bn=b.size();
if(n>=bn) {
poly rt(a);
for(register int i=0; i<=bn; ++i)rt.a[i]=(a[i]-b.a[i]+mod)%mod;
return rt;
}
poly rt(bn);
for(register int i=0; i<=n; ++i)rt.a[i]=(a[i]-b.a[i]+mod)%mod;
for(register int i=n+1; i<=bn; ++i)rt.a[i]=(mod-b.a[i])%mod;
return rt;
}
//负多项式
inline poly operator-() {
register int n=size();
poly rt(n);
for(register int i=0; i<=n; ++i)rt.a[i]=(mod-a[i])%mod;
return rt;
}
//多项式乘法
inline poly operator*(poly b) {
int n=size(),bn=b.size();
int len=n+bn;
if(1ll*n*bn<=10000) {
poly rt(len);
for(register int i=0; i<=n; ++i) {
for(register int j=0; j<=bn; ++j) {
rt.a[i+j]=(rt.a[i+j]+1ll*a[i]*b.a[j])%mod;
}
}
return rt;
}
poly A(a),B(b.a);
A.resize(len);
B.resize(len);
A.NTT();
B.NTT();
poly rt(A.size());
for(register int i=0; i<=A.size(); ++i)rt.a[i]=1ll*A.a[i]*B.a[i]%mod;
rt.UNTT();
rt.resize(len);
return rt;
}
//多项式乘法(保留次数为左侧多项式次数)
inline poly operator&(poly b) {
int n=size(),bn=b.size();
int len=n+bn;
if(1ll*n*bn<=10000) {
poly rt(n);
for(register int i=0; i<=n; ++i) {
for(register int j=0; j<=min(bn,n-i); ++j) {
rt.a[i+j]=(rt.a[i+j]+1ll*a[i]*b.a[j])%mod;
}
}
return rt;
}
poly A(a),B(b.a);
A.resize(len);
B.resize(len);
A.NTT();
B.NTT();
poly rt(A.size());
for(register int i=0; i<=A.size(); ++i)rt.a[i]=1ll*A.a[i]*B.a[i]%mod;
rt.UNTT();
rt.resize(n);
return rt;
}
//多项式卷积的转置运算(res[i-j]+=f[i]*g[j])
inline poly operator^(poly b) {
poly temp=b.rev();
temp=(*this)*temp;
temp.a.erase(temp.a.begin(),temp.a.begin()+b.size());
return temp;
}
//多项式求逆
inline poly inv() {
if(size()==0) {
return poly(vector<int>(1,getm(1,a[0])));
}
poly sub(size()>>1),temp;
int ss=sub.size();
for(register int i=0; i<=ss; ++i)sub.a[i]=a[i];
sub=sub.inv();
temp=(*this)&(sub*sub);
F(i,0,ss)sub[i]=(sub[i]<<1)%mod;
return sub-temp;
}
//多项式开根(需保证多项式常数项为1)
inline poly sqrt() {
if(size()==0) {
return poly(vector<int>(1,1));
}
poly sub(size()>>1);
int ss=sub.size();
for(register int i=0; i<=ss; ++i)sub.a[i]=a[i];
sub=sub.sqrt();
sub.resize(size());
sub=((*this)&sub.inv())+sub;
ss=size();
for(register int i=0; i<=ss; ++i)sub.a[i]=1ll*sub.a[i]*inv2%mod;
return sub;
}
//多项式系数翻转
inline poly rev() {
poly rt(a);
reverse(rt.a.begin(),rt.a.end());
return rt;
}
//多项式除法
inline poly operator/(poly b) {
if(b.size()>size())return poly();
poly temp=b.rev();
temp.resize(size());
poly rt=rev()&temp.inv();
rt.resize(size()-b.size());
return rt.rev();
}
//多项式取模
inline poly operator%(poly b) {
if(b.size()>size())return *this;
poly rt=(*this)-(*this)/b*b;
rt.resize(b.size()-1);
return rt;
}
//多项式求导
inline poly dev() {
int n=size();
poly rt(n-1);
for(register int i=1; i<=n; ++i)rt.a[i-1]=1ll*i*a[i]%mod;
return rt;
}
//多项式积分
inline poly inter() {
int n=size();
poly rt(n+1);
for(register int i=0; i<=n; ++i)rt.a[i+1]=1ll*a[i]*getinv::inv[i+1]%P;
return rt;
}
//多项式积分(舍弃最高位)
inline poly inter2() {
int n=size();
poly rt(n);
for(register int i=0; i<n; ++i)rt.a[i+1]=1ll*a[i]*getinv::inv[i+1]%P;
return rt;
}
//多项式对数函数(需常数项为1)
inline poly ln() {
return (inv()&dev()).inter2();
}
//分治求解多项式指数函数子函数:分治FFT
inline void exp_solve(int l,int r,vector<int> &op,int rr) {
if(l==r)return;
int mid=(l+r)>>1;
exp_solve(l,mid,op,rr);
if(mid>=rr)return;
poly sub(a.begin(),a.begin()+r-l+1),temp(op.begin()+l,op.begin()+mid+1);
sub=sub&temp;
for(int i=mid-l+1,iend=min(r,rr)-l; i<=iend; ++i)op[i+l]=(op[i+l]+1ll*getinv::inv[i+l]*sub[i])%mod;
exp_solve(mid+1,r,op,rr);
}
//分治求解多项式指数函数(需常数项为0)(复杂度O(nlog^2n),常数较小,实测比牛顿迭代略快)
#if EXP==1
inline poly exp() {
#else
inline poly exp2() {
#endif
unsigned int k=1;
int temp=a.size();
while(k<a.size())k<<=1;
a.resize(k);
for(int i=1; i<temp; ++i)a[i]=1ll*a[i]*i%mod;
vector<int>res(a.size(),0);
res[0]=1;
exp_solve(0,size(),res,temp-1);
for(int i=1; i<temp; ++i)a[i]=1ll*a[i]*getinv::inv[i]%mod;
a.resize(temp);
res.resize(temp);
return poly(res);
}
//牛顿迭代求解多项式指数函数(需常数项为0)(复杂度O(nlogn),常数较大)
#if EXP!=1
inline poly exp() {
#else
inline poly exp2() {
#endif
if(size()==0) {
return poly(vector<int>(1,1));
}
poly sub(size()>>1),temp;
int ss=sub.size();
for(register int i=0; i<=ss; ++i)sub.a[i]=a[i];
sub=sub.exp();
temp=sub;
temp.resize(size());
temp=*this-temp.ln();
temp.a[0]=(temp.a[0]+1)%mod;
return temp⊂
}
/*--------------------多项式功能--------------------*/
//多项式快速幂(x为指数)
inline poly power(ll x) {
vector<int>temp=a;
int t1=0,t2=0,n=size();
for(register int i=0; i<=n; ++i) {
if(a[i]) {
t1=i,t2=a[i];
for(register int j=i; j<=n; ++j)a[j]=getm(a[j],t2);
a.erase(a.begin(),a.begin()+i);
break;
}
}
if((x>=mod&&t1)||!t2) {
a=temp;
return poly(n);
}
ll xx=x%(mod-1);
x%=mod;
if(t1*x>n) {
a=temp;
return poly(n);
}
t2=pw(t2,xx);
*this=ln();
for(register int i=0; i<=n; ++i)a[i]=a[i]*x%mod;
*this=exp();
for(register int i=0; i<=n; ++i)a[i]=1ll*a[i]*t2%mod;
a.insert(a.begin(),t1*x,0);
swap(a,temp);
return temp;
}
//多项式快速幂(x为指数对mod取模的结果,xx为指数对mod-1取模的结果)
inline poly power(ll x,ll xx,bool exc=false) {
vector<int>temp=a;
int t1=0,t2=0,n=size();
for(register int i=0; i<=n; ++i) {
if(a[i]) {
t1=i,t2=a[i];
for(register int j=i; j<=n; ++j)a[j]=getm(a[j],t2);
a.erase(a.begin(),a.begin()+i);
break;
}
}
if((exc&&t1)||t1*x>n||!t2) {
a=temp;
return poly(n);
}
t2=pw(t2,xx);
*this=ln();
for(register int i=0; i<=n; ++i)a[i]=a[i]*x%mod;
*this=exp();
for(register int i=0; i<=n; ++i)a[i]=1ll*a[i]*t2%mod;
a.insert(a.begin(),t1*x,0);
swap(a,temp);
return temp;
}
//多项式多点求值子函数一;求每段多项式乘积
inline void multieva_getpoly(int *bg,int *ed,int p,poly *op) {
if(bg+1==ed) {
op[p]=poly(1);
op[p][1]=1;
op[p][0]=mod-*bg;
return;
}
multieva_getpoly(bg,bg+((ed-bg)>>1),p<<1,op);
multieva_getpoly(bg+((ed-bg)>>1),ed,p<<1|1,op);
op[p]=op[p<<1]*op[p<<1|1];
}
//多项式多点求值子函数二:进行分治求解
inline void multieva_solve(int *bg,int *ed,poly *mul,int p,int *op) {
if(bg+1==ed) {
*op=a[0];
return;
}
poly t1=(*this)%mul[p<<1],t2=(*this)%mul[p<<1|1];
t1.multieva_solve(bg,bg+((ed-bg)>>1),mul,p<<1,op);
t2.multieva_solve(bg+((ed-bg)>>1),ed,mul,p<<1|1,op+((ed-bg)>>1));
}
//多项式多点求值
inline void multieva(int *bg,int *ed,int *op) {
vector<poly>temp((ed-bg+1)<<2);
multieva_getpoly(bg,ed,1,&temp[0]);
multieva_solve(bg,ed,&temp[0],1,op);
}
} f,g;
//多个多项式相乘
template<class T>
inline poly multi(T bg,T ed) {
//含左边界,不含右边界
if(bg+1==ed)return *bg;
return multi(bg,bg+((ed-bg)>>1))*multi(bg+((ed-bg)>>1),ed);
}
}
using namespace Poly;
bool vis[3002][1502];
int x=1500,y=0,n,m,k;
inline char orz(){
char ch=getchar();
while(ch!='0'&&ch!='1'&&(ch<'a'||ch>'z'))ch=getchar();
return ch;
}
int main() {
NTT_set(10500000);
cin>>n>>m>>k;
g.resize((n+1505)*m*2);
f.resize(g.size());
for(auto &i:f.a)i=1;
F(i,1,n)F(j,1,m){
f[i*m*2+j]=orz()-'0';
}
g[x*m*2+y]=1;
F(i,1,k){
char ch=orz();
if(ch=='a')++x;
else if(ch=='d')--x;
else if(ch=='w')++y;
else --y;
g[x*m*2+y]=1;
}
f=f*g;
int ans=0;
F(i,1500+1,1500+n)F(j,1,m)ans+=(f[i*m*2+j]==0);
cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 60ms
memory: 69696kb
input:
5 5 5 00000 10000 00000 00000 01001 awdsw
output:
11
result:
ok single line: '11'
Test #2:
score: -100
Wrong Answer
time: 510ms
memory: 189740kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
77289
result:
wrong answer 1st lines differ - expected: '77549', found: '77289'