题目大意:
有一个n个数的置换序列,告诉你每个数在包括它自己的哪个区间内最大(最大满足要求区间),然后让你求有有多少种置换方式满足上述要求。
思路:
之前一直没试过通过预处理阶乘和阶乘逆元来初始化组合数。这样做可以将求 C(n,m) 的时间复杂度降至 O(n) ;
另外将区间排序后居然可以顺次遍历满足搜索的顺序,即区间dfs分解顺序。这样避免了使用 hash 映射的 log(n) 。
输入输出外挂是网上copy的。
代码:
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005050
#define mod 1000000007
struct point
{
int l;int r;int id;
};
point a[maxn];
bool cmp(point a,point b)
{
if(a.l==b.l)return a.r>b.r;
return a.l<b.l;
}
namespace IO {
const int MX = 4e7; //1e7占用内存11000kb
char buf[MX]; int c, sz;
void begin() {
c = 0;
sz = fread(buf, 1, MX, stdin);
}
inline bool read(int &t) {
while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
if(c >= sz) return false;
bool flag = 0; if(buf[c] == '-') flag = 1, c++;
for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
if(flag) t = -t;
return true;
}
}
int cas=1,n,now,possible;
long long int fi[maxn],inv[maxn];
void init()
{
fi[0]=1;
for(int i=1;i<maxn;i++)
{
fi[i]=fi[i-1]*(long long int)i;
fi[i]%=mod;
}
}
long long int fast_pow(long long int x,long long int p)
{
long long int ans=1;
while(p>0)
{
if(p&1)ans*=x;
x*=x;
x%=mod;
ans%=mod;
p>>=1;
}
return ans;
}
long long int get_inv(int x)
{
if(inv[x]!=-1)
return inv[x];
long long int tt=mod-2;
return inv[x]=fast_pow(fi[x],tt);
}
long long int C(int n,int m)
{
if(m<0||n<m)return 0;
long long int ans=get_inv(m)*get_inv(n-m);
ans%=mod;
return (ans*fi[n])%mod;//pow(x,mod-2)
}
long long int dfs(int l,int r)
{
if(possible==0)return 0;
if(l>r)return 1;
if(a[now].l!=l||a[now].r!=r)
{
possible=0;
return 0;
}
if(l==r)
{
now++;return 1;
}
int k=a[now++].id;
long long int ans=dfs(l,k-1)*dfs(k+1,r);
ans%=mod;
ans*=C(r-l,k-l);
//printf("(%d,%d)=%lld\t%lld\n",l,r,ans,C(k-l,r-l));
return (ans%mod);
}
int main()
{
init();
memset(inv,-1,sizeof(inv));
IO::begin();
//printf("sda");
while(IO::read(n))
//while(scanf("%d",&n)!=EOF)
{
possible=1;now=1;
for(int i=1;i<=n;i++)
{
IO::read(a[i].l);
//scanf("%d",&a[i].l);
}
for(int i=1;i<=n;i++)
{
//scanf("%d",&a[i].r);
IO::read(a[i].r);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
long long int ans=dfs(1,n);
//printf("possible=%d\n",possible);
printf("Case #%d: %lld\n",cas++,ans);
}
}