A.
- 求一个序列有一个子序列,满足and和为1(即至少存在一个)
- 选数可重复,顺序有影响
- 考虑构造出一个不重复的统计方案
- 考虑选i个最低位为1,剩余最低位为0
- 则求出让这i个数形成一个合法的序列
- 即对于除最低位之外的二进制位,不存在出现i个1,即全为1的情况
- 此时一定有子序列合法
- 所以i个数的选择方案 p1= pow(two[i]-1,m-1)
- (two[i]-1为对于一个二进制为i个数任意选减去全1的一种)
- 而i个数又可以选择n中任意i个位置 p2= C[n][i]
- 对于剩下的最低位为0的数则随便选,共有two[m]/2种
- n-i个位置任意选数,共有 p3= pow(two[m-1],n-i)
- 所以总方案数为 Sum i { p1*p2*p3 }
- 注意模数可以不为质数,会没有逆元
- 组合数的求解只能用 C[i][j]=C[i-1][j]+C[i-1][j-1] 递推式得出
B.
- 求一个序列有两个合法子序列,满足and和为1(即至少存在两个)
- 至少有一个合法区间-只有一个合法区间
- 只有一个合法区间,即是自己本身,不然一定可以拆成前后两个
- f i j 选i个数,m-1位中选了j位只有一个0
- f i j 任删去一个数,就不合法(|不为1)
- 所以i中每个数上至少有一位属于j(是只有一个0的0)
- 下一个特殊位可以放在原先的i个数上,有i种选择
- 或新加一个数放在该数上,但新加的数有i个位置可以插入,也有i种选择
- f i j = i*( f i-1 j-1 + f i j-1 )
- 所以 f i j 就是 必须选i个数形成的合法区间
- 只有一个子序列总方案数 Sum i j { f i j * pow(two[i]-1-i,t-j) * pow(two[t],n-i) * C[n][i] * C[t][j] }(j>=i)
- two[i]-1(全1)-i(只有一个0)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// long long md=(long long)998244353;
// i64 mx=LONG_LONG_MAX/2;
int n,m;i64 md;std::cin>>n>>m>>md;int N=5000;
auto pow=[&](i64 a,i64 b){
i64 res=1;
while(b>0){
if(b&1)res=res*a%md;
a=a*a%md;
b>>=1;
}
return res;
};
std::vector<std::vector<i64>> C(N+5,std::vector<i64>(N+5));//md为偶数
for(int i=0;i<=N;++i){
for(int j=0;j<=i;++j){
if(j==0)C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%md;
}
}
std::vector<i64> two(N+5);two[0]=1;
for(int i=1;i<=N;++i){
two[i]=two[i-1]*2LL%md;
}
//A
i64 ans=0;int t=m-1;
for(int i=1;i<=n;++i){
i64 now=pow((two[i]-1+md)%md,t);
now=now*C[n][i]%md;
now=now*pow(two[t],n-i)%md;
ans+=now;
ans%=md;
}
//B
std::vector<std::vector<i64>> f(N+5,std::vector<i64>(N+5,0));
f[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=i;j<=t;++j){
f[i][j]=(f[i][j-1]+f[i-1][j-1])%md*i%md;
}
}
std::vector<i64> tt(N+5);
i64 onl=0;
for(int i=2;i<=n;++i){
i64 p=(two[i]-1-i+md)%md;
tt[0]=1;
for(int j=1;j<=t-i;++j){
tt[j]=tt[j-1]*p%md;
}
i64 p2=pow(two[t],n-i);
for(int j=i;j<=t;++j){
onl+=f[i][j]*tt[t-j]%md*p2%md*C[n][i]%md*C[t][j]%md;
onl%=md;
}
}
onl+=pow(two[t],n-1)*n%md;onl%=md;
std::cout<<(ans-onl+md)%md<<std::endl;
// std::cout<<ans<<" "<<onl<<std::endl;
}
D.
- 后缀一直变化,考虑找不变化的量,除了删去的前缀不变,后缀=总和-前缀
- (Sumall-pre i) mod 2 ^(d+1) >= 2^d,d位为1
- Sumall mod 2 ^(d+1) + (2 ^(d+1) -pre i ) mod 2 ^(d+1) >= 2^d
- 将(2 ^(d+1) -pre i ) mod 2 ^(d+1) 放到 2^d 对应的树状数组上,统计个数
- 查 x(d位为1)则满足 : 2 ^(d+1) > x + Sumall mod 2 ^(d+1) >=2^d
- 即x在 r= 2 ^(d+1) - 1 - Sumall mod 2 ^(d+1) , l= 2^d - Sumall mod 2 ^(d+1)
- 对每一位查[l,r]个数,即为d位为1的个数,若为奇数则异或和为1
- 若 l > r ,查 [l,n],[0,r] , 即r实际为 2 ^d+1 + r
- 注意加入树状数组时对前缀和取模
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// long long md=(long long)998244353;
// i64 mx=LONG_LONG_MAX/2;
struct Tree{
int D=1;
int siz=0;
std::vector<int> tr;
void init(int n){
n+=D;
tr.assign(n+5,0);
siz=n;
}
#define lowbit(x) (x&-x)
void update(int x,int k){
x+=D;
for(int i=x;i<=siz;i+= lowbit(i)){
tr[i]+=k;
}
}
int get(int x){
x+=D;
int res=0;
for(int i=x;i;i-= lowbit(i)){
res+=tr[i];
}
return res;
}
int query(int l,int r){
if(l>r)return 0;return get(r)-get(l-1);
}
};std::vector<Tree> Tr(25);
int n;std::cin>>n;
std::vector<i64> pre(n+5,0);int len=0;
auto init=[&](){
for(int i=0;i<21;++i)Tr[i].init((1<<(i+1)));
};
auto change=[&](int x,int k){
for(int i=0;i<21;++i){
int p=1<<(i+1);
Tr[i].update((p-x%p)%p,k);//加入-pre
}
};
auto check=[&](){
int ans=0;
for(int i=0;i<21;++i){
int cnt=0;
int p=1<<(i+1);int l=1<<i;int r=p-1;
l=(l-pre[len]%p+p)%p;r=(r-pre[len]%p+p)%p;
if(l<=r) cnt+=Tr[i].query(l,r);
else cnt+= Tr[i].query(l,p-1)+Tr[i].query(0,r);
ans|=(cnt&1)<<i;
}
return ans;
};
init();
for(int i=1;i<=n;++i){
int t;i64 v;std::cin>>t>>v;
while(t--){
if(len==1){
len--;
break;
}
change(pre[len-1],-1);len--;
}
change(pre[len],1);len++;
pre[len]=pre[len-1]+v;//pre[len],即总和不入树状数组
std::cout<<check()<<std::endl;
}
}
I.
- 光线只有两种
- 一种链出矩阵(可以有交叉,会有假环,虽然绕了一圈但会原路返回)
- 一种成环(不会有一个链在连个环)
- 对于链,当前个数等于反方向的答案
- 对于环,最终的结果个数为环上所有点的结果
- 避免判断一个点是链是环
- 先直接从矩阵边搜出链的点
- 直接搜会超时
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// long long md=(long long)998244353;
// i64 mx=LONG_LONG_MAX/2;
int n,m;std::cin>>n>>m;
std::vector<std::vector<char>> mp(n+5,std::vector<char>(m+5));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
std::cin>>mp[i][j];
}
}
int ans=0;
//left 1,above 2,right 3,below 4
std::vector<std::vector<std::vector<bool>>> vis(n+1,std::vector<std::vector<bool>>(m+1,std::vector<bool>(5,false)));
std::vector<std::vector<std::vector<int>>> num(n+1,std::vector<std::vector<int>>(m+1,std::vector<int>(5,-1)));
auto run=[&](int i,int j,int k){
std::set<pii> s;
while(1){
if(i > n || i < 1 || j > m || j < 1)
break;
if(k == 3)
num[i][j][1] = s.size();
if(k == 1)
num[i][j][3] = s.size();
if(k == 2)
num[i][j][4] = s.size();
if(k == 4)
num[i][j][2] = s.size();
if(k == 1)
{
if(mp[i][j] == '|') k = 3;
if(mp[i][j] == '\\') k = 2;
if(mp[i][j] == '/') k = 4;
if(mp[i][j]!='-')s.insert({i,j});
}
else if(k == 3)
{
if(mp[i][j] == '|') k = 1;
if(mp[i][j] == '\\') k = 4;
if(mp[i][j] == '/') k = 2;
if(mp[i][j]!='-')s.insert({i,j});
}
else if(k == 2)
{
if(mp[i][j] == '-') k = 4;
if(mp[i][j] == '\\') k = 1;
if(mp[i][j] == '/') k = 3;
if(mp[i][j]!='|')s.insert({i,j});
}
else if(k == 4)
{
if(mp[i][j] == '-') k = 2;
if(mp[i][j] == '\\') k = 3;
if(mp[i][j] == '/') k = 1;
if(mp[i][j]!='|')s.insert({i,j});
}
if(k == 1) j--;
if(k == 3) j++;
if(k == 2) i--;
if(k == 4) i++;
}
};
for(int i = 1;i <= n;i++)//出矩阵的
run(i,1,3),run(i,m,1);
for(int j = 1;j <= m;j++)
run(1,j,4),run(n,j,2);
auto run2=[&](int i,int j,int k)
{
int x = i,y = j,kk = k;
set<pii> s;
while(1)
{
if(k == 1) j--;
if(k == 3) j++;
if(k == 2) i--;
if(k == 4) i++;
if(i > n || i < 1 || j > m || j < 1 || vis[i][j][k])
break;
vis[i][j][k] = true;
if(k == 1)
{
if(mp[i][j] == '|') k = 3;
if(mp[i][j] == '\\') k = 2;
if(mp[i][j] == '/') k = 4;
if(mp[i][j]!='-')s.insert({i,j});
}
else if(k == 3)
{
if(mp[i][j] == '|') k = 1;
if(mp[i][j] == '\\') k = 4;
if(mp[i][j] == '/') k = 2;
if(mp[i][j]!='-')s.insert({i,j});
}
else if(k == 2)
{
if(mp[i][j] == '-') k = 4;
if(mp[i][j] == '\\') k = 1;
if(mp[i][j] == '/') k = 3;
if(mp[i][j]!='|')s.insert({i,j});
}
else if(k == 4)
{
if(mp[i][j] == '-') k = 2;
if(mp[i][j] == '\\') k = 3;
if(mp[i][j] == '/') k = 1;
if(mp[i][j]!='|')s.insert({i,j});
}
}
i = x,j = y;
k = kk;
int cnt = s.size();
while(1)
{
if(num[i][j][k] == cnt)
break;
num[i][j][k] = cnt;
if(k == 1) j--;
if(k == 3) j++;
if(k == 2) i--;
if(k == 4) i++;
if(k == 1)
{
if(mp[i][j] == '|') k = 3;
if(mp[i][j] == '\\') k = 2;
if(mp[i][j] == '/') k = 4;
}
else if(k == 3)
{
if(mp[i][j] == '|') k = 1;
if(mp[i][j] == '\\') k = 4;
if(mp[i][j] == '/') k = 2;
}
else if(k == 2)
{
if(mp[i][j] == '-') k = 4;
if(mp[i][j] == '\\') k = 1;
if(mp[i][j] == '/') k = 3;
}
else if(k == 4)
{
if(mp[i][j] == '-') k = 2;
if(mp[i][j] == '\\') k = 3;
if(mp[i][j] == '/') k = 1;
}
}
};
for(int i = 1;i <= n;i++){//成环的
for(int j = 1;j <= m;j++){
for(int k = 1;k <= 4;k++){
if(num[i][j][k] == -1)
run2(i,j,k);
}
}
}
int q;std::cin>>q;
for(;q>0;--q){
int x,y;std::cin>>x>>y;
string s;std::cin>>s;int op;
if(s[0]=='l')op=1;
else if(s[0]=='a')op=2;
else if(s[0]=='r')op=3;
else op=4;
std::cout<<num[x][y][op]<<std::endl;
}
}
/*
* 5 4
-\\\
|\\\
|\\\
|\\\
\--\
2
3 2 left
3 1 above
*/