NC20511. [ZJOI2013]话旧
描述
输入描述
第一行包含2个用空格隔开的整数N,K 。接下来K行，每行2个整数，表示x[i]和f(x[i])。
输出描述
一行两个整数，分别对应两个问题的答案。考虑到第一问答案可能很大，你只要输出它除以19940417的余数。
示例1
输入:
2 0
输出:
1 1
示例2
输入:
6 9 4 2 4 2 2 0 4 2 6 0 5 1 2 0 0 0 0 0
输出:
1 2
C++(clang++11) 解法, 执行用时: 152ms, 内存消耗: 16632K, 提交时间: 2020-10-25 19:58:22
#include<bits/stdc++.h>
#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;--x)
#define FOR_(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)
#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)
#define ts *this
#define sf scanf
#define pf printf
#define ll long long
#define ull unsigned long long
#define db double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)
using namespace std;
template<class T>
bool tomin(T &x,T y)
{
return x>y?x=y,1:0;
}
template<class T>
bool tomax(T &x,T y)
{
return x<y?x=y,1:0;
}
template<class T>
void read(T &x)
{
char c;
x=0;
int f=1;
while(c=getchar(),c<'0'||c>'9')
if(c=='-') f=-1;
do x=(x<<3)+(x<<1)+(c^48);
while(c=getchar(),c>='0'&&c<='9');
x*=f;
}
const db Pi=acos(-1);
const int maxn=1e6+5;
const int P=19940417;
int n,m;
struct node
{
int x,y;
bool operator <(const node &A)const
{
return x<A.x;
}
bool operator ==(const node &A)const
{
return x==A.x&&y==A.y;
}
}pos[maxn];
ll dp[maxn][2];
void Mod(ll &x,ll y)
{
x+=y;
x%=P;
}
ll pw(ll s)
{
ll res=1,x=2;
while(s)
{
if(s&1) res=res*x%P;
x=x*x%P;
s>>=1;
}
return res;
}
int main()
{
srand(time(NULL));
read2(m,n);
FOR(i,1,n) read2(pos[i].x,pos[i].y);
pos[++n]=(node){0,0};
pos[++n]=(node){m,0};
sort(pos+1,pos+n+1);
n=unique(pos+1,pos+n+1)-pos-1;
dp[1][0]=1;
int mx=0;
FOR(i,1,n-1)
{
int j=i+1;
tomax(mx,(pos[j].y+pos[j].x+pos[i].y-pos[i].x)/2);
if(abs(pos[i].y-pos[j].y)==pos[j].x-pos[i].x)
{
if(pos[j].y>pos[i].y)
{
if(pos[i].y==0) Mod(dp[j][1],dp[i][0]);
else Mod(dp[j][1],dp[i][1]);
}
else
{
Mod(dp[j][0],dp[i][0]);
Mod(dp[j][0],dp[i][1]);
}
}
else
{
ll m=((ll)pos[j].x-pos[i].x-pos[i].y-pos[j].y)/2;
if(m<0) Mod(dp[j][0],dp[i][1]);
else
{
if(dp[i][0])
{
if(m) Mod(dp[j][0],pw(m-1)*dp[i][0]);
Mod(dp[j][1],pw(max((ll)0,m-1))*dp[i][0]);
}
if(dp[i][1])
{
Mod(dp[j][0],pw(m)*dp[i][1]);
Mod(dp[j][1],pw(m)*dp[i][1]);
}
}
}
if(pos[j].y==0) dp[j][1]=0;
}
pf("%lld %d",(dp[n][0]+dp[n][1])%P,mx);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 202ms, 内存消耗: 16632K, 提交时间: 2019-08-20 21:47:06
#include<bits/stdc++.h>
#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)
#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)
#define ts (*this)
#define sf scanf
#define pf printf
#define ll long long
#define ull unsigned long long
#define db double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)
using namespace std;
template<class T>bool tomin(T &x,T y){return x>y?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
char c;
x=0;
int f=1;
while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
do x=(x<<3)+(x<<1)+(c^48);
while(c=getchar(),c>='0'&&c<='9');
x*=f;
}
const db Pi=acos(-1);
const int maxn=1e6+5;
const int P=19940417;
int n,m;
struct node{
int x,y;
bool operator <(const node &A)const
{
return x<A.x;
}
bool operator ==(const node &A)const
{
return x==A.x&&y==A.y;
}
}pos[maxn];
ll dp[maxn][2];
void Mod(ll &x,ll y){
x+=y;
x%=P;
}
ll pw(ll s){
ll res=1,x=2;
while(s){
if(s&1)res=res*x%P;
x=x*x%P;
s>>=1;
}return res;
}
int main(){
srand(time(NULL));
read2(m,n);
FOR(i,1,n)read2(pos[i].x,pos[i].y);
pos[++n]=(node){0,0};
pos[++n]=(node){m,0};
sort(pos+1,pos+n+1);
n=unique(pos+1,pos+n+1)-pos-1;
dp[1][0]=1;
int mx=0;
FOR(i,1,n-1){
int j=i+1;
tomax(mx,(pos[j].y+pos[j].x+pos[i].y-pos[i].x)/2);
if(abs(pos[i].y-pos[j].y)==pos[j].x-pos[i].x){
if(pos[j].y>pos[i].y){
if(pos[i].y==0)Mod(dp[j][1],dp[i][0]);
else Mod(dp[j][1],dp[i][1]);
}else{
Mod(dp[j][0],dp[i][0]);
Mod(dp[j][0],dp[i][1]);
}
}else{
ll m=((ll)pos[j].x-pos[i].x-pos[i].y-pos[j].y)/2;
if(m<0)Mod(dp[j][0],dp[i][1]);
else{
if(dp[i][0]){
if(m)Mod(dp[j][0],pw(m-1)*dp[i][0]);
Mod(dp[j][1],pw(max((ll)0,m-1))*dp[i][0]);
}
if(dp[i][1]){
Mod(dp[j][0],pw(m)*dp[i][1]);
Mod(dp[j][1],pw(m)*dp[i][1]);
}
}
}
if(pos[j].y==0)dp[j][1]=0;
}
pf("%lld %d",(dp[n][0]+dp[n][1])%P,mx);
return 0;
}