[杂题]CSUOJ1276 Counting Route Sequence

题目链接

题意：从1号点走到n号点（每条边只能走一次，两结点间的边数必定为奇数）

问经过结点不同顺序的方式有多少种（如1->2->3->4和1->3->2->4为两种）

方法数模上1000000007

此题只需先考虑相邻两结点交替的方法数然后依次递推相乘即可

就是：如从1走到5

只需先考虑2、3交替的方法数：（很明显与边数有关的组合数）

然后类似的考虑3、4交替的方法数

最后全部相乘就可以了

公式是$\displaystyle\prod\limits_{i=1}^n\Bigg({\Large\complement}_{\frac{a_{i+1}-1}{2}+\frac{a_i-1}{2}}^{\frac{a_i-1}{2}}\Bigg)$

$C_n^m$的公式是 $\frac{n!}{m!(n-m)!}$

因为n、m的范围为$10^5$，所以要进行取模，因此就要求m！(n-m)！的逆元

要是直接for一遍再对tmp做ex_gcd 果然TLE。。。

1     LL tmp=1, ans=1;
2     for(LL i=min(n, m);i>=1;i--)
3     {
4         tmp=(tmp*i)%mod;
5         ans=(ans*(n+1-i))%mod;
6     }

所以可以先对$10^5$内的阶乘打个表预处理一下

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <climits>
  5 #include <cctype>
  6 #include <cmath>
  7 #include <string>
  8 #include <sstream>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <iomanip>
 12 using namespace std;
 13 #include <queue>
 14 #include <stack>
 15 #include <vector>
 16 #include <deque>
 17 #include <set>
 18 #include <map>
 19 typedef long long LL;
 20 typedef long double LD;
 21 const double pi=acos(-1.0);
 22 const double eps=1e-9;
 23 #define INF 0x3f3f3f
 24 #define lson l, m, rt<<1
 25 #define rson m+1, r, rt<<1|1
 26 typedef pair<int, int> PI;
 27 typedef pair<int, PI > PP;
 28 #ifdef _WIN32
 29 #define LLD "%I64d"
 30 #else
 31 #define LLD "%lld"
 32 #endif
 33 //#pragma comment(linker, "/STACK:1024000000,1024000000")
 34 //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;}
 35 //inline int read(){char ch=' ';int ans=0;while(ch<'0' || ch>'9')ch=getchar();while(ch<='9' && ch>='0'){ans=ans*10+ch-'0';ch=getchar();}return ans;}
 36 inline void print(LL x){printf(LLD, x);puts("");}
 37 //inline void read(LL &ret){char c;int sgn;LL bit=0.1;if(c=getchar(),c==EOF) return ;while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');if(c==' '||c=='\n'){ ret*=sgn; return ; }while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;ret*=sgn;}
 38 
 39 const int mod=1000000007;
 40 int a[100005];
 41 LL JC[200005];
 42 void pre()
 43 {
 44     JC[0]=1;
 45     for(int i=1;i<=200000;i++)
 46         JC[i]=(i*JC[i-1])%mod;
 47 }
 48 void ex_gcd(LL a, LL b, LL &x, LL &y)
 49 {
 50     if(b)
 51     {
 52         ex_gcd(b, a%b, x, y);
 53         LL tmp=x;
 54         x=y;
 55         y=tmp-(a/b)*y;
 56     }
 57     else
 58     {
 59         x=1, y=0;
 60         return ;
 61     }
 62 }
 63 LL C(LL n, LL m)
 64 {
 65     if(n==m || m==0)
 66         return 1;
 67     if(m==1 || m==n-1)
 68         return n;
 69 //    LL tmp=1, ans=1;
 70 //    for(LL i=min(n, m);i>=1;i--)
 71 //    {
 72 //        tmp=(tmp*i)%mod;
 73 //        ans=(ans*(n+1-i))%mod;
 74 //    }
 75     LL x, y;
 76     ex_gcd(JC[m]*JC[n-m], mod, x, y);
 77     return (JC[n]*x)%mod;
 78 }
 79 LL MOD(LL x)
 80 {
 81     while(x<0)
 82         x+=mod;
 83     return x%mod;
 84 }
 85 int main()
 86 {
 87     pre();
 88     int t;
 89     scanf("%d", &t);
 90     while(t--)
 91     {
 92         int n;
 93         scanf("%d", &n);
 94         for(int i=0;i<n-1;i++)
 95             scanf("%d", &a[i]);
 96         LL ans=1;
 97         for(int i=0;i<n-2;i++)
 98             ans=(ans*C((a[i+1]-1)/2+(a[i]-1)/2, (a[i]-1)/2)%mod)%mod;
 99         print(MOD(ans));
100     }
101     return 0;
102 }

CSUOJ 1276

[杂题]CSUOJ1276 Counting Route Sequence

推荐阅读