結果
問題 | No.389 ロジックパズルの組み合わせ |
ユーザー |
![]() |
提出日時 | 2024-09-23 21:24:24 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,655 bytes |
コンパイル時間 | 9,128 ms |
コンパイル使用メモリ | 202,048 KB |
実行使用メモリ | 34,884 KB |
最終ジャッジ日時 | 2024-09-23 21:35:57 |
合計ジャッジ時間 | 20,980 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 99 |
ソースコード
#include<bits/stdc++.h>#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair<ll,ll>#define pii pair<ll,pair<ll,ll>>#define iip pair<pair<ll,ll>,ll>#define ppii pair<pair<ll,ll>,pair<ll,ll>>#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i<=r;i++)#define _For(i,l,r) for(int i=r;i>=l;i--)using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=2e6+10,mod=1e9+7;inline ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;}inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}ll n,x,sum,k;ll f[N],inv[N];ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1)ans=(ans*a)%mod;a=(a*a)%mod;b>>=1ll;}return ans;}void init(){f[0]=f[1]=inv[0]=inv[1]=1;For(i,2,N-1)f[i]=(f[i-1]*i)%mod;inv[N-1]=qpow(f[N-1],mod-2);_For(i,2,N-2)inv[i]=inv[i+1]*(i+1)%mod;}ll C(ll n,ll m){return f[n]*inv[m]%mod*inv[n-m]%mod;}bool End;int main(){// open("banner.in","banner.out");init();n=read();while(scanf("%lld",&x)!=EOF){++k;sum+=x;}sum=n-sum-k+1;if(sum<0){puts("NA");exit(0);}if(k==1&&!x){puts("1");exit(0);}write(C(sum+k,k));cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";return 0;}