A集合计数
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int num[100007]; int mod = 1000000007; #define ll long long ll cal(ll a, ll b){ if(b < 0) return 0; ll ans = 1; while(b){ if(b&1) ans = ans * a % mod; a = a * a % mod; b = b / 2; } return ans; } int main(){ ll n,k; while(cin>>n>>k){ for(int i = 0;i < n; i++){ scanf("%d",&num[i]); } sort(num,num+n); int p = 0; ll ans = 0; for(int i = 0;i < n; i++){ while(p < i - 1 && num[p+1] + num[i] <= k) p++; while(p>=0 && num[p] + num[i] > k) p--; if(p == -1) break; ans += (cal(2,p+1)-1)*(cal(2,i-p-1))%mod; if(num[i] * 2 <= k) ans ++; ans %= mod; } cout<<ans<<endl; } }
B 迷宫探索
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; char map[500][500]; int main(){ int n,m; while(cin>>n>>m){ for(int i = 0;i <= 2*n+1;i++) for(int j = 0;j <= 2*m+1; j++) if((i&1) && (j&1)) map[i][j] = ' '; else map[i][j] = '+'; int x = 1, y = 1, f = 0; int dir[4][2] = { 0,1, 1,0, 0,-1, -1,0 }; int face[3]; char next[2]; for(int i = 0;i < 2 * n * m - 1; i++){ scanf("%d%d%d%s",&face[0],&face[1],&face[2],next); for(int j = 0;j < 3; j++){ int u = (f + j) % 4; int xx = (x +dir[u][0]); int yy = y + dir[u][1]; if(face[j] == 0) map[xx][yy] = ' '; else if(xx & 1) map[xx][yy] = '|'; else map[xx][yy] = '-'; } switch(next[0]){ case 'l': f = 1; y-=2; break; case 'u': f = 2; x-=2; break; case 'r': f = 3; y+=2; break; case 'd': f = 0; x+=2; break; } } for(int i = 0;i <2*n+1; i++){ for(int j = 0;j < 2 * m + 1; j++) putchar(map[i][j]); puts(""); } } }
