首页 > 代码库 > [杂题]CSUOJ1276 Counting Route Sequence

[杂题]CSUOJ1276 Counting Route Sequence

2024-08-07 07:43:50   209人阅读

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1276

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

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

方法数模上1000000007

 

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

就是：如从1走到5

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

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

最后全部相乘就可以了

 

公式是

 

的公式是 

因为n、m的范围为1e5， 所以要进行取模， 因此就要求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     }

 

所以可以先对1e5内的阶乘打个表 预处理一下

 

  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


联系
我们