做网站外链,wordpress网页怎么上传,松岗建设网站,wordpress 链接传参数牛客网暑期ACM多校训练营#xff08;第九场#xff09; A. Circulant Matrix 做法#xff1a;看到下标 \(xor\) 这种情况就想 \(FWT\)#xff0c;可是半天没思路#xff0c;于是放弃了。。其实这个 \(n\) 疯狂暗示啊。设未知数向量为 \(x\)#xff0c;列一下方程组就可以… 牛客网暑期ACM多校训练营第九场 A. Circulant Matrix 做法看到下标 \(xor\) 这种情况就想 \(FWT\)可是半天没思路于是放弃了。。其实这个 \(n\) 疯狂暗示啊。设未知数向量为 \(x\)列一下方程组就可以发现有: \[b[k] \sum_{i \oplus j k} a[i]·x[j]\] 做法就显然了吧把\(a\)和\(b\)分别\(FWT\)对应相除然后反变换即可。表示前天才学的\(FWT\)就不会使了。。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
typedef long long ll;
const int mod 1e97;
const int N 26214410;
using namespace std;
inline int add(int x,int y) {xy;if(xmod)x-mod;return x;
}
inline int sub(int x,int y) {x-y;if(x0)xmod;return x;
}
int n;
ll a[N],b[N],inv2;
ll q_pow(ll a,ll b) {ll ans1;while(b) {if(b1) ans(ans*a)%mod;a(a*a)%mod;b1;}return ans;
}
void FWT_xor(ll a[],int n,int on) {for(int i1;in;i1) {for(int j0;jn;j(i1)) {for(int k0;ki;k) {ll ua[jk], ta[jki];a[jk]add(u,t); a[jki]sub(u,t);if(on-1) {a[jk](ll)a[jk]*inv2%mod;a[jki](ll)a[jki]*inv2%mod;}}}}
}
int main() {scanf(%d,n);inv2 q_pow(2,mod-2);rep(i,0,n-1) scanf(%lld,a[i]);rep(i,0,n-1) scanf(%lld,b[i]);FWT_xor(a,n,1);FWT_xor(b,n,1);rep(i,0,n-1) a[i](b[i]*q_pow(a[i],mod-2))%mod;FWT_xor(a,n,-1);rep(i,0,n-1) printf(%lld\n,a[i]);return 0;
}E. Music Game 做法签到题。\(dp[i]\) 表示前i个位置的答案转移就有1当前这一位是 \(0\) 2当前这一位到位置 \(j\) 都是\(1\)位置\(j-1\)是\(0\)直接dp即可。\[dp[i] dp[i-1]·(1-p[i]) i^m·\prod_{j1}^ip[i] (i-1)^m·\prod_{j2}^ip[i]·(1-p[1]) \sum_{j3}^i ((i-j1)^m dp[j-2])·\prod_{kj}^i p[k]·(1-p[j-1])\]要注意区间的概率需要判\(0\)在这卡了好久。 #include bits/stdc.h
#define rep(i,a,b) for(ll ia;ib;i)
typedef long long ll;
const ll mod 1e9 7;
const int N 1100;
using namespace std;
ll q_pow(ll a,ll b) {ll ans 1;while(b) {if(b1) ans(ans*a)%mod;a(a*a)%mod;b1;}return ans;
}
ll INV(ll x) {return q_pow(x,mod-2);
}
ll n,m,p[N],inv1,dp[N],PP[N],s0[N];
ll P(int l,int r) {ll ans0;if(s0[r]-s0[l-1]0) return PP[r]*INV(PP[l-1])%mod;return 0;
}
int main() {scanf(%lld%lld,n,m);inv1q_pow(100LL,mod-2);rep(i,1,n) scanf(%lld,p[i]),(p[i]*inv1)%mod;//cal();int tt 1,cc0;while(p[tt]0ttn)tt;for(int itt;in;i) p[cc]p[i];ncc;PP[0]1;PP[1]p[1];s0[1](p[1]0);rep(i,2,n) {if(p[i]) PP[i](PP[i-1]*p[i])%mod;else PP[i]PP[i-1];s0[i](s0[i-1])(p[i]0);}dp[1] p[1];rep(i,2,n) {dp[i] (dp[i-1]*(1-p[i]mod))%mod;dp[i] ((q_pow(i-1LL,m)*P(2,i))%mod*(1-p[1]mod))%mod;dp[i] % mod;dp[i] (q_pow(i,m)*P(1,i))%mod;dp[i] % mod;if(i2) {rep(j,3,i) {dp[i] (((q_pow(i-j1,m)dp[j-2])%mod*P(j,i))%mod*(1-p[j-1]mod))%mod;dp[i] % mod;}}dp[i] % mod;}dp[n]%mod;printf(%lld\n,(dp[n]mod)%mod);return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9489432.html
