2023.8.13

atcoder_abc\AtCoder Beginner Contest 310\E_NAND_repeatedly

//题意：给定一个n长度的01串，计算f(l,r)(l<=r,l在1~n,r在1~n)的和,f的计算(ai,a(i+1))运算,有0就为1,11为0

//若f(l,r)=1,则f(l,r-1)为0或sr为0,即只取决于上一位的情况和当前位，枚举右端点，对答案的贡献即有多少左端点使得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){//求解不进行取余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;//题意：给定一个n长度的01串，计算f(l,r)(l<=r,l在1~n,r在1~n)的和,f的计算(ai,a(i+1))运算,有0就为1,11为0//若f(l,r)=1,则f(l,r-1)为0或sr为0,即只取决于上一位的情况和当前位，枚举右端点，对答案的贡献即有多少左端点使得f(i,r)=1;//int n,m;int a[N];int dp[N][2];               //dp[i][0/1]表示f(l,i)==0的数量或f(l,i)==1的数量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的数量或f(l,i-1)==1的数量}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个数（k为奇数且k<n），程序告诉k个数的异或值，求可以唯一确定的n长度序列（数值只会为0或1）

//思路：以n=4,k=3为例，先查询1 2 3,1 3 4,1 2 4三个结果的异或值，将三个结果异或就可以得知a1的值，同理，前k+1个数也可推出

//要知道第k+2个数，查询3,4..k+2的异或值，再异或a3,a4...ak+1即可

//k为奇数是为了保证在k次查询中除查询的其他均出现偶数次

#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;}

//题意：给定一个字符串，由()?组成，可以将?替换成(或)，求能组成满足()的个数

 //状态：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){//求解不进行取余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;//题意：给定一个字符串，由()?组成，可以将?替换成(或)，求能组成满足()的个数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;}