結果
問題 | No.2344 (l+r)^2 |
ユーザー |
|
提出日時 | 2023-10-13 20:09:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 772 ms / 2,000 ms |
コード長 | 2,563 bytes |
コンパイル時間 | 1,777 ms |
コンパイル使用メモリ | 194,848 KB |
最終ジャッジ日時 | 2025-02-17 06:56:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
//vanitas vanitatum et omnia#include<bits/stdc++.h>#define fi first#define se second#define eb emplace_back#define mp make_pairusing namespace std;typedef long double ld;typedef long long ll;typedef unsigned long long ull;typedef __int128 i128;template<typename T,typename U>T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}template<typename T,typename U>T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}template<class T,class S>bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}template<class T,class S>bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}int popcnt(int x) {return __builtin_popcount(x);}int popcnt(ll x) {return __builtin_popcountll(x);}int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}#define int long long#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define per(i,a,b) for(int i=(a);i>=(b);i--)typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<pii> vp;typedef tuple<int,int,int> tiii;int read() {int x=0,w=1; char c=getchar();while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}return x*w;}const int N=2e5+5;int T,n,m,a[N],b[N],fac[N],c[N],ifac[N],mod;int ksm(int x,int y,int r=1) {for(;y;y>>=1,x=x*x%mod) if(y&1) r=r*x%mod;return r;}void exgcd(int a,int b,int &x,int &y) {if(b==0) {x=1, y=0; return;}exgcd(b,a%b,x,y); int d=x;x=y, y=d-a/b*y;}int inv(int x) {int a,b; exgcd(x,mod,a,b); return (a%mod+mod)%mod;}void pre() {fac[0]=1;rep(i,1,n) {int x=i; c[i]=c[i-1];while(x%2==0) x/=2, c[i]++;fac[i]=fac[i-1]*x%mod;//cout<<i<<" "<<x<<" "<<fac[i]<<endl;}rep(i,1,n) ifac[i]=inv(fac[i]);ifac[0]=1;}int C(int x,int y) {if(x<y) return 0;int cc=c[x]-c[x-y]-c[y];if(cc>=m) return 0;else {int p=(1<<cc);return fac[x]*ifac[y]%mod*ifac[x-y]%mod*p%mod;}}void solve() {n=read(), m=read();rep(i,1,n) a[i]=read();int p=max(0ll,n-m*2);int flag=0; if(m==1) m++, flag=1;mod=1<<m;rep(i,1,n) {if(p<=m) b[i]=ksm(a[i],1<<p);else b[i]=ksm(a[i],m-1);}pre();rep(i,1,n-p) {a[i]=0;rep(j,i,n) {a[i]=(a[i]+b[j]*C(p,j-i))%mod;}}rep(j,p+1,n-1) {rep(i,1,n-j) {a[i]=(a[i]+a[i+1])*(a[i]+a[i+1])%mod;}}if(flag) a[1]%=2;printf("%lld\n",a[1]);}signed main() {T=read(); while(T--) solve();return 0;}