[BZOJ 3622]已经没有什么好害怕的了

 1 #include <cstdio>
 2 #include <algorithm>
 3 const int mod=1000000009;
 4 const int size=2048;
 5 
 6 namespace IOspace
 7 {
 8     inline int getint()
 9     {
10         register int num=0;
11         register char ch;
12         do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);
13         do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);
14         return num;
15     }
16     inline void putint(int num, char ch=‘\n‘)
17     {
18         char stack[15];
19         register int top=0;
20         if (num==0) stack[top=1]=‘0‘;
21         for ( ;num;num/=10) stack[++top]=num%10+‘0‘;
22         for ( ;top;top--) putchar(stack[top]);
23         if (ch) putchar(ch);
24     }    
25 }
26 
27 int n, k;
28 int a[size], b[size];
29 int next[size];
30 int fact[size];
31 int C[size][size];
32 int f[size][size];
33 inline int add(int x, int y) {return (x+y)%mod;}
34 inline int sub(int x, int y) {return (x-y+mod)%mod;}
35 inline int mul(int x, int y) {return static_cast<long long>(x)*y%mod;}
36 inline void prepare();
37 
38 int main()
39 {
40     n=IOspace::getint(), k=IOspace::getint();
41     if ((n-k)&1) {putchar(‘0‘); putchar(‘\n‘); return 0;}
42     k=(n+k)>>1;
43     for (int i=1;i<=n;i++) a[i]=IOspace::getint();
44     for (int i=1;i<=n;i++) b[i]=IOspace::getint();
45 
46     prepare();
47 
48     f[0][0]=1;
49     for (int i=1;i<=n;i++)
50         for (int j=0;j<=i;j++)
51         {
52             f[i][j]=f[i-1][j];
53             if (j && next[i]-j+1>0)
54                 f[i][j]=add(f[i][j], mul(f[i-1][j-1], next[i]-j+1));
55         }
56 
57     for (int i=n;i>=k;i--)
58     {
59         f[n][i]=mul(f[n][i], fact[n-i]);
60         for (int j=i+1;j<=n;j++) f[n][i]=sub(f[n][i], mul(f[n][j], C[j][i]));
61     }
62 
63     IOspace::putint(f[n][k]);
64 
65     return 0;
66 }
67 inline void prepare()
68 {
69     std::sort(a+1, a+n+1); std::sort(b+1, b+n+1);
70 
71     int j=0;    
72     for (int i=1;i<=n;i++)
73     {
74         for ( ;j<n && a[i]>b[j+1];j++);
75         next[i]=j;
76     }
77 
78     for (int i=0;i<=n;i++)
79     {
80         C[i][0]=C[i][i]=1;
81         for (int j=1;j<i;j++)
82             C[i][j]=add(C[i-1][j-1], C[i-1][j]);
83     }
84 
85     fact[0]=1;
86     for (int i=1;i<=n;i++) fact[i]=mul(fact[i-1], i);
87 }