A:A Bit Common
题目大意：建立一个长度为n且每个数严格小于\(2^m\)的非空序列A使其存在一个非空子序列B，B中所有元素的与运算结果为1，输出合法A序列的个数。
思路：存在子序列合法即该序列合法，其他元素无要求。即可以枚举合法子序列的长度，其他元素均为必定非合法整数。又因为需要结果为1，所以合法子序列上的所有元素必定为奇数，其他元素必定为偶数。可证：若其它元素中存在奇数x，长为i的合法子序列已经满足除第一位上数字全为1外其他位上元素均存在0，加上x仍然成立，那么合法子序列长度为（i+1），与本次枚举情况不符。
当存在i位合法情况如图：
| 第一位 | 第二位 | ...... | 第m位 |
|---|---|---|---|
| 1 | |||
| 1 | |||
| 1 | |||
| 0 | |||
| 0 | |||
| 0 | |||
| 0 |
合法数位置的情况\(\binom{n}{i}\)
i个合法数第j位的组合情况\(2^i-1\)，共m-1位，即\((2^i-1)^{(m-1)}\)
同理非法数组合情况为\((2^{(n-i)})^{(m-1)}\)
即总数为ans+=\(\sum_{i=1}^{n} \binom{n}{i}*(2^i-1)^{(m-1)}*(2^{(n-i)})^{(m-1)}\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define max(a, b) ((a)>(b)? (a):(b))
#define min(a, b) ((a)<(b)? (a):(b))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 5e5 + 10;
const int M = 1e9 + 10;
const int INF = 0x3f3f3f;
//const int mod = 1e9+7;
int mod;
int qp(int a, int b) {
int ans = 1;
while (b) {
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int x1, y1, d;
d = exgcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
return d;
}
int norm(int x, int MOD = mod) { return (x % MOD + MOD) % MOD; }
int inv(int a, int b = mod) {
int x, y;
exgcd(a, b, x, y);
return norm(x, b);
}
int jie(int x) {
int ans = 1;
for (int i = 1; i <= x; i++) {
ans = ans * i % mod;
}
return ans % mod;
}
namespace CNM
{
const int N = 5e3 + 7;
int c[N][N];
void init(int n)
{
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
c[i][j] = 0 < j && j < i ? (c[i - 1][j - 1] + c[i - 1][j]) % mod : 1;
}
int getc(int n, int m)
{
if (n == m && m == -1)
return 1;
if (n < m || m < 0)
return 0;
return c[n][m];
}
}
//int C(int n, int m) {
// return norm( norm (jie(m) * inv(jie(n)) ) * inv(jie(m - n)) % mod );
//}
void solve() { //2 3 17;2 4 43;2 5 113;
int n, m, ans = 0;
cin >> n >> m >> mod;
CNM::init(n);
for (int i = 1; i <= n; i++) {
int res=1;
res=res*norm( CNM::getc(n,i))%mod;
res=res*norm(qp( norm( qp(2, i) - 1 ), (m - 1) ))%mod;
res=res*norm(qp(norm(qp(2,n-i)%mod),m-1))%mod;
ans=(ans+res)%mod;
ans=norm(ans);
}
cout << ans;
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) {
solve();
}
return 0;
}
I:Mirror Maze
题目大意：给出一个nm的图，每一格中存在镜子{/,\,|,-}光线触碰镜子会反射，对于q个询问求该光线触碰的镜子数（同一面镜子多次触碰只记为1）。
思路：光线通过镜子的反射形成环或链，链必定会从边界射出，环必定以同一方向经过已经走过的格子，而且链以一种方向走过的格子与环不可能重复（若链与环有重复，那么链将不会出界，与链必定出界矛盾）。即可以先处理从边界射入的所有光线以一个方向经过的每个格子，并标记（可以用set处理同一镜子经过多次导致重复计数的问题）。处理完链后遍历图，若未被标记则为环，即处理环。
环：环上每一点经过的镜子数相同，记录总数后赋值即可。
链：经过一个镜子加一，倒序赋值即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 10;
const int mod = 998244353;
struct mi{int x,y,dec;};
vector<vector<char> > mp(N, vector<char>(N));
vector<vector<vector<int> > > ans(N, vector<vector<int> >(N, vector<int>(5)));
vector<vector<vector<int> > > book(N, vector<vector<int> >(N, vector<int>(5))); //上下左右
vector<mi >mirror;
map<string,int>go;
int n, m;
void dfs(int x, int y, int dec) {
if (x < 1 || x > n || y < 1 || y > m) return; //链退出
if (book[x][y][dec]) // 环的退出
return;
book[x][y][dec] = 1;
mi a={x,y,dec};
mirror.emplace_back(a);
if (mp[x][y] == '/') {
if (dec == 1) {
dfs(x, y + 1, 4);
} else if (dec == 2) {
dfs(x, y - 1, 3);
} else if (dec == 3) {
dfs(x + 1, y, 2);
} else if (dec == 4) {
dfs(x - 1, y, 1);
}
} else if (mp[x][y] == '\\') {
if (dec == 1) {
dfs(x, y - 1, 3);
} else if (dec == 2) {
dfs(x, y + 1, 4);
} else if (dec == 3) {
dfs(x - 1, y, 1);
} else if (dec == 4) {
dfs(x + 1, y, 2);
}
} else if (mp[x][y] == '-') {
if (dec == 1) {
dfs(x + 1, y, 2);
} else if (dec == 2) {
dfs(x - 1, y, 1);
} else if (dec == 3) {
dfs(x, y - 1, 3);
} else if (dec == 4) {
dfs(x, y + 1, 4);
}
} else if (mp[x][y] == '|') {
if (dec == 1) {
dfs(x - 1, y, 1);
} else if (dec == 2) {
dfs(x + 1, y, 2);
} else if (dec == 3) {
dfs(x, y + 1, 4);
} else if (dec == 4) {
dfs(x, y - 1, 3);
}
}
}
int check(int x,int y,int dec){
if((dec==3||dec==4)&&mp[x][y]=='-') return 0;
if((dec==1||dec==2)&&mp[x][y]=='|') return 0;
return 1;
}
void addl(int x,int y,int dec){
mirror.clear();
dfs(x,y,dec);
reverse(mirror.begin(),mirror.end());
set<pair<int,int>> s;
for(auto [a,b,c]:mirror){
if(check(a,b,c)){
s.insert({a,b});
}
ans[a][b][c]=s.size();
}
}
void addh(int x,int y,int dec){
mirror.clear();
dfs(x,y,dec);
set<pair<int,int>> s;
for(auto [a,b,c]:mirror){
if(check(a,b,c)){
s.insert({a,b});
}
}
for(auto [a,b,c]:mirror){
ans[a][b][c]=s.size();
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
}
}
for (int i = 1; i <= n; i++) { //处理从左右边界射入的光
addl(i,1,4);
addl(i,m,3);
}
for (int j = 1; j <= m; j++) { //处理从上下边界射入的光
addl(1,j,2);
addl(n,j,1);
}
for(int x=1;x<=n;x++){
for(int y=1;y<=m;y++){
for(int dec=1;dec<=4;dec++){
if(!book[x][y][dec]) addh(x,y,dec);
}
}
}
go["above"]=1;
go["below"]=2;
go["left"]=3;
go["right"]=4;
int q;
cin >> q;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// for(int k=1;k<=4;k++){
// cout << ans[i][j][k] <<"|";
// }
// cout << ' ';
// }
// cout << '\n';
// }
while (q--) {
int x,y;
cin >> x >> y;
string dir;
cin >> dir;
int dec=go[dir];
if(dec==1){
x--;
}else if(dec==2){
x++;
}else if(dec==3){
y--;
}else if(dec==4){
y++;
}
cout << ans[x][y][dec] <<"\n";
}
}
signed main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios::sync_with_stdio(false);
int _ = 1;
//cin >> _;
while (_--) {
solve();
}
return 0;
}