【Codevs 2115】数集分割

 1 // <2115.cpp> - Sun Oct  9 12:58:23 2016
 2 // This file is made by YJinpeng，created by XuYike‘s black technology automatically.
 3 // Copyright (C) 2016 ChangJun High School, Inc.
 4 // I don‘t know what this program is.
 5 
 6 #include <iostream>
 7 #include <cstdio>
 8 #define LL long long
 9 using namespace std;
10 int quick_pow(int a,int b,int p){
11     int w=1;
12     while(b){
13         if(b&1)w=(w*a)%p;
14         b>>=1;a=(a*a)%p;
15     }
16     return w;
17 }
18 int main()
19 {
20     freopen("2115.in","r",stdin);
21     freopen("2115.out","w",stdout);
22     int n;scanf("%d",&n);
23     int ans=(quick_pow(2,n/2,10000)-1)*(quick_pow(2,(n-1)/2,10000)-1);
24     ans%=10000;printf((n>=15?"%.4d":"%d"),ans);
25     return 0;
26 }