atcoder_abc\AtCoder Beginner Contest 310\E_NAND_repeatedly

//題意：給定一個(gè)n長度的01串，計(jì)算f(l,r)(l<=r,l在1~n,r在1~n)的和,f的計(jì)算(ai,a(i+1))運(yùn)算,有0就為1,11為0

//若f(l,r)=1,則f(l,r-1)為0或sr為0,即只取決于上一位的情況和當(dāng)前位，枚舉右端點(diǎn)，對答案的貢獻(xiàn)即有多少左端點(diǎn)使得f(i,r)=1;

#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>#include<unordered_map>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define int128 __int128_t#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define fer(i,x) ? for(int i=e.head[x];i;i=e.next[i])#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;ll poww(ll x, ll k){if(k == 1) return x;if(k == 0) return 1;ll tmp = poww(x, k / 2);if(k & 1) return tmp * tmp % mod * x % mod;return tmp * tmp % mod;}template<size_t size>struct Road{int to[size], next[size], head[size], cnt = 1;ll w[size];void add(int x, int y, ll ww){to[cnt] = y;w[cnt] = ww;next[cnt] = head[x];head[x] = cnt ++;}void clear(int n){for(int i = 0; i <= n; i ++){head[i] = 0;}cnt = 1;}};template<size_t size>struct Combinatorial_number{int fact[size], finv[size]; // fact[x]是x的階乘，inv[x]是fact[x]的逆元void init(){fact[0] = 1;for(int i = 1; i < (int)size; i ++){fact[i] = 1ll * fact[i - 1] * i % mod;}finv[size - 1] = poww(fact[size - 1], mod - 2);for(int i = size - 2; i >= 0; i --){finv[i] = 1ll * finv[i + 1] * (i + 1) % mod;}}ll C(int n, int m){if(m < n || n < 0 || m < 0) return 0;return 1ll * fact[m] * finv[n] % mod * finv[m - n] % mod;}ll A(int n, int m){if(m < n || n < 0 || m < 0) return 0;return 1ll * fact[m] * finv[m - n] % mod;}ll llC(int n, int m){//求解不進(jìn)行取余mod的可能爆longlong的C(n,m)值;if(m < n || n < 0 || m < 0) return 0;swap(n, m);long long sum = 1;if (m > n - m) ?m = n - m;n = n - m + 1;for (int i = 1; i <= m; i ++){sum *= n ++;sum /= i;}return sum;}};template<size_t size>struct Prime{int con[size], tot = 0, vis[size];void init(){for(int i = 2; i < (int)size; i ++){if(vis[i] == 0) con[++ tot] = i;for(int j = 1; j <= tot && i * con[j] < (int)size; j ++){vis[i * con[j]] = con[j];if(i % con[j] == 0) break;}}}};// Road <N> e; // 無向圖 * 2// Combinatorial_number <N> comb;// Prime <N> prime;//題意：給定一個(gè)n長度的01串，計(jì)算f(l,r)(l<=r,l在1~n,r在1~n)的和,f的計(jì)算(ai,a(i+1))運(yùn)算,有0就為1,11為0//若f(l,r)=1,則f(l,r-1)為0或sr為0,即只取決于上一位的情況和當(dāng)前位，枚舉右端點(diǎn)，對答案的貢獻(xiàn)即有多少左端點(diǎn)使得f(i,r)=1;//int n,m;int a[N];int dp[N][2]; ? ? ? ? ? ? ? //dp[i][0/1]表示f(l,i)==0的數(shù)量或f(l,i)==1的數(shù)量void solve(){cin>>n;string s;cin>>s;s=" "+s;int ans=0;fr(i,1,s.size()-1){if(s[i]=='0'){dp[i][0]=1; ? ? ? ? ? ? ? ? ? ? ? ? ? ?//本身dp[i][1]=dp[i-1][0]+dp[i-1][1]; ? ? ? ? ? ? //考慮上一位有多少f(l,i-1)==0的數(shù)量或f(l,i-1)==1的數(shù)量}else{dp[i][0]=dp[i-1][1];dp[i][1]=dp[i-1][0]+1;}ans+=dp[i][1];}cout<<ans<<'\n';}signed main(){int t=1;// ? cin>>t;while(t--) solve();return 0;}

atcoder_abc\AtCoder Beginner Contest 313\D_Odd_or_Even

//題意：交互題，給定n，可以選擇k個(gè)數(shù)（k為奇數(shù)且k<n），程序告訴k個(gè)數(shù)的異或值，求可以唯一確定的n長度序列（數(shù)值只會(huì)為0或1）

//思路：以n=4,k=3為例，先查詢1 2 3,1 3 4,1 2 4三個(gè)結(jié)果的異或值，將三個(gè)結(jié)果異或就可以得知a1的值，同理，前k+1個(gè)數(shù)也可推出

//要知道第k+2個(gè)數(shù)，查詢3,4..k+2的異或值，再異或a3,a4...ak+1即可

//k為奇數(shù)是為了保證在k次查詢中除查詢的其他均出現(xiàn)偶數(shù)次

#include <bits/stdc++.h>using namespace std;using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;vector<int> ans(n);auto solve = [&](int l, int r) {vector<int> tmp(r - l);vector<int> q;for (int i = l; i < r; ++i) {q.clear();for (int j = l; j < r; ++j)if (j != i)q.push_back(j);cout << "?";for (auto& i : q)cout << ' ' << i + 1;cout << endl;cin >> tmp[i - l];}for (int i = l; i < r; ++i) {for (int j = l; j < r; ++j) {if (j != i) {ans[i] ^= tmp[j];}}}};solve(0, k + 1);for (int i = k + 1; i < n; i++) {cout << "?";for (int j = i; j > i - k; --j) {cout << ' ' << j + 1;}cout << endl;cin >> ans[i];for (int j = i - 1; j > i - k; --j)ans[i] ^= ans[j];}cout << "!";for (auto& i : ans)cout << ' ' << i;cout << endl;return 0;}

//題意：給定一個(gè)字符串，由()?組成，可以將?替換成(或)，求能組成滿足()的個(gè)數(shù)

?//狀態(tài)：dp[i][j]表示在i位置,(記作1，)表示-1，j表示前綴和

#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>#include<unordered_map>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define int128 __int128_t#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;ll poww(ll x, ll k){if(k == 1) return x;if(k == 0) return 1;ll tmp = poww(x, k / 2);if(k & 1) return tmp * tmp % mod * x % mod;return tmp * tmp % mod;}template<size_t size>struct Road{int to[size], next[size], head[size], cnt = 1;ll w[size];void add(int x, int y, ll ww){to[cnt] = y;w[cnt] = ww;next[cnt] = head[x];head[x] = cnt ++;}void clear(int n){for(int i = 0; i <= n; i ++){head[i] = 0;}cnt = 1;}};template<size_t size>struct Combinatorial_number{int fact[size], finv[size]; // fact[x]是x的階乘，inv[x]是fact[x]的逆元void init(){fact[0] = 1;for(int i = 1; i < (int)size; i ++){fact[i] = 1ll * fact[i - 1] * i % mod;}finv[size - 1] = poww(fact[size - 1], mod - 2);for(int i = size - 2; i >= 0; i --){finv[i] = 1ll * finv[i + 1] * (i + 1) % mod;}}ll C(int n, int m){if(m < n || n < 0 || m < 0) return 0;return 1ll * fact[m] * finv[n] % mod * finv[m - n] % mod;}ll A(int n, int m){if(m < n || n < 0 || m < 0) return 0;return 1ll * fact[m] * finv[m - n] % mod;}ll llC(int n, int m){//求解不進(jìn)行取余mod的可能爆longlong的C(n,m)值;if(m < n || n < 0 || m < 0) return 0;swap(n, m);long long sum = 1;if (m > n - m) ?m = n - m;n = n - m + 1;for (int i = 1; i <= m; i ++){sum *= n ++;sum /= i;}return sum;}};template<size_t size>struct Prime{int con[size], tot = 0, vis[size];void init(){for(int i = 2; i < (int)size; i ++){if(vis[i] == 0) con[++ tot] = i;for(int j = 1; j <= tot && i * con[j] < (int)size; j ++){vis[i * con[j]] = con[j];if(i % con[j] == 0) break;}}}};// Road <maxn> e; // 無向圖 * 2// Combinatorial_number <N> comb;// Prime <N> prime;//題意：給定一個(gè)字符串，由()?組成，可以將?替換成(或)，求能組成滿足()的個(gè)數(shù)int n,m;int a[N];int dp[3010][3010]; ? ? ? ? ? ? //dp[i][j]表示在i位置,(記作1，)表示-1，j表示前綴和void solve(){string s;cin>>s;n=s.size();s=' '+s;dp[0][0]=1;int Max=0;fr(i,1,n){fr(j,0,i){if(s[i]=='('){if(j)dp[i][j]=dp[i-1][j-1];}else if(s[i]==')'){dp[i][j]=dp[i-1][j+1];}else {if(!j) ?dp[i][j]=dp[i-1][j+1];else dp[i][j]=(dp[i-1][j+1]+dp[i-1][j-1])%mod;}}}cout<<dp[n][0]<<'\n';}signed main(){int t=1;// ? cin>>t;while(t--) solve();return 0;}