zhx's contest

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 352 Accepted Submission(s): 120

Problem Description

As one of the most powerful brushes, zhx is required to give his juniors

Input

Multiply test cases(less than

Output

For each test case, output a single line indicating the answer.

Sample Input

2 233 3 5

Sample Output

2 1

Hint

In the first case, both sequence {1, 2} and {2, 1} are legal. In the second case, sequence {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} are legal, so the answer is 6 mod 5 = 1

Source

Recommend

hujie | We have carefully selected several similar problems for you:

题意：数字1~n，按某种顺序排列，且满足下列某一个条件：（1）a1~ai递增，ai~an递减（2）a1~ai递减，ai~an递增。问有多少种不同的排列。

思路：首先是全部递减或全部递增各一种；另外就是满足上列两个条件的情况了，要想满足条件（1）那就只能把最大的n放在i位置，共有C（1，n-1）+C（2，n-1）+。。。+C（n-2，n-1）即2^(n-1)-2；条件（2）与（1）相同，所以共有(2^(n-1)-2)*2+2=2^n-2.

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FRL(i,a,b) for(i = a; i < b; i++)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n) scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pf printf#define DBG pf("Hi\n")typedef __int64 ll;using namespace std;ll n,p;ll quickmul(ll x,ll m) //快速乘法，与快速幂相似{ ll re=0; while(m){ if(m&1){ re=(re+x)%p; } x=(x+x)%p; m>>=1; } return re;}ll pow_m(ll a,ll n) //快速幂{ ll ret=1; ll temp=a%p; while (n){ if (n&1) ret=quickmul(ret,temp)%p; temp=quickmul(temp,temp)%p; n>>=1; } return ret;}int main(){ int i,j; while (~scanf("%I64d%I64d",&n,&p)) { if (n==1) //特判 { if (p==1) pf("0\n"); else pf("1\n"); continue; } pf("%I64d\n",(pow_m(2,n)-2+p)%p); } return 0;}

转载于:https://www.cnblogs.com/i8888/p/4338566.html

你可能感兴趣的文章