結果
問題 | No.329 全射 |
ユーザー |
![]() |
提出日時 | 2015-12-22 12:18:42 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 876 ms / 2,000 ms |
コード長 | 1,063 bytes |
コンパイル時間 | 1,444 ms |
コンパイル使用メモリ | 164,068 KB |
実行使用メモリ | 8,448 KB |
最終ジャッジ日時 | 2024-09-18 18:34:03 |
合計ジャッジ時間 | 9,980 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:24:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 24 | scanf("%d%d",&n,&m); | ~~~~~^~~~~~~~~~~~~~ main.cpp:25:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | for(i=1;i<=n;++i)scanf("%d",w+i); | ~~~~~^~~~~~~~~~ main.cpp:27:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | scanf("%d%d",&i,&j); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; #define mod 1000000007 int noktbl[1010][1010]; int nok(int n,int k){ if(!noktbl[n][k]){ noktbl[n][k]=k==0||k==n?1:(nok(n-1,k)+nok(n-1,k-1))%mod; } return noktbl[n][k]; } long long mpow(long long n,int e){ return e?(e&1?n:1)*mpow(n*n%mod,e/2)%mod:1; } priority_queue<int> a; int w[210],ln[210][210],li[210],u[210]; int rtbl[1010][1010]; int main(){ int i,j,k,l,m,n,r,s,t; scanf("%d%d",&n,&m); for(i=1;i<=n;++i)scanf("%d",w+i); for(k=0;k<m;++k){ scanf("%d%d",&i,&j); ln[i][li[i]++]=j; } r=0; for(k=1;k<=n;++k){ memset(u,0,sizeof u); u[k]=w[k]; a.push(k|w[k]<<8); while(!a.empty()){ l=a.top();a.pop(); s=l>>8; l&=255; for(i=0;j=ln[l][i];++i){ t=min(s,w[j]); if(u[j]<t){ u[j]=t; a.push(j|t<<8); } } } s=w[k]; for(l=1;l<=n;++l){ if((t=u[l])&&t==w[l]){ if(!rtbl[s][t]){ long long h=0; for(i=1;i<=t;++i){ h=(mpow(i,s)*nok(t,i)-h+mod)%mod; } rtbl[s][t]=h; } r=(r+rtbl[s][t])%mod; } } } printf("%d",r); }