差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200513比赛记录 [2020/05/24 13:42]
zars19 [A-Blank]
+++ 2020-2021:teams:wangzai_milk:20200513比赛记录 [2020/06/08 14:23] (当前版本)
wzx27
@@ 行 2: / 行 2: @@
 ===== 比赛情况 =====
+^题号 	^A 	^B 	^C 	^D 	^E 	^F 	^G 	^H 	^I 	^J 	^K 	^L 	^M	|
+^状态 	|Ø 	|O 	|- 	|O 	|O 	|Ø 	|- 	|- 	|Ø	|-	|-	|Ø	|Ø	|
+//O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试//
 **比赛时间**
@@ 行 504: / 行 510: @@
 </code>
+==== L-Sequence ====
+补题 by _wzx27
+把数列 $a_i$ 写成其生成函数的形式 $f(x)=\sum a_ix^i$，每个操作 $k$ 相当于 $f(x)\cdot \sum x^{ik}$，由交换律知顺序不重要，所以可以统计每种操作的次数 $m_i$，最后有
+$$f(x)\cdot (\sum x^{i})^{m_1} \cdot (\sum x^{2i})^{m_2} \cdot (\sum x^{3i})^{m_3}$$
+其中$(\sum x^{ki})^m = \sum {i+m-1 \choose m-1}x^{ik}$
+另外模数刚好是998244353，做三次NTT即可
+<hidden code>
+<code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii_ pair<int,int>
+#define mp_ make_pair
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=(a);i<=(b);i++)
+#define per(i,a,b) for(int i=(a);i>=(b);i--)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+const int maxn = 2e6+5;
+const ll M = 998244353;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s; }
+int n,m,lim,l,r[maxn],cnt[maxn];
+ll A[maxn],B[maxn],fac[maxn],inv[maxn];
+int c[5];
+void NTT(ll a[],int type)
+{
+    rep(i,1,lim-1) if(i<r[i]) swap(a[i],a[r[i]]);
+    for(int mid=1;mid<lim;mid<<=1){
+        ll wn = qpow(3,(M-1)/mid/2);
+        if(type==-1) wn = qpow(wn,M-2);
+        for(int R=mid<<1,j=0;j<lim;j+=R){
+            ll w = 1;
+            for(int k=0;k<mid;k++,w=w*wn%M){
+                ll x=a[j+k],y=w*a[j+mid+k]%M;
+                a[j+k] = (x+y)%M;
+                a[j+mid+k] = (x-y+M)%M;
+            }
+        }
+    }
+    if(type==-1){
+        ll INV = qpow(lim,M-2);
+        rep(i,0,lim) a[i] = a[i]*INV%M;
+    }
+}
+ll Comb(ll a,ll b) {return a<b?0:fac[a]*inv[b]%M*inv[a-b]%M;}
+void init()
+{
+    fac[0] = 1;
+    rep(i,1,2000000) fac[i]=fac[i-1]*i%M;
+    inv[2000000] = qpow(fac[2000000],M-2);
+    per(i,2000000-1,0) inv[i]=inv[i+1]*(i+1)%M;
+}
+int main()
+{
+    fastio();
+    int _;
+    init();
+    for(cin>>_;_;_--){
+        cin>>n>>m;
+        memset(A,0,sizeof(A));
+        memset(B,0,sizeof(B));
+        rep(i,0,n-1) cin>>A[i];
+        lim=1,l=0;
+        while(lim<=2*n) lim<<=1,l++;
+        rep(i,0,lim-1) r[i] = (r[i>>1]>>1) | ((i&1)<<(l-1));
+        cnt[1]=cnt[2]=cnt[3]=0;
+        while(m--) {int x;cin>>x;cnt[x]++;}
+        rep(i,1,3)if(cnt[i]){
+            memset(B,0,sizeof(B));
+            for(int j=0;j*i<n;j++) B[i*j] = Comb(cnt[i]+j-1,j);
+            NTT(A,1);NTT(B,1);
+            rep(i,0,lim) A[i] = A[i]*B[i]%M;
+            NTT(A,-1);
+            rep(i,n+1,lim) A[i]=0;
+        }
+        ll ans = 0;
+        rep(i,0,n-1) ans ^= ((i+1)*A[i]);
+        cout<<ans<<endl;
+    }
+    return 0;
+}
+</code>
+</hidden>
 ==== M-Code ====

CVBB ACM Team

用户工具

站点工具

差别

页面工具