Tutorial is loading...
solution
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;
if (n < m) {
cout << "NO\n";
continue;
}
bool same = true;
for (int i = 1; i < b.size(); ++i) {
if (a[i + n - m] != b[i]) {
same = false;
break;
}
}
if (!same) {
cout << "NO\n";
continue;
}
for (int i = 0; i < n - m + 1; ++i) {
if (a[i] == b[0]) {
same = false;
}
}
if (same) {
cout << "NO\n";
}
else {
cout << "YES\n";
}
}
}
Tutorial is loading...
solution
#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <map>
#include <chrono>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <memory>
#include <cstdio>
#include <assert.h>
#include <iostream>
const int MAXN = 300005;
int numbers[MAXN];
int main() {
int t;
int n, x;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &x);
for (int i = 1; i <= n; i++) {
scanf("%d", &numbers[i]);
}
int num_min = numbers[1];
int num_max = numbers[1];
int res = 0;
for (int i = 2; i <= n; i++) {
if (numbers[i] > num_max) {
num_max = numbers[i];
}
if (numbers[i] < num_min) {
num_min = numbers[i];
}
if (num_max - num_min > 2 * x) {
res++;
num_min = num_max = numbers[i];
}
}
printf("%d\n", res);
}
return 0;
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int N = 500005, inf = 2147483647, M = 1004535809;
int n, m, a[N], T, k;
struct str {
int x, y;
}t[N];
int main() {
scanf("%d", &T);
while (T--) {
k = 0;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d", &a[i]);
sort(a + 1, a + 1 + m);
for (int i = 2; i <= m; ++i)
t[++k] = { a[i] - a[i - 1] - 1,2 };
int num_tmp = a[1] + n - a[m] - 1;
if (num_tmp > 0) {
t[++k] = { num_tmp, 2 };
}
sort(t + 1, t + 1 + k, [](str a, str b) {return a.x > b.x; });
long long ans = 0, cnt = 0;
for (int i = 1; i <= k; ++i) {
if (t[i].x - cnt * 2 > 0) {
int num_tmp = max(1ll, t[i].x - cnt * 2 - 1);
ans += num_tmp;
}
cnt += 2;
}
printf("%lld\n", n - ans);
}
}
Tutorial is loading...
solution
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <cassert>
const int MAXN = 500005;
std::vector<long long> numbers[MAXN];
std::map<long long, long long> val_to_index;
int main()
{
int t;
int n, m;
scanf("%d ", &t);
while (t--)
{
val_to_index.clear();
scanf("%d %d", &n, &m);
long long num_tmp;
for (int i = 1; i <= n; i++) {
numbers[i].clear();
numbers[i].push_back(0);
for (int j = 1; j <= m; j++) {
scanf("%lld", &num_tmp);
numbers[i].push_back(num_tmp);
}
}
long long res_tmp = -1;
for (long long i = 1; i <= n; i++) {
long long val = 0;
for (long long j = 1; j <= m; j++) {
val += (j * numbers[i][j]);
}
if (val_to_index.find(val) != val_to_index.end()) {
res_tmp = val;
val_to_index[val] = -1;
}
else {
val_to_index[val] = i;
}
}
assert(val_to_index.size() == 2);
for (auto &item : val_to_index) {
if (item.second != -1ll) {
printf("%lld %lld\n", item.second, std::abs(res_tmp - item.first));
break;
}
}
}
return 0;
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int N = 500005, inf = 2147483647, M = 998244353;
int n, m, a[N], u, v, i, d[N], q[N], r, mx;
int b[N], tmp[N];
vector<int> g[N], z[N];
long long s[N];
int p[15];
void NEX(int M) {
for (int i = 1; i <= n; ++i)
if (b[i]) {
tmp[i] += b[i] - 1;
for (auto it : g[i])
++tmp[it];
}
for (int i = 1; i <= n; ++i) {
if (tmp[i] >= M)
b[i] = tmp[i] % M + M;
else
b[i] = tmp[i] % M;
tmp[i] = 0;
}
}
int cal(int M) {
for (int i = 1; i <= n; ++i) {
b[i] = a[i];
}
for (int i = 1; i <= n; ++i) {
bool fl = false;
for (int j = 1; j <= n; ++j)
if (b[j])
fl = true;
if (!fl)
return i - 1;
NEX(M);
}
return n;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
g[i].clear();
z[i].clear();
d[i] = 0;
tmp[i] = 0;
s[i] = 0;
}
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &u, &v);
++d[u];
g[u].push_back(v);
z[v].push_back(u);
}
mx = cal(M);
if (mx < n) {
cout << mx << endl;
continue;
}
r = 0;
for (int i = 1; i <= n; ++i)
if (!d[i])
q[++r] = i;
s[q[1]] = 1;
for (int i = 1; i <= r; ++i) {
s[q[i]] %= M;
for (auto it : z[q[i]]) {
--d[it];
s[it] += s[q[i]];
if (!d[it])
q[++r] = it;
}
}
long long ans = n;
for (int i = 1; i <= n; ++i)
ans = (ans + s[i] * b[i]) % M;
cout << ans << endl;
}
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int N=500005,inf=2147483647,M=998244353;
int n,i,t,f[N],vis[N];
char c[N];
int main(){
for(int i=1;i<=1000;++i){
for(int j=0;j<=i-2;++j)
vis[f[j]^f[i-2-j]]=1;
int j;
for(j=0;vis[j];++j);
f[i]=j;
for(int j=0;j<=i;++j)
vis[j]=0;
}
for(int i=1001;i<N;++i)
f[i]=f[i-34];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",c+1);
int s=0;
for(int i=1;i<=n;++i)
if(c[i]=='R')
++s;
else
--s;
if(s>0)
puts("Alice");
if(s<0)
puts("Bob");
if(s==0){
int ans=0;
for(int i=1;i<=n;){
int j=i+1;
for(;j<=n&&c[j]!=c[j-1];++j);
ans^=f[j-i];
i=j;
}
puts(ans?"Alice":"Bob");
}
}
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int M1=998244353,M2=1004535809,M3=469762049,E=524288,N=200005;
struct poly{
const int M;
poly(int _M):M(_M){}
int R[N*4];
long long qpow(long long a,long long b){
long long ans=1;
while(b){
if(b&1)
ans=ans*a%M;
a=a*a%M;
b>>=1;
}
return ans;
}
long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4];
void init(int E,int g){
int i;
iwn[E/2]=wn[E/2]=1;
long long s1=qpow(g,(M-1)/E);
long long s2=qpow(s1,M-2);
for(i=E/2+1;i<E;++i){
wn[i]=wn[i-1]*s1%M;
iwn[i]=iwn[i-1]*s2%M;
}
for(i=E/2-1;i;--i){
wn[i]=wn[i<<1];
iwn[i]=iwn[i<<1];
}
ifac[0]=fac[0]=inv[1]=1;
for(i=2;i<E;++i)
inv[i]=inv[M%i]*(M-M/i)%M;
for(i=1;i<E;++i){
ifac[i]=inv[i]*ifac[i-1]%M;
fac[i]=fac[i-1]*i%M;
}
}
unsigned long long ccc[N*4];
void NTT(long long *f,int lim,int op){
int i,j,k;
for(i=0;i<lim;++i){
R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0);
if(R[i]<i)
swap(f[R[i]],f[i]);
}
for(i=0;i<lim;++i)
ccc[i]=(f[i]%M+M)%M;
for(i=1;i<lim;i<<=1)
for(j=0;j<lim;j+=(i<<1))
for(k=j;k<j+i;++k){
long long w=(op==1?wn[k-j+i]:iwn[k-j+i]);
unsigned long long p=ccc[k+i]*w%M;
ccc[k+i]=ccc[k]+M-p;
ccc[k]+=p;
}
for(i=0;i<lim;++i)
f[i]=ccc[i]%M;
if(op==-1){
long long inv=qpow(lim,M-2);
for(i=0;i<lim;++i)
f[i]=f[i]*inv%M;
}
}
long long ta[N*4],tb[N*4];
void mult(long long *a,int n,long long *b,int m,long long *c){
int lim=1;
while(lim<n+m)
lim<<=1;
copy(a,a+n,ta);
copy(b,b+m,tb);
for(int i=n;i<lim;++i)
ta[i]=0;
for(int i=m;i<lim;++i)
tb[i]=0;
NTT(ta,lim,1);
NTT(tb,lim,1);
for(int i=0;i<lim;++i)
ta[i]=ta[i]*tb[i]%M;
NTT(ta,lim,-1);
copy(ta,ta+lim,c);
}
}X(M1),Y(M2),Z(M3);
int n,m,o[N],t,tn;
long long a[N],b[N],c[N],d[N*4],e[N],f[N*4],ss[N],td[N],tf[N];
bool fl[N],zz;
vector<int> ans;
long long cal(int l,int r){
return 1ll*(l+r)*(r-l+1)/2;
}
long long cal2(int u,int v){
return 1ll*((v-u)/2+1)*(u+v)/2;
}
bool iok(int n,int p,int q){
long long ss=q+1ll*(n/2)*(n/2+1);
p=p+(n/2+1);
long long mn=cal(0,p-1),mx=cal(n-p+1,n);
if(mn<=ss&&ss<=mx){
for(int i=n;i<n+m-2;++i)
if(td[i]!=tf[i-n+1]&&td[i]!=tf[i-n+1]-1)
return false;
ss-=mn;
for(int i=n;i<n+m-2;++i)
if(td[i]!=tf[i-n+1])
ans.push_back(i+2);
fill(fl,fl+1+n,0);
for(int i=0;i<p;++i)
fl[(ss/p+(i>=p-ss%p)+i)]=1;
for(int i=0;i<=n;++i)
if(fl[i]^(i&1)^1)
if(n+1-i<=tn)
ans.push_back(n+1-i);
zz=true;
return true;
}
return false;
}
void OT(){
if(!zz)
puts("-1");
else{
printf("%d\n",ans.size());
for(auto it:ans)
printf("%d ",it);
printf("\n");
}
}
void judgement(poly &v,long long *c,long long *e){
for(int i=0;i<n-2;++i)
d[i]=(c[i+1]+c[i+2])%v.M;
for(int i=0;i<m-2;++i)
f[i]=(e[i+1]+e[i+2])%v.M;
reverse(f,f+m-2);
long long s=0;
for(int i=0;i<m-2;++i)
s+=(f[i]*f[i]-f[i])%v.M;
for(int i=1;i<=n-2;++i)
ss[i]=(ss[i-1]+d[i-1]*(d[i-1]+1))%v.M;
v.mult(d,n-2,f,m-2,d);
for(int i=m-3;i<n-2;++i)
if((s+ss[i+1]-ss[i-m+3]-2*d[i])%v.M!=0)
o[i-m+4]=0;
}
int main(){
X.init(E,3);
Y.init(E,3);
Z.init(E,3);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
tn=n;
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i)
scanf("%lld",&b[i]);
for(int i=1;i<n;++i)
c[i]=a[i]+a[i+1];
for(int i=1;i<m;++i)
e[i]=b[i]+b[i+1];
fill(o,o+1+n,0);
ans.clear();
for(int i=1;i<=n;++i)
o[i]=1;
if(m>2){
for(int i=0;i<n-2;++i)
td[i+1]=c[i+1]+c[i+2];
for(int i=0;i<m-2;++i)
tf[i+1]=e[i+1]+e[i+2];
judgement(X,c,e);
judgement(Y,c,e);
judgement(Z,c,e);
}
else
for(int i=1;i<=n;++i)
o[i]=1;
int x=-1;
zz=false;
if(m==1){
for(int i=1;i<=n;++i)
if(-cal2(0,i/2*2)<=b[1]-a[i]&&b[1]-a[i]<=cal2(1,(i-1)/2*2+1)){
for(int j=-(i/2+1);j<=(i+1)/2;++j)
if(iok(i,j,b[1]-a[i]))
break;
break;
}
}
else
for(int i=1;i+m-1<=n;++i)
if(o[i]&&iok(i,(a[i]+a[i+1])-(b[1]+b[2]),b[1]-a[i]))
break;
OT();
}
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int N=200005,E=15000005;
const long long inf=1000000000000000000ll;
int n,M,mi[5005][5005];
long long fac[N],inv[N],ans;
long long C(int n,int m){
return fac[n]*inv[m]%M*inv[n-m]%M;
}
long long qpow(long long a,long long b){
long long s=a,ans=1;
while(b){
if(b&1)
ans=ans*s%M;
s=s*s%M;
b>>=1;
}
return ans;
}
int main(){
cin>>n>>M;
fac[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;++i)
inv[i]=inv[M%i]*(M-M/i)%M;
for(int i=1;i<=n;++i){
inv[i]=inv[i-1]*inv[i]%M;
fac[i]=fac[i-1]*i%M;
}
long long s1=1;
for(int i=0;i<=n;++i){
mi[i][0]=1;
for(int j=1;j<=n;++j)
mi[i][j]=1ll*mi[i][j-1]*i%M;
}
for(int j=1;2*j<=n;++j){
s1=s1*(n-1)%M;
for(int i=0;i<=n-2*j;++i)
ans=(ans+C(n,i)*fac[n-i]%M*s1%M*mi[n-i-j][i]%M*C(n-i-j-1,j-1)%M*inv[j])%M;
}
cout<<ans<<endl;
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int N=100005,inf=2147483647;
const long long sq5=200717101;
int M;
namespace poly{
int R[N*4];
long long qpow(long long a,long long b){
long long ans=1;
while(b){
if(b&1)
ans=ans*a%M;
a=a*a%M;
b>>=1;
}
return ans;
}
long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4],g;
void init(int E){
int i;
iwn[E/2]=wn[E/2]=1;
long long s1=qpow(g,(M-1)/E);
long long s2=qpow(s1,M-2);
for(i=E/2+1;i<E;++i){
wn[i]=wn[i-1]*s1%M;
iwn[i]=iwn[i-1]*s2%M;
}
for(i=E/2-1;i;--i){
wn[i]=wn[i<<1];
iwn[i]=iwn[i<<1];
}
ifac[0]=fac[0]=inv[1]=1;
for(i=2;i<E;++i)
inv[i]=inv[M%i]*(M-M/i)%M;
for(i=1;i<E;++i){
ifac[i]=inv[i]*ifac[i-1]%M;
fac[i]=fac[i-1]*i%M;
}
}
unsigned long long ccc[N*4];
void NTT(long long *f,int lim,int op){
int i,j,k;
for(i=0;i<lim;++i){
R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0);
if(R[i]<i)
swap(f[R[i]],f[i]);
}
for(i=0;i<lim;++i)
ccc[i]=(f[i]%M+M)%M;
for(i=1;i<lim;i<<=1)
for(j=0;j<lim;j+=(i<<1))
for(k=j;k<j+i;++k){
long long w=(op==1?wn[k-j+i]:iwn[k-j+i]);
unsigned long long p=ccc[k+i]*w%M;
ccc[k+i]=ccc[k]+M-p;
ccc[k]+=p;
}
for(i=0;i<lim;++i)
f[i]=ccc[i]%M;
if(op==-1){
long long inv=qpow(lim,M-2);
for(i=0;i<lim;++i)
f[i]=f[i]*inv%M;
}
}
long long ta[N*4],tb[N*4];
void mult(long long *a,int n,long long *b,int m,long long *c){
int lim=1;
while(lim<n+m)
lim<<=1;
copy(a,a+n,ta);
copy(b,b+m,tb);
for(int i=n;i<lim;++i)
ta[i]=0;
for(int i=m;i<lim;++i)
tb[i]=0;
NTT(ta,lim,1);
NTT(tb,lim,1);
for(int i=0;i<lim;++i)
ta[i]=ta[i]*tb[i]%M;
NTT(ta,lim,-1);
copy(ta,ta+lim,c);
}
long long tmp[N*4],tans[N*4];
void Getinv(long long *a,long long *ans,int lim){
ans[0]=qpow(a[0],M-2);
for(int i=1;i<lim;i<<=1){
for(int j=i;j<(i<<2);++j)
ans[j]=tans[j]=tmp[j]=0;
for(int j=0;j<(i<<1);++j)
tmp[j]=a[j];
for(int j=0;j<i;++j)
tans[j]=ans[j];
NTT(tmp,i<<2,1);
NTT(tans,i<<2,1);
for(int j=0;j<(i<<2);++j)
tmp[j]=tmp[j]*tans[j]%M*tans[j]%M;
NTT(tmp,i<<2,-1);
for(int j=0;j<(i<<1);++j)
ans[j]=(2*ans[j]-tmp[j])%M;
}
}
long long tinv[N*4];
void Getln(long long *a,long long *ans,int n){
for(int i=0;i<n-1;++i)
ans[i]=a[i+1]*(i+1)%M;
Getinv(a,tinv,n);
mult(ans,n-1,tinv,n,ans);
for(int i=n;i>=1;--i)
ans[i]=ans[i-1]*inv[i]%M;
ans[0]=0;
}
long long tln[N*4];
void Getexp(long long *a,long long *ans,int n){
ans[0]=1;
for(int i=1;i<n;i<<=1){
for(int j=i;j<(i<<1);++j)
ans[j]=0;
Getln(ans,tln,i<<1);
for(int j=0;j<(i<<1);++j)
tln[j]=-tln[j]+a[j];
++tln[0];
mult(ans,i,tln,i<<1,ans);
}
}
void Getroot(long long *a,long long *ans,int n){
ans[0]=1;
for(int i=1;i<n;i<<=1){
fill(ans+i,ans+(i<<1),0);
Getinv(ans,tinv,i<<1);
mult(tinv,i<<1,a,i<<1,tinv);
for(int j=0;j<(i<<1);++j)
ans[j]=(ans[j]+tinv[j])*inv[2]%M;
}
}
long long ttln[N*4];
void Getpow(long long *a,long long *ans,int n,int m){
Getln(a,ttln,m);
for(int i=0;i<m;++i)
ttln[i]=ttln[i]*n%M;
Getexp(ttln,ans,m);
}
};
int n,m;
long long f[N*4],g[N*4],h[N*4],hd[N*4],tmp[N*4],eh[N*4],tmp2[N*4],inv[N*4];
void Newton(int lim){
f[0]=f[1]=0;
for(int i=2;i<lim;i<<=1){
poly::Getexp(f,g,i<<1);
for(int j=(i<<1)-1;j>=1;--j)
g[j]=g[j-1];
g[0]=0;
for(int j=0;j<(i<<1);++j)
h[j]=(f[j]+g[j])%M;
poly::Getexp(h,eh,i<<1);
poly::mult(eh,i<<1,h,i<<1,tmp);
++h[0];
++g[0];
poly::mult(g,i<<1,h,i<<1,tmp2);
poly::mult(tmp2,i<<1,eh,i<<1,tmp2);
for(int j=(i<<1);j>=1;--j){
tmp2[j]=-tmp2[j-1];
tmp[j]=-tmp[j-1];
}
tmp2[0]=1;
for(int j=0;j<(i<<1);++j)
tmp[j]=(tmp[j]+f[j])%M;
poly::Getinv(tmp2,inv,i<<1);
poly::mult(inv,i<<1,tmp,i<<1,h);
for(int j=0;j<(i<<1);++j)
f[j]=(f[j]-h[j])%M;
}
}
long long rt[N*4],X[N*4],Y[N*4],p1[N*4],p2[N*4],p[N*4],e1[N*4],e2[N*4];
long long fd[N*4],gd[N*4],as[N*4],ans[N*4],as2[N*4];
int lim=1;
int main(){
cin>>n>>M;
int tmpp=M-1;
vector<int> dz;
for(int i=2;i*i<=tmpp;++i)
while(tmpp%i==0){
tmpp/=i;
dz.push_back(i);
}
if(tmpp!=1)
dz.push_back(tmpp);
for(int i=2;i<M;++i){
int z=M-1;
bool fl=true;
for(auto it:dz)
if(poly::qpow(i,z/it)==1){
fl=false;
break;
}
if(fl){
poly::g=i;
break;
}
}
poly::init(262144);
++n;
while(lim<=n*2)
lim<<=1;
Newton(n+1);
memset(inv,0,sizeof(inv));
poly::Getexp(f,g,n+1);
for(int j=n;j>=1;--j)
g[j]=g[j-1];
g[0]=0;
for(int j=0;j<=n;++j)
h[j]=(f[j]+g[j])%M;
poly::Getexp(h,eh,n+1);
for(int j=1;j<=n;++j)
tmp[j]=-eh[j-1];
tmp[0]=1;
poly::Getln(tmp,as2,n+1);
for(int j=1;j<=n;++j)
as2[j]=(as2[j]-f[j])%M;
poly::mult(eh,n+1,h,n+1,X);
for(int i=0;i<=n;++i)
eh[i]=(X[i]+eh[i])%M;
for(int i=n;i>=1;--i){
eh[i]=eh[i-1];
Y[i]=eh[i];
}
eh[0]=0;
poly::mult(eh,n+1,g,n+1,eh);
for(int i=1;i<=n;++i)
h[i]=(-eh[i]-Y[i])%M;
h[0]=1;
poly::Getln(h,as,n+1);
for(int i=0;i<=n;++i)
as[i]=(-as[i]+as2[i])%M;
poly::Getexp(as,ans,n+1);
--n;
for(int i=1;i<=n;++i)
printf("%lld\n",(ans[i]*poly::fac[i]%M+M)%M);
}
